Sparse NOMA: A Closed-Form Characterization
Benjamin M. Zaidel

Ori Shental

Shlomo Shamai (Shitz)

Faculty of Engineering
Bar-Ilan University
Ramat-Gan 52900, Israel
Email: benjamin.zaidel@gmail.com

Communications Theory Department
Bell Labs
Holmdel, New Jersey 07733, USA
Email: ori.shental@nokia-bell-labs.com

Department of Electrical Engineering
Technion
Haifa 32000, Israel
Email: sshlomo@ee.technion.ac.il

arXiv:1801.04427v1 [] 13 Jan 2018

Abstract
Understanding fundamental limits of the various technologies suggested for future 5G and beyond cellular systems is crucial for
developing efficient state-of-the-art designs. A leading technology of major interest is non-orthogonal multiple-access (NOMA). In
this paper, we derive an explicit rigorous closed-form analytical expression for the optimum spectral efficiency in the large-system
limit of regular sparse NOMA, where only a fixed and finite number of orthogonal resources are allocated to any designated user,
and vice versa. The basic Verdú-Shamai formula for (dense) randomly-spread code-division multiple-access (RS-CDMA) turns out
to coincide with the limit of the derived expression, when the number of orthogonal resources per user grows large. Furthermore,
regular sparse NOMA is rigorously shown to be spectrally more efficient than RS-CDMA across the entire system load range. It
may therefore serve as an efficient means for reducing the throughput gap to orthogonal transmission in the underloaded regime,
and to the ultimate Cover-Wyner bound in overloaded systems. The results analytically reinforce preliminary conclusions in [1],
which mostly relied on heuristics and numerical observations. The spectral efficiency is also derived in closed form for the suboptimal linear minimum-mean-square-error (LMMSE) receiver, which again extends the corresponding Verdú-Shamai LMMSE
formula to regular sparse NOMA.

I. I NTRODUCTION
Orthogonal transmission is the holy grail of multiple-access communications. Orthogonal multiple-access (OMA) allows for
a feasible transceiver design, which also achieves the ultimate total throughput in a fully-loaded Gaussian channel, where the
number of users equals the total number of available orthogonal resources. However, non-orthogonal multiple-access (NOMA)
schemes with tractable near-optimal receivers open up the practicality of operation in the overloaded regime, where the number
of designated users exceeds the number of available resources. Note that even for pragmatic underloaded systems it is typically
hard to maintain orthogonality, and OMA leads to severe throughput penalties. Thus, NOMA exhibits significant advantages
over OMA by either supporting more concurrent users or, alternatively, facilitating higher user throughput when orthogonality
breaks down. In a nutshell, these are the main incentives driving NOMA as a key enabler for the Internet-of-Things (IoT) and
5G and beyond networks. An overview of the ample literature on NOMA can be found, e.g., in [2] and references therein.
Sparse, or low-density code-domain (LDCD) NOMA is a prominent sub-category, which conceptually relies on multiplexing
low-density signatures (LDS) [3]. Sparse spreading codes comprising only a small number of non-zero elements are employed
for linearly modulating each user’s symbols over shared physical orthogonal resources. The sparse mapping between users and
resources is dubbed: regular when each user occupies a fixed number of resources, and each resource is used by a fixed number
of users; irregular when the respective numbers are random, and only fixed on average; partly-regular when each user occupies
a fixed number of resources, and each resource is used by a random, yet fixed on average, number of users (or vice versa).
The main attractiveness of this central class of NOMA schemes is in its inherent receiver complexity reduction, achieved
by utilizing message-passing algorithms (MPAs) [2]. Different variants of sparse NOMA, e.g., sparse-code multiple-access
(SCMA) [4], have recently gained much attention in 5G standardization. Naturally, information-theoretic analysis of sparse
NOMA has been a fruitful grounds for research, providing a great deal of insight into its workings, e.g., [5]–[8]. However, it
is important to note that neither of these contributions provide an explicit rigorous closed-form analytical characterization of
sparse NOMA throughput. This holds even in the large-system limit, and comes in sheer contrast to the insightful work by
Verdú and Shamai on (dense) randomly-spread code-division multiple-access (RS-CDMA) [9].
In a recent paper [1], the authors have presented a closed-form analytical expression for the limiting empirical squared
singular value density of a spreading (signature) matrix, corresponding to regular sparse NOMA. The result was rigorously
derived only for a repetition-based sparse spreading scheme, while for binary sparse random spreading the same result was
claimed to hold based on the heuristic cavity method of statistical physics. The limiting density was then used to plot the
optimum asymptotic spectral efficiency, but only by means of numerical integration.
In this contribution, using a recent fundamental result by Bordenave and Lelarge [10], we first re-establish the aforementioned
limiting density result in full rigor, and in fact extend it to the more general case of sparse signatures, of which non-zero
entries reside on the unit-circle in the complex plane. Then, a rigorous closed-form explicit analytical expression for the spectral
efficiency of regular sparse NOMA with optimum decoding is derived. The formula is obtained for Gaussian signaling and
non-fading channels in the asymptotic large-system limit. The Verdú-Shamai optimum spectral efficiency formula [9] turns out
to be a particular instantiation of the derived expression for the case where the spreading codes become dense. A closed-form

expression for the asymptotic spectral efficiency of the linear minimum-mean-square-error (LMMSE) receiver is also provided.
An extreme-SNR characterization leading to useful insights is given as well. The results allow for easy comparison to the
spectral efficiency of RS-CDMA [9] (representing dense NOMA), and other sparse NOMA variants, e.g., [5], [8]. Assuming
optimal decoding, the remarkable superiority of the feasible regular sparse NOMA over not only its irregular, or partly-regular,
counterparts, but also over the intractable RS-CDMA, as originally observed (only) numerically in [1], is here being analytically
verified.
II. S PARSE NOMA S YSTEM M ODEL
Consider a system where the signals of K users are multiplexed over N shared orthogonal resources. These resources
can designate, e.g., orthogonal frequencies in orthogonal frequency-division multiplexing (OFDM) based systems, or different
time-slots in time-hopping (TH) multiple-access systems [8]. Multiplexing is performed while employing randomly chosen
sparse spreading signatures of length N (namely, N -dimensional vectors). Each sparse signature is assumed to contain a small
number of non-zero entries (typically much smaller than N ), while the remaining entries are set to zero. The N -dimensional
received signal, at some arbitrary time instance, at the output of a generic complex Gaussian vector channel, adheres to
q
(1)
y = snr
d Ax + n ,
where x is a K-dimensional complex vector comprising the coded symbols of the users. Assuming Gaussian signaling,
full symmetry, fixed powers, and no cooperation between encoders corresponding to different users, the input vector x is
distributed as x ∼ CN (0, IK ); i.e., a unit energy per symbol per user is assumed. A denotes the N × K sparse signature
matrix, whose kth column represents the spreading signature of user k, and its non-zero entries designate the user-resource
mapping (user k occupies resource n if Ank 6= 0, where Ank denotes the (n, k)’th entry of A). Finally, n ∼ CN (0, IN )
denotes the N -dimensional circularly-symmetric complex additive white Gaussian noise (AWGN) vector at the receiving end.
The normalization factor √1d in (1), d ∈ N+ , controls the signature norms (as explained in the sequel). The parameter snr thus
designates the received signal-to-noise ratio (SNR) of each user, and we further use β , K
N to denote the system load (users
per resource).
In sparse NOMA, due to the sparsity of A, typically only a few of the users’ signals collide over any given orthogonal
resource. The regularity assumption dictates that each column of A (respectively, row) has exactly d (respectively, βd) nonzero entries. β is therefore chosen here so that βd ∈ N+ . The non-zero entries of A are assumed to arbitrarily reside on the
unit-circle in the complex plane. Repetition-based spreading and random binary spreading [1] thus constitute special cases.
The model may also account for phase-fading scenarios in conjunction with sparse spreading. The normalization in (1) ensures
that the columns of √1d A have unit norm. Finally, we also assume here that A is perfectly known at the receiving end, and
uniformly chosen randomly and independently per each channel use from the set of (βd, d)-regular matrices.
Note at this point that a key tool in the derivations to follow is the observation that the signature matrix A can be associated
with the adjacency matrix of a random (βd, d)-semiregular bipartite (factor) graph A, where a user node k and a resource
node n are connected if and only if Ank 6= 0. This factor graph is assumed henceforth to be locally tree-like1 , and to converge
in the large-system limit (as N → ∞) to a bipartite Galton-Watson tree (BGWT), as specified in Section III. This assumption
essentially implies that for large dimensions short cycles are rare (similar to LDPC codes [10]), and it allows for reduced
complexity iterative near-optimal multiuser detection by applying MPAs over the underlying factor graph.
III. A SYMPTOTIC S PECTRAL D ENSITY
Our first step is to characterize the limiting empirical distribution of the squared singular values of the normalized signature
matrix √1d A, which is a cornerstone in the derivation of our main analytical results. To this end, we first review a useful result
by Bordenave and Lelarge [10] on properties of random weighted bipartite graphs, whose random weak limit is the probability
measure of a BGWT. Due to space limitations, we avoid a fully formal representation, while referring the reader to [10] for a
full account.
Consider a sequence of random bipartite graphs {GN }, converging in law to a BGWT with degree distribution (δβd , δd ),
1
and parameter 1+β
. Let W be an N × K complex random matrix independent of GN , with i.i.d. entries having finite absolute
second moments. With some abuse of notation, let the weighted adjacency matrix of GN read

 
 

0
W
0 Ā
0 A
ÃN =
,
◦
,
(2)
A† 0
W† 0
Ā† 0
where ◦ denotes the Hadamard product, Ā is an N × K matrix such that Āij = 1 if vertex i is connected by an edge to vertex
N + j on GN , and Āij = 0 otherwise, where i ∈ {1, . . . , N }, and j ∈ {1, . . . , K}. Let H denote the set of holomorphic
1
functions f : C+ → C+ such that |f (z)| ≤ Im(z)
. Finally, let P(H) denote the space of probability measures on H.
1A

precise mathematical definition can be found, e.g., in [10].

Theorem 1 ([10, Theorems 4 & 5]). Let the above assumptions on the structure of ÃN hold. Then
1) There exists a unique pair of probability measures (µa , µb ) ∈ P(H) × P(H) such that for all z ∈ C+
Pβd−1
2
d
Y a (z) = −(z + i=1 Wib Yib (z))−1
Pd−1
d
2
Y b (z) = −(z + i=1 |Wia | Yia (z))−1 ,

(3)
(4)

where Y a , Yia (respectively, Y b , Yib ) are i.i.d. random variables with law µa (respectively, µb ), and Wia , Wib are i.i.d.
random variables distributed as W11 2 .
2) For all z ∈ C+ , the Stieltjes transform3 mÃN (z) of the empirical eigenvalue distribution of ÃN converges as N → ∞
β
1
in L1 to mÃ (z) = 1+β
E{X a (z)} + 1+β
E{X b (z)}, where for all z ∈ C+
d

X a (z) = −(z +
d

X b (z) = −(z +

Pβd

2

i=1
Pd
i=1

Wib Yib (z))−1
2

|Wia | Yia (z))−1 ,

(5)
(6)

where Yia , Yib , Wia , and Wib are i.i.d. copies with laws as in Part (1).
Turning to the sparse regular NOMA setting specified in Section II, we immediately observe that the graph A associated
with the signature matrix A (cf. (1)) falls exactly within the framework of Theorem 1, and its weighted adjacency matrix
can be expressed as in (2). Furthermore, the underlying assumption on the spreading signatures dictates that all entries of the
corresponding weight matrix W have surely a unit absolute value. We thus get the following result.
Theorem 2. Let A be a sparse random N × K matrix with exactly 2 ≤ d ∈ N+ < ∞ (respectively, 2 ≤ βd ∈ N+ < ∞)
non-zero entries in each column (respectively, row), arbitrarily distributed over the unit-circle in C. Assume that the (βd, d)semiregular bipartite graph A associated with A is locally tree-like, with a BGWT having degree distribution (δβd , δd ) and
βd−1
1
parameter 1+β
as a weak limit. Let α , d−1
d and γ ,
d . Then
1) For all z ∈ C+ , the Stieltjes transform of the empirical eigenvalue distribution of d1 AA† converges as N → ∞ in L1 to
−1
β
m d1 AA† (z) = − z − 1+αm(z)
,
(7)
where m(z) solves the following deterministic equation:
m(z) = − z −

−1
γ
1+αm(z)

.

2) Subject to the convergence of the Stieltjes transform, the weak limit of the empirical eigenvalue distribution of
as N → ∞ is a distribution with density
√
[λ−λ− ]+ [λ+ −λ]+
ρ(λ, β, d) = [1 − β]+ δ(λ) + βd
,
2π
λ(βd−λ)
√
√
where λ± = ( α ± γ)2 , δ(λ) is a unit point mass at λ = 0, and [z]+ , max{0, z}.

(8)
1
†
d AA

(9)

Proof Outline: The weights {Wia , Wib } in (3) and (4) have unit absolute values. The equations hence admit a unique
deterministic solution. Next, note that the eigenvalues of


AA†
0
2
ÃN =
(10)
0
A† A
are simply the eigenvalues of AA† together with those of A† A (which are in fact the same up to |K − N | additional zero
eigenvalues). Furthermore, the limiting Stieltjes transform of the empirical
distribution of Ã2N admits the following
q eigenvalue
√
relation zmÃ2 (z 2 ) = mÃ (z). This lets us conclude that m d1 AA† (z) = dz X a ( dz), where X a (z) is obtained from (5). Eqs.
(7) and (8) then follow after some algebra. Finally, we get (9) using the Stieltjes inversion formula.
2 The

d

equality = in (3) and (4) is in the sense that the distribution of the random
variables on both sides of the equation is the same.
R
1
Stieltjes transform of a probability measure µ on R reads m(z) , R x−z
dµ(x), z ∈ C+ . The measure µ can be recovered from m(z) via the
1
Stieltjes inversion formula dµ(λ) = π lim→0+ Im(m(z))|z=λ+j dλ, where the limit is in the sense of weak convergence of measures (e.g., [11]).
3 The

IV. O PTIMUM R ECEIVER
The fundamental figure of merit for system performance is taken here as the normalized spectral efficiency (total throughput)
in bits/sec/Hz per dimension. For optimum processing this quantity corresponds to the ergodic sum-capacity, given by the
normalized conditional input-output mutual information [9]:
opt
CN
(snr, β, d) ,

=

1
N I(x; y|A)

1
N E log2 det

IN +

†
snr
d AA



.

(11)

Focusing on the large-system limit, the asymptotic spectral efficiency of the optimum receiver corresponds to
opt
C opt (snr, β, d) , lim CN
(snr, β, d) ,

(12)

N →∞

where the existence of the limit follows from Theorem 2. The following result is one of the main contributions of this paper.
Theorem 3. Let d, β, α and γ be as in Theorem 2. Further let β̃ ,
converges as N → ∞ to

α
γ

and ζ ,

βd
γ .

Then, the optimum spectral efficiency (11)

C opt (snr, β, d) =
β(d−1)+1
2


log2 1 + (γ + α)snr − 14 F(γsnr, β̃)

+ (β − 1) log2 1 + αsnr − 14 F(γsnr, β̃)


(1+βd snr)2
,
− β(d−1)−1
log
2
2
G(γsnr,ζ,β̃)

where (cf. [9]) F(x, z) , ((x (1 +

√

2

z) + 1)1/2 − (x (1 −

√

(13)

2

z) + 1)1/2 )2 and

G(x, y, z) ,
q
2
q
√
√
√
√
(y−(1− z)2 )(x(1+ z)2 +1)− (y−(1+ z)2 )(x(1− z)2 +1)
√
√
√
√
y−(1− z)2 − y−(1+ z)2
√
x, y, z ∈ R+ , y ≥ (1 + z)2 .

(14)

Proof Outline: The space H specified in Section III, equipped with an appropriate topology, is a complete separable
metrizable compact space (see [10]). Considering the sequence of Stieltjes transforms converging to (7) by Theorem 2, recall
that the ergodic normalized sum-capacity (11) is determined by the distribution of the signature matrices. Therefore, by the
Skorokhod representation theorem (see, e.g., [10, Theorem 7]), we can assume that the sequence of Stieltjes transforms and
its limit (which is in fact a deterministic function) are defined on a common probability space, and that the convergence
to the limit is in the almost sure sense. We next observe that by Hadamard’s inequality, along with the unit absolute value
†
of the non-zero entries of A, N1 log2 det IN + snr
≤ log2 (1 + βsnr) < ∞. This in turn implies that the sequence
d AA
snr
1
†
log
det
I
+
AA
is
uniformly
integrable.
By
the
weak convergence stated in Theorem 2 (cf. (9)) we can hence
N
2
N
d
conclude that
Z ∞
C opt (snr, β, d) =
log2 (1 + snrλ)ρ(λ, β, d) dλ .
(15)
0

Explicit calculation of the integral finally yields (13).
Remark 4. Although (13) applies to 2 ≤ d, βd ∈ N+ < ∞, total throughputs on the convex closure of the respective rates are
achievable by means of time-sharing between different (d, βd) points in the admissible set.
We complete the asymptotic analysis of the optimum receiver by means
Recall that a
 of extreme-SNR characterization.

Eb
Eb
S0
spectral efficiency R is approximated in the low-SNR regime as R ≈ 3dB
|
−
|
,
where
S
denotes
the low0
N0 dB
N0 min dB
Eb
Eb
Eb
SNR slope, N
is the minimum N
that enables reliable communications, and 3dB , 10 log10 2 [12]. The SNR and N
0 min
0
0
Eb
are related via βsnr = R N
.
In
the
high-SNR
regime
the
spectral
efficiency
is
approximated
as
R
≈
S
(log
snr
−
L
),
∞
∞
2
0
where S∞ denotes the high-SNR slope (multiplexing gain), and L∞ denotes the high-SNR power offset [12]. The results are
summarized in the following proposition (the proof is omitted due to space limitations).


Eb opt
Proposition 5. Let d and β be as in Theorem 2. Then, the low-SNR parameters of the optimum receiver read: N
= ln 2,
0 min
2βd
opt
= min(β, 1), while the high-SNR power
and S0opt = d(β+1)−1
. The high-SNR slope of the optimum receiver is given by S∞
offset satisfies
Lopt
∞ =


 1
(d − 1) log2 1 − d1 , β < 1

 β − 1 log2 (1 − β) −


−(d − 1) log 1 − 1 ,
β=1
2
d
(β − 1) log2 (β − 1) − β log2 β




1
− (βd − 1) log2 1 − βd
,
β > 1.

(16)

Eb
Comparison to RS-CDMA [12] reveals that N
and S∞ are identical in both settings. However, the low-SNR slope of
0 min
regular sparse NOMA is strictly higher, while the high-SNR power offset is strictly lower, compared to RS-CDMA. Regular
sparse NOMA thus exhibits superior performance in extreme-SNR regimes. The spectral efficiency coincides with that of
RS-CDMA as d → ∞ in all SNR regimes, which is also evident from (15) and (9) (cf. [1]).

V. LMMSE R ECEIVER
In this section we turn to investigate the ergodic spectral efficiency of the LMMSE receiver. Recall that the corresponding
error covariance matrix is given by M = (IK + snr R)−1 , where R , d1 A† A is the signature crosscorrelation matrix [9]. The
signal-to-interference-plus-noise ratio (SINR) at the output of the receiver for user k is M1kk − 1, and the spectral efficiency of
the LMMSE receiver thus reads
 1 PK

1
C mmse (snr, β, d) = β E K
.
(17)
k=1 log2 Mkk
The following theorem characterizes the spectral efficiency of the LMMSE receiver in the large-system limit.
Theorem 6. Let the definitions and assumptions of Theorem 3 hold. Then, the spectral efficiency of the LMMSE receiver
converges as N → ∞ to


1+βd snr
mmse
C
(snr, β, d) = βlog2
.
(18)
dF(γsnr,β̃)
1+dγ snr−

Proof Outline: Let RR (z) , (R − zIK )

−1

4

+

, z ∈q
C , denote the resolvent of R. Following [10], it can be shown that the
√
diagonal entries of RR (z) converge in distribution to dz X b ( dz) (cf. (6)), which gives the Stieltjes transform of the limiting
d

1
1
mR (− snr
),
empirical eigenvalue distribution of R, mR (z). Applying analytic continuation we thus conclude that Mkk −
→ snr
M1 . Since the random variables {Mkk } have a bounded strictly positive support, we may conclude by the continuity of log2 ( x1 )
and uniform integrability of log2 ( M1kk ), that C mmse (snr, β, d) = β log2 (M1−1 ), leading to (18).
We note here that the time-sharing argument in Remark 4 holds for the LMMSE receiver as well. The extreme-SNR
characterization of this receiver is given next.

Eb mmse
= ln 2,
Proposition 7. Let d and β be as in Theorem 2. Then, the low-SNR parameters of the LMMSE receiver read: N
0 min
2βd
mmse
and S0
= (2β+1)d−2 . The high-SNR slope of the LMMSE receiver is given by


β, β < 1
mmse
(19)
S∞
= 12 , β = 1


0, β > 1

while the high-SNR power offset satisfies
Lmmse
∞



(
1
log2 1−β
+ log2
=

d−1
log2 d
,

d−1
d



,

β<1
β = 1.

Comparison to [12] leads again to the same conclusions as drawn for the optimum receiver.

(20)

6

4

No Spreading
5.5

Reg. Sparse d=3
Reg. Sparse d=10
RS-CDMA d
Irreg. Sparse d=10
Irreg. Sparse d=3
Partly-Reg. Sparse d=1

Optimal

l

na

o
rth

5

go

O

C [bits/sec/Hz]

C [bits/sec/Hz]

5

6

No Spreading

3
LMMSE

2

Optimal

4.5

Reg. Sparse d=2
Reg. Sparse d=3
Reg. Sparse d=10
RS-CDMA d
Irreg. Sparse d=10
Irreg. Sparse d=2
Partly-Reg. Sparse d=1

4
3.5
3
2.5

1

LMMSE

2
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

1.5
1

(a) Underloaded regime

1.5

2

2.5

3

3.5

4

(b) Overloaded regime

Fig. 1: Limiting spectral efficiency vs. the system load β for Eb /N0 = 10 dB.
VI. N UMERICAL R ESULTS
Some numerical results for the limiting spectral efficiency of regular sparse NOMA, following (13) and (18), are shown in
Eb
= 10dB. The results were calculated for d = 2 (β ≥ 1),
Fig. 1, and plotted as a function of the system load β for fixed N
0
3 and 10. The markers in the figure designate the points for which βd ∈ N+ . The piecewise linear (dotted) lines represent
the achievable throughputs by exercising time-sharing between integer βd values (see Remark 4). Fig. 1 clearly indicates that
regular sparse NOMA outperforms RS-CDMA [9, Eqs. (9), (12)]. In the underloaded regime (β < 1), the gap to the spectral
efficiency of orthogonal transmissions [9, Eq. (8)] is reduced. In the overloaded regime the scheme reduces the gap to the
ultimate performance limit, as given by the Cover-Wyner bound [9, Eq. (4)], corresponding to the absence of spreading. Note
also that the spectral efficiency of regular sparse NOMA approaches that of RS-CDMA from above with the increase of the
sparsity parameter d, as already indicated in [1]. For the sake of comparison we also included in Fig. 1 the spectral efficiencies
of irregular sparse NOMA [5, Eqs. (28)–(32)], and partly-regular sparse NOMA when the transmit energy is concentrated in a
single orthogonal resource (namely, d = 1) [8, Eq. (13)]4 . The results reinforce the initial observations made in [1], indicating
that irregular sparse NOMA schemes exhibit degraded performance, due to the fact that some resources may be left unused
(and in the fully irregular case some users may end up without any designated resources). Irregular sparse NOMA schemes
are also observed to approach the spectral efficiency of RS-CDMA with the increase of d, however the approach to the limit
is from below (cf. [8]).
VII. C ONCLUDING R EMARKS
Regular sparse NOMA has been investigated in this paper in the large-system limit. Considering the optimum receiver
(whose performance can be approached using practical MPAs even in overloaded regimes), and the simple LMMSE receiver,
the respective spectral efficiencies were expressed in closed explicit form, and shown to outperform the achievable throughputs
of both RS-CDMA and irregular sparse NOMA. It is crucial to emphasize that the underlying NOMA system model is markedly
different here from previously analyzed settings. Firstly, the random matrices are sparse, as opposed to standard RS-CDMA [9],
where performance is governed by the Marčenko-Pastur law. Secondly, the entries of the signature matrix are not i.i.d., as
opposed to Poissonian irregular sparse NOMA (e.g., [5]). The setting also differs from the recently analyzed partly-regular
scheme [8] (time-hopping CDMA), where sparse random spreading sequences with a fixed number of non-zero entries per
time frame are employed. This is since in the current setting the number of non-zero entries is identical and fixed also in
each row of the signature matrix, in contrast to [8]. Finally, the setting differs also from the sparse models considered, e.g.,
in [7], where the limiting average sparsity amounts to a fixed (small) fraction of the dimensions (implying linear scaling); and
[6], where the number of non-zero signature entries amounts to a vanishing fraction of its dimension, but is still infinite in
the large-system limit. We conclude by noting that our observations facilitate the understanding of the potential performance
gains of sparse NOMA, and advocate employing regular schemes as a key practical tool for enhancing performance of future
highly loaded cellular systems.
4 This

seems to be the only case where the spectral efficiency is fully analytically tractable in this framework (cf. [8]).

ACKNOWLEDGMENT
The work of B. M. Zaidel and S. Shamai (Shitz) was supported by the Heron consortium via the Israel Ministry of Economy
and Industry.
R EFERENCES
[1] O. Shental, B. M. Zaidel, and S. Shamai (Shitz), “Low-density code-domain NOMA: Better be regular,” in Proc. 2017 IEEE Int. Symp. Inf. Theory
(ISIT’17), Aachen, Germany, Jun. 25–30, 2017.
[2] Z. Ding, X. Lei, G. J. Karagiannidis, R. Schober, J. Yuan, and V. K. Bhargava, “A survey on non-orthogonal multiple access for 5G networks: Research
challenges and future trends,” IEEE J. Sel. Areas Commun., vol. 35, no. 10, pp. 2181–2195, Oct. 2017.
[3] R. Hoshyar, R. Razavi, and M. Al-Imari, “LDS-OFDM an efficient multiple access technique,” in Proc. 2010 IEEE 71st Veh. Technol. Conf., Taipei,
Taiwan, May 2010, pp. 1–5.
[4] H. Nikopour and H. Baligh, “Sparse code multiple access,” in Proc. 2013 IEEE 24th Int. Symp. Personal Indoor and Mobile Radio Commun. (PIMRC),,
London, UK, Sep. 2013, pp. 332–336.
[5] M. Yoshida and T. Tanaka, “Analysis of sparsely-spread CDMA via statistical mechanics,” in Proc. 2006 IEEE Int. Symp. Inf. Theory (ISIT’06), Seatle,
WA, Jul. 2006, pp. 2378–2382.
[6] D. Guo and C.-C. Wang, “Multiuser detection of sparsely spread CDMA,” IEEE J. Sel. Areas Commun., vol. 26, no. 3, pp. 421–431, Apr. 2008.
[7] D. Guo, D. Baron, and S. Shamai (Shitz), “A single-letter characterization of optimal noisy compressed sensing,” in Proc. 47th Ann. Allerton Conf.
Commun. Control Comp., Monticello, IL, Sep./Oct. 2009.
[8] G. C. Ferrante and M.-G. Di Benedetto, “Spectral efficiency of random time-hopping CDMA,” IEEE Trans. Inf. Theory, vol. 61, no. 12, p. 6643, Dec.
2015.
[9] S. Verdú and S. Shamai (Shitz), “Spectral efficiency of CDMA with random spreading,” IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 622–640, Mar.
1999.
[10] C. Bordenave and M. Lelarge, “Resolvent of large random graphs,” Random Struct. Alg., vol. 37, pp. 332–352, 2010.
[11] A. M. Tulino and S. Verdú, “Random matrix theory and wireless communications,” Found. Trends Commun. Inf. Theory, vol. 1, no. 1, pp. 1–182, 2004.
[12] S. Shamai (Shitz) and S. Verdú, “The impact of frequency-flat fading on the spectral efficiency of CDMA,” IEEE Trans. Inf. Theory, vol. 47, no. 4, pp.
1302–1327, May 2001.

