---
abstract: 'Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links.  Each user has a fixed number $k$ of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading).  In this paper we consider the many-user asymptotics of Chen-Chen-Guo’2017, where the number of users grows linearly with the blocklength.  In addition, we adopt a per-user probability of error criterion of Polyanskiy’2017 (as opposed to classical joint-error probability criterion).  Under these two settings we derive bounds on the optimal required energy-per-bit for reliable multi-access communication.  We confirm the curious behaviour (previously observed for non-fading MAC) of the possibility of perfect multi-user interference cancellation for user densities below a critical threshold.  Further we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e., TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection).' 
author:
- '[^1] [^2]'
- 
bibliography:
- 'IEEEabrv.bib'
- 'refs.bib'
---

Many-user MAC, fading, fundamental limits, no-CSI

Introduction {#sec:intro}
============

We clearly witness two recent trends in the wireless communication technology: the increasing deployment density and miniaturization of radio-equipped sensors.  The first trend results in progressively worsening interference environment, while the second trend puts ever more stringent demands on communication energy efficiency.  This suggests a bleak picture for the future networks, where a chaos of packet collisions and interference contamination prevents reliable connectivity. 

This paper is part of a series aimed at elucidating the fundamental tradeoffs in this new “dense-networks” regime of communication, and on rigorously demonstrating suboptimality of state-of-the-art radio-access solutions (ALOHA, orthogonalization, or FDMA/TDMA [^3], and treating interference as noise, or TIN).  This suboptimality will eventually lead to dramatic consequences.  For example, environmental impact of billions of toxic batteries getting depleted at 1/10 or 1/100 of the planned service time is easy to imagine.  In order to future-proof our systems, we should avoid locking in on outdated and unfixable multiple-access architectures causing tens of dB losses in energy efficiency.  The information-theoretic analysis in this paper demonstrates that the latter is indeed unavoidable (with state-of-the-art schemes).  However, our message is in fact optimistic, as we also demonstrate existence of protocols which are partially immune to the increase of the sensor density. 

Specifically, in this paper we consider a problem of $K$ nodes communicating over a frame-synchronized multiple-access channel.  When $K$ is fixed and the frame size $n$ (which we will also call “blocklength” or the “number of degrees of freedom”) is taken to infinity we get the classical regime [@cover2012elements], in which the fundamental limits are given by well-known mutual information expressions.  A new regime, deemed *many-access*, was put forward by Chen, Chen and Guo [@chen2017capacity].  In this regime the number of nodes $K$ grows with blocklength $n$. It is clear that the most natural scaling is linear: $K=\mu n,
n\to\infty$, corresponding to the fact that in time $n$ there are linearly many users that will have updates/traffic to send [@polyanskiy2017perspective].  That is, if each device wakes up once in every $T$ seconds and transmits over a frame of length $t$, then in time (proportional to) $t$ there are $K\approx t/T$ users where $t$ is large enough for this approximation to hold but small that no device wakes up twice.  Further, asymptotic results obtained from this linear scaling have been shown to approximately predict behavior of the fundamental limit at finite blocklength, e.g. at $n=30000$ and $K<=300$ [@polyanskiy2017perspective; @ZPT-isit19].  The analysis of [@chen2017capacity] focused on the regime of infinitely large payloads (see also [@wei2018fundamental] for a related massive MIMO MAC analysis in this setting).  In contrast [@polyanskiy2017perspective] proposed to focus on a model where each of the $K=\mu n$ nodes has only finitely many bits to send.  In this regime, it turned out, one gets the relevant engineering trade-offs.  Namely, the communication with finite energy-per-bit is possible as $n\to\infty$ and the optimal energy-per-bit depends on the user density $\mu$. For this to happen, however, a second crucial departure from the classical MAC model was needed: the per-user probability of error, *PUPE*, criterion [@polyanskiy2017perspective]. 

These two modifications (the scaling $K=\mu n$ and the PUPE) were investigated in the case of the AWGN channel in [@polyanskiy2017perspective; @ZPT-isit19; @polyanskiy2018_course].  We next describe the main discovery of that work.  The channel model is: $$\label{eq:awgn}
    Y^n = \sum_{i=1}^K X_i + Z^n\,,\qquad Z^n \sim \mathcal{CN}(0,I_n)\,,$$ and $X_i = f_i(W_i) \in \mathbb{C}^n$ is the codeword of $i$-th user corresponding to $W_i \in [2^k]$ chosen uniformly at random.  The system is said to have PUPE $\epsilon$ if there exist decoders $\hat W_i = \hat W_i(Y^n)$ such that

[LLL]{} \[eq:pupe1\] P\_[e,u]{}= \_[i=1]{}\^K . 

The energy-per-bit is defined as $\frac{E_b}{N_0}=\frac{1}{k} \sup_{i\in [K], w\in [2^k]} \|f_i(w)\|^2$. The goal in [@polyanskiy2017perspective; @polyanskiy2018_course] was to characterize the asymptotic limit $$\label{eq:fund_lim}
\mate^*(\mu, k, \epsilon) \eqdef \limsup_{n\to\infty} \inf \frac{E_b}{N_0}$$ where infimum is taken over all possible encoders $\{f_i\}$ and decoders $\{\hat W_i\}$ achieving the PUPE $\epsilon$ for $K=\mu n$ users. 

To predict how $\mate^*(\mu, \epsilon)$ behaves, first consider a naive Shannon-theoretic calculation [@verdu2002spectral]: if $K$ users want to send $k$ bits in $n$ degrees of freedom, then their sum-power $P_{tot}$ should satisfy $$n\log(1+P_{tot}) = kK\,.$$ In turn, the sum-power $P_{tot} = \frac{kK}{n} \frac{E_b }{ N_0}$. Overall, we get $$\mate^* \approx \frac{2^{\mu k} - 1}{ k\mu}\,.$$ This turns out to be a correct prediction, but only in the large-$\mu$ regime.  The true behavior of the fundamental limit is roughly given by $$\mate^*(\mu, k, \epsilon) \approx \max\left(\frac{2^{\mu k} - 1}{ k\mu}, \mate_{\mathrm{s.u.}}\right)\,,$$ where $\mate_{\mathrm{s.u.}}=\mate_{\mathrm{s.u.}}(k,\epsilon)$ does not depend on $\mu$ and corresponds to the single-user minimal energy-per-bit for sending k bits with error $\epsilon$, for which a very tight characterization is given in [@polyanskiy2010minimum].  In particular, with good precision for $k\ge 10$ we have $$\label{eq:E_su}
\mate_{\mathrm{s.u.}}(k,\epsilon)=\frac{1}{2}\left(\mathcal{Q}^{-1}\left(2^{-k}\right)-\mathcal{Q}^{-1}\left(1-\epsilon\right)\right)^2$$ where $\mathcal{Q}$ is the complementary CDF of the standard normal distribution: $\mathcal{Q}(x)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{u^2}{2}}du$.

In all, results of [@polyanskiy2017perspective; @ZPT-isit19; @polyanskiy2018_course] suggest that the minimal energy-per-bit has a certain “inertia”: as the user density $\mu$ starts to climb from zero up, initially the energy-per-bit should stay the same as in the single-user $\mu=0$ limit.  In other words, optimal multiple-access architectures should be able to *perfectly cancel all multi-user interference (MUI)*, achieving an essentially single-user performance for each user, *provided the user density is below a critical threshold*.  Note that this is much better than orthogonalization, which achieves the same effect at the expense of shortening the available (to each user) blocklength by a factor of $\frac{1}{ K}$. Quite surprisingly, standard approaches to multiple-access such as TDMA and TIN[^4], while having an optimal performance at $\mu\to0$ demonstrated a significant suboptimality for $\mu>0$ regime.  In particular, no “inertia” was observed and the energy-per-bit for those suboptimal architectures is always a monotonically increasing function of the user density $\mu$. This opens the (so far open) quest for finding a future-proof MAC architecture that would achieve $\mate_{\mathrm{s.u.}}$ energy-per-bit for a strictly-positive $\mu>0$.

(We note that in this short summary we omitted another important part of [@polyanskiy2017perspective]: the issue of random-access – i.e. communicating when the identities/codebooks of active users are unknown a priori.  We mention, however, that for the random-access version of the problem, there are a number of low-complexity (and quite good performing) algorithms that are available [@kowshik2019energy; @ordentlich2017low; @vem2017user; @amalladinne2018coupled; @10.1007/978-3-030-01168-0_15; @thompson2018compressed; @calderbank2018chirrup].) 

The *contribution* of this paper is in demonstrating the same perfect MUI cancellation effect in a much more practically relevant communication model, in which the ideal unit power-gains of  are replaced by random (but static) fading gain coefficients.  We consider two cases of the channel state information: known at the receiver (CSIR) and no channel state information (noCSI). 

*Key technical ideas:* For handling the noCSI case we employ the subspace projection decoder similar to the one proposed in [@yang2014quasi], which can be seen as a version of the maximum-likelihood decoding (without prior on fading coefficients) – an idea often used in support recovery literature [@wainwright2009information; @reeves2009note; @reeves2012sampling].  Another key idea is to decode only a subset of users corresponding to the strongest channel gains – a principle originating from Shamai-Bettesh [@bettesh2000outages].  While the randomness of power-gains increases the energy-per-bit requirements, we also mention that [@kowshik2019energy] finds an unexpected advantage: the inherent randomization helps the decoder disambiguate different users and improves performance of the belief propagation decoder. 

The paper is organized as follows.  In Section \[sec:model\] we formally define the problem and the fundamental limits.  In Section \[sec:classical\] as a warm-up we discuss the classical regime ($K$–fixed, $n\to\infty$) under the PUPE criterion.  We show that our projection decoder achieves the best known achievability bound in this setting [@bettesh2000outages]. ( We also note that for the quasi-static fading channel model the idea of PUPE is very natural, and implicitly appears in earlier works, e.g. [@bettesh2000outages; @tuninetti2002throughput], where it is conflated with the outage probability.)  After this short warm-up we go to our main Section \[sec:manymac\], which contains rigorous achievability and converse bounds for the $K=\mu n, n\to\infty$ scaling regime.  Finally, we conclude with numerical evaluations and discussions in Section \[sec:numerical\], where we also compare our bounds with the TDMA and TIN. 

Notations
---------

Let $\mathbb{N}$ denote the set of natural numbers.  For $n\in\mathbb{N}$, let $\mathbb{C}^n$ denote the $n$–dimensional complex Euclidean space.  Let $S\subset \mathbb{C}^n$. We denote the projection operator or matrix on to the subspace *spanned* by $S$ as $P_{S}$ and its orthogonal complement as $P^{\perp}_{S}$. For $0\leq p\leq 1$, let $h_2(p)=-p\log_2(p)-(1-p)\log_2(1-p)$ and $h(p)=-p\ln(p)-(1-p)\ln(1-p)$, with $0\ln 0$ defined to be $0$. We denote by $\mathcal{N}(0,1)$ and $\cn(0,1)$ the standard normal and the standard circularly symmetric complex normal distributions, respectively.  $\mathbb{P}$ and $\mathbb{E}$ denote probability measure and expectation operator respectively.  For $n\in \mathbb{N}$, let $[n]=\{1,2,...,n\}$. $\log$ denotes logarithm to base $2$. Lastly, ${\left\| \cdot \right\|}$ represents the standard euclidean norm. 

Definitions and System Model {#sec:model}
============================

$$\label{eq:sys1}
Y^n=\sum_{i=1}^{K}H_i X_i^n+Z^n$$ where $Z^n{\mathbin{\overset{}{\kern\z@\sim}}}\cn(0,I_n)$, and $H_i{\mathbin{\overset{iid}{\kern\z@\sim}}}\cn(0,1)$ are the fading coefficients which are independent of $\{X^n_i\}$ and $Z^n$. Naturally, we assume that there is a maximum power constraint: $$\label{eq:pow}
{\left\| X^n_i \right\|}^2\leq nP.$$

We consider two cases: 1) no channel state information (no-CSI): neither the transmitters nor the receiver knows the realizations of channel fading coefficients, but they both know the law; 2) channel state information only at the receiver (CSIR): only the receiver knows the realization of channel fading coefficients.  The special case of where $H_i=1,\forall i$ is called the Gaussian MAC (GMAC). 

In the rest of the paper we drop the superscript $n$ unless it is unclear. 

\[def:0\] An $\left((M_1,M_2,...,M_K),n\right)$ code for the MAC $P_{Y^n|X^n}$ is a set of (possibly randomized) maps $\{f_i:[M_i]\to\mathcal{X}_i^n\}_{i=1}^{K}$ (the encoding functions) and $g:\mathcal{Y}^n\to \prod_{i=1}^{K}[M_i]$ (the decoder). 

Classical regime: $K$ fixed, $n\to\infty$ {#sec:classical}
=========================================

In this section, we focus on the channel under classical asymptotics where $K$ is fixed (and large) and $n\to \infty$. We show that subspace projection decoder achieves a) $\epsilon$–capacity region ($C_{\epsilon,J}$) for the joint error and b) the best known bound for $\epsilon$–capacity region $C_{\epsilon,PU}$ under per-user error.  This motivates using projection decoder in the many-user regime. 

Joint error
-----------

A rate tuple $(R_1,...,R_K)$ is said to be $\epsilon$–achievable [@han1998information] for the MAC if there is a sequence of codes whose rates are asymptotically at least $R_i$ such that joint error is asymptotically smaller than $\epsilon$. Then the $\epsilon$–capacity region $C_{\epsilon,J}$ is the closure of the set of $\epsilon$–achievable rates.  $$\label{eq:cap}
C_{\epsilon,J} =\left\{R=(R_1,...,R_K):\forall i,R_i\geq 0 \text{ and } P_{0}(R)\leq \epsilon\right\}$$ where the outage probability $P_{0}(R)$ is given by

[L]{} \[eq:outage\] P\_[0]{}(R)=\

\[th:cap\_joint\] Let $R\in C_{\epsilon,J}$ of .  Then $R$ is $\epsilon$–achievable through a sequence of codes with the decoder being the projection decoder . 

Per-user error
--------------

The $\epsilon$–capacity region for the channel under per-user error, $C_{\epsilon,PU}$ is defined similarly as $C_{\epsilon,J}$ but with per-user error instead of joint error.  $C_{\epsilon,PU}$ is unknown, but the best lower bound is given by the Shamai-Bettesh capacity bound [@bettesh2000outages]: given a rate tuple $R=(R_1,...,R_K)$, an upper bound on the per-user probability of error under the channel , as $n\to\infty$, is given by

[LLL]{} \[eq:pu3\] P\_[e,u]{}& & P\_e\^S(R)\
&=& 1-{ |D|:D, SD, S,.\
&& .  \_[iS]{}R\_i &lt; (1+) }

where the maximizing set, among all those that achieve the maximum, is chosen to contain the users with largest fading coefficients.  The corresponding achievability region is

[LLL]{} \[eq:pu3a\] C\^[S.B]{}\_[,PU]{}={R: P\_e\^S(R)}

and hence it is an inner bound on $C_{\epsilon,PU}$.

We note that, in [@bettesh2000outages], only the symmetric rate case i.e, $R_i=R_j\, \forall i,j$ is considered.  So is the extension of that result to the general non-symmetric case. 

\[th:pu1\] For any $R\in C^{S.B}_{\epsilon,PU}$ there exists a sequence of codes with projection decoder with asymptotic rate $R$ such that the per-user probability of error is asymptotically smaller than $\epsilon$

In the case of symmetric rate, an outer bound on $C_{\epsilon,PU}$ can be given as follows. 

\[prop:conv\] If the symmetric rate $R$ is such that $P_{e,u}\leq \epsilon$, then

[LLL]{} \[eq:pu\_conv\] R& { ,\_2(1-P(1-))}, (,1\]

In the above figure we have also presented the performance of TDMA.  That is, if we use orthogonalization then for any number of users $K$ (not necessarily large), we have $$\label{eq:TDMA_classical_pupe}
 \epsilon = {\mathbb{P}\left[R > 1/K \log (1+KP |H|^2) \right]}$$ where $\epsilon$ is the PUPE.  Thus the sum-rate vs $E_b/N_0$ formula for orthogonalization is

$$\label{eq:TDMA_ebn0}
E_b/N_0= \frac{2^S-1}{S}\frac{1}{-\ln (1-\epsilon)}$$

where $S$ is the sum-rate or the spectral efficiency. 

We see that orthogonalization is suboptimal under the PUPE criterion.  The reason is that it fails to exploit the multi-user diversity by allocating resources even to users in deep fades. [ ]{} 

Many user MAC: $K=\mu n$, $n\to\infty$ {#sec:manymac}
======================================

This is our main section.  We are interested in the tradeoff of minimum $E_b/N_0$ required for the PUPE to be smaller than $\epsilon$, with the user density $\mu$ ($\mu<1$).  So, we fix the message size $k$. Let $S=k\mu$ be the spectral efficiency. 

We focus on the case of different codebooks, but under symmetric rate.  So if $M$ denotes the size of the codebooks, then $S=\frac{K\log M}{n}=\mu\log M$. Hence, given $S$ and $\mu$, $M$ is fixed.  Let $\PT=KP$ denote the total power.  Therefore denoting by $\mathcal{E}$ the energy-per-bit, $\mathcal{E}=E_b/N_0=\frac{nP}{\log_2 M}=\frac{\PT}{S}$. For finite $E_b/N_0$, we need finite $\PT$, hence we consider the power $P$ decaying as $O(1/n)$.

Let $\cd_j=\{c^j_1,...,c^j_M\}$ be the codebook of user $j$, of size $M$. The power constraint is given by ${\left\| c^j_i \right\|}^2\leq nP=\mathcal{E}\log_2 M,\forall j\in[K],i\in[M]$. The collection of codebooks $\{\cd_j\}$ is called an $\left(n,M,\epsilon,\mathcal{E},K\right)$–code if it satisfies the power constraint described before, and the per-user probability of error is smaller than $\epsilon$. Then, we can define the following fundamental limit for the channel

[LLL]{} \[eq:sc\_conv\_1\] \^\*(M,,)=\_[n]{} {:(n,M,,,K=n)-code}. 

We make an important remark here that all the following results also hold for maximal per-user error (PUPE-max) as discussed in appendix \[app:pupe-max\]. 

No-CSI
------

In this subsection, we focus on the no-CSI case.  The difficulty here is that, a priori, we do not know which subset of the users to decode.  We have the following theorem. 

\[th:scaling\_noCSI\] Consider the channel (no-CSI) with $K=\mu n$ where $\mu< 1$. Fix the spectral efficiency $S$ and target probability of error (per-user) $\epsilon$. Let $M=2^{S/\mu}$ denote the size of the codebooks and $\PT=KP$ be the total power.  Let $h(p)=-p\ln p-(1-p)\ln(1-p),p\in[0,1]$.Fix $\nu \in (1-\epsilon,1]$. Let $\epsilon'=\epsilon-(1-\nu)$. Then if $\mathcal{E}>\mathcal{E}^*_{no-CSI}=\sup_{\frac{\epsilon'}{\nu}< \theta\leq 1}\sup_{\xi\in[0,\nu(1-\theta)]}\frac{\PTX(\theta,\xi)}{S}$, there exists a sequence of $\left(n,M,\epsilon_n,\mathcal{E},K=\mu n\right)$ codes such that $\limsup_{n\to\infty} \epsilon_n\leq \epsilon$, where, for $\frac{\epsilon'}{\nu}< \theta\leq 1$ and $\xi\in[0,\nu(1-\theta)]$,

[RLL]{} (,)&=&\[eq:sc\_nc1a\]\
(,)&=&\[eq:sc\_nc1b\]\
f()&=& \[eq:sc\_nc1c\]\
V\_&=&e\^[-\_]{}\[eq:sc\_nc1d\]\
\_ &=&\^\*++\
&&h() +\
&&h()\[eq:sc\_nc1e\]\
\^\* &=&\[eq:sc\_nc1f\]\
c\_&=&\[eq:sc\_nc1g\]\
q\_&=&\[eq:sc\_nc1h\]\
\_1\^\*&=& q\_(1+c\_)+\
&& \[eq:sc\_nc1i\]\
\_2\^\* &=& {x: 0&lt;x&lt;1, -(1-x)-x&gt;}\[eq:sc\_nc1j\]\
(a,b)&=& a(a)-b(b)+b-a. \[eq:sc\_nc1k\]

Hence $\mathcal{E}^*\leq \mathcal{E}^*_{no-CSI}$.

CSIR
----

In this subsection, we focus on the CSIR scenario.  We could use projection decoding to decode a fraction of users where decoding set is a function of CSIR.  But a better bound is obtained by directly using euclidean metric to decode, similar to [@polyanskiy2017perspective].  Then have the following theorem. 

\[th:scaling\_CSIR\] Consider the channel (with CSIR) with $K=\mu n$ where $\mu<1$. Fix the spectral efficiency $S$ and target probability of error (per-user) $\epsilon$. Let $M=2^{S/\mu}$ denote the size of the codebooks and $\PT=KP$ be the total power.  Fix $\nu \in (1-\epsilon,1]$. Let $\epsilon'=\epsilon-(1-\nu)$. Then if $\mathcal{E}>\mathcal{E}^*_{CSIR}=\sup_{\frac{\epsilon'}{\nu}< \theta\leq 1}\inf_{0\leq \rho\leq 1}\frac{\PTX(\theta,\rho)}{S}$, there exists a sequence of $\left(n,M,\epsilon_n,\mathcal{E},K=\mu n\right)$ codes such that $\limsup_{n\to\infty} \epsilon_n\leq \epsilon$, where, for $\frac{\epsilon'}{\nu}< \theta\leq 1$,

[LLL]{} (,)\
= \[eq:sc\_csir1a\]\
(a,b) = a(a)-b(b)+b-a.\[eq:sc\_csir1b\]

Hence $\mathcal{E}^*\leq \mathcal{E}^*_{CSIR}$.

Converse
--------

Bounds tighter than can be obtained if further assumptions are made on the codebook.  For instance, if we assume that each codebook consists of iid entries of the form $\frac{C}{K}$ where $C$ is sampled from a distribution with zero mean and finite variance, then using ideas similar to [@reeves2013approximate Theorem 3] we have the following converse bound. 

\[Th:conv2\] Let $M$ be the codebook size, and let $\mu n$ users ($\mu<1$) generate their codebooks independently with each code symbol iid of the form $\frac{C}{K}$ where $C$ is of zero mean and variance $\PT$. Then in order for the iid codebook to achieve PUPE $\epsilon$ with high probability, the energy-per-bit $\mathcal{E}$ should satisfy

[LLL]{} \[eq:sc\_conv\_new1\]

where infimum is taken over all $\PT>0$ that satisfies

[LLL]{} \[eq:sc\_conv\_new2\] M - (M-1)-h()(M(,)-(,))

where $\mathcal{V}$ is given by [@reeves2013approximate]

[LLL]{} (r,)=r(1+-(r,))+(1+r-(r,))-\[eq:sc\_conv\_new3a\]\
(r,)=(-)\^2\[eq:sc\_conv\_new3b\]\

The proof is almost the same as in [@reeves2013approximate Theorem 3] (see [@reeves2013approximate Remark 3] as well).  We will highlight the major differences here.  First, our communication system can be modeled as a support recovery problem as follows.  Let $A$ be the $n\times KM$ matrix consisting of $n\times M$ blocks of codewords of users.  Let $\boldsymbol{H}$ be the $KM\times KM$ block diagonal matrix with block $i$ being a diagonal $M\times M$ matrix with all diagonal entries being equal to $H_i$. Finally let $W\in\{0,1\}^{KM}$ with $K$ blocks of size $M$ each and within each $M$ sized block, there is exactly one $1$. So the position of $1$ in block $i$ of $W$ denotes the message or codeword corresponding to the user $i$ which is the corresponding column in block $i$ of matrix $A$.  Hence our channel can be represented as $$\label{eq:sys_comp_sens}
Y=A\boldsymbol{H}W+Z$$ with the goal of recovering $W$.

Next the crucial step is bound $R^K (\epsilon,M)$ in as

[LLL]{} \[eq:sc\_conv\_new4\] R\^K(,M)I(W;Y|A)=I(W;Y|A)-I(W;Y|A,W)

where the equality in the above display follows from [@reeves2013approximate equation (78)].  The first term in above display is bounded as

[LLL]{} \[eq:sc\_conv\_new5\] I(W;Y|A=A\_1) =I(W;A\_1 HW+Z ) \_[U]{} I(U;A\_1 U+Z)

where $A_1$ is a realization of $A$ and supremum is over random vectors $U\in \mathbb{C}^{KM}$ such that ${\mathbb{E}\left[U \right]}=0$ and ${\mathbb{E}\left[UU^* \right]}={\mathbb{E}\left[(\boldsymbol{H}W)(\boldsymbol{H}W)^*  \right]}=\frac{{\mathbb{E}\left[|H_1|^2 \right]}}{M}I_{KM\times KM}$. Now similar to [@reeves2013approximate], the supremum is achieved when $U{\mathbin{\overset{}{\kern\z@\sim}}}\cn\left(0,\frac{{\mathbb{E}\left[|H_1|^2 \right]}}{M}I_{KM\times KM}\right)$. Hence

[LLL]{} \[eq:sc\_conv\_new6\] I(W;Y|A=A\_1)(I\_[nn]{}+AA\^\*). 

Next, for any realization $A_1$ and $W_1$ of $A$ and $W$ respectively, we have

[LLL]{} \[eq:sc\_conv\_new7\] I(W;Y|A=A\_1,W=W\_1)&=&I(W\_1;A\_1W\_1+Z)\
&=& I(;(A\_1)\_[W\_1]{}+Z)\
&& I(;+(A\_1)\_[W\_1]{}\^Z)

where $\tilde{\boldsymbol{H}}=[H_1,...,H_{K}]^T$ and $(A_1)_{W_1}$ is the $n\times K$ submatrix of $A_1$ formed by columns corresponding to the support of $W_1$ and $\dagger$ denotes the Moore-Penrose inverse (pseudoinverse).  The last equality in the above follows from the data processing inequality.  Now, by standard mutual information of Gaussians, we have

[LLL]{} \[eq:sc\_conv\_new7a\] I(;+(A\_1)\_[W\_1]{}\^Z)=(I\_[KK]{}+((A\_1)\_[W\_1]{})\^\*(A\_1)\_[W\_1]{}). 

Hence

[LLL]{} \[eq:sc\_conv\_new7b\] I(W;Y|A,W)= . 

Hereafter, the we can proceed similarly to the proof of [@reeves2013approximate Theorem 3] using results from random-matrix theory [@verdu1999spectral; @salo2006asymptotic] to finish the proof. 

We remark here that for a general fading distribution, the term $I(\tilde{\boldsymbol{H}};\tilde{\boldsymbol{H}}+(A_1)_{W_1}^{\dagger}Z)$ can be lower bounded similar to the proof of [@reeves2013approximate Theorem 3] using EPI (and its generalization [@zamir1993generalization]) to get

[LLL]{} \[eq:sc\_conv\_new8\] I(;+((A\_1)\_[W\_1]{})\^Z)K(1+N\_[H]{}((((A\_1)\_[W\_1]{})\^\*(A\_1)\_[W\_1]{}))\^)

where $N_H=\frac{1}{\pi e}\exp(h(H))$ is the entropy power of fading distribution.  Hence

[LLL]{} \[eq:sc\_conv\_new9\] I(W;Y|A,W)K.

Again, we can use results from random-matrix theory [@salo2006asymptotic] and proceed similarly to the proof of [@reeves2013approximate Theorem 3] to get a converse bound with the second term in replaced by $\mathcal{V}_{LB}\left(\frac{1}{\mu},\PT\right)$ and $$\label{eq:sc_conv_new10}
\mathcal{V}_{LB}(r,\gamma)=\ln\left(1+\gamma r \left(\frac{r}{r-1}\right)^{r-1}\frac{1}{e}\right)$$

We make a few observations regarding the preceding theorem.  First and foremost, this hold only for the case of no-CSI because the term analogous to $I(\boldsymbol{H}W;Y|A,W)$ in the case of CSIR is $ I(\boldsymbol{H}W;Y|A,\boldsymbol{H},W)$ which is zero.  Next, it assumes that the codebooks have iid entries with variance scaling $\Theta(1/n)$. This point is crucial to lower bounding $I(\boldsymbol{H}W;Y|A,W)$, and this is where a significant improvement comes when compared to .  Indeed, EPI and results from random matrix theory give $O(n)$ lower bound for $I(\boldsymbol{H}W;Y|A,W)$. This once again brings to focus the the difference between classical regime and the scaling regime, where in the former, this term is negligible.  Further this leaves open the question of whether we could improve performance in the high-density of users case by using non-iid codebooks. 

Now, as to what types of codebooks give a $\Theta(n)$ lower bound for $I(\boldsymbol{H}W;Y|A,W)$, a partial answer can be given by carefully analyzing the full proof of the theorem.  In particular, if $\mathcal{S}=\mathrm{supp}W$ i.e, the support of $W$, then as seen from [@reeves2013approximate equation (85)], any non zero lower bound on $\det(A_{\mathcal{S}}^{*}A_{\mathcal{S}})^{1/K}$ is enough.  So if the matrix $A_{\mathcal{S}}^{*}A_{\mathcal{S}}$ is strongly diagonally dominant or if there is a $O(n)$ constraint on $\operatorname{Tr}(A_{\mathcal{S}}^{*}A_{\mathcal{S}})^2 $ one can lower bound the determinant using Hadamard type lower bounds (see [@grone1984improving] for instance).  These boil down to the codewords being overwhelmingly close to orthogonal. 

Numerical evaluation and discussion {#sec:numerical}
===================================

**TODO:** Move all discussion and description of figures to here.  I mean the $K=\mu n$ discussion, not the classical MAC stuff. In this section, we provide the results of numerical evaluation of the bounds in the paper.  We focus on the trade-off of user density $\mu$ with the minimum energy-per-bit $\mathcal{E}^*$ for a given message size $k$ and target probability of error $P_e$.

For $k=100$ bits, we evaluate the trade-off from the bounds in this paper for $P_e=0.1$ and $P_e=0.001$ in figures \[fig:3\] and \[fig:4\] respectively.  For TDMA, we split the frame of length $n$ equally among $K$ users, and compute the smallest $P_{tot}$ the ensures the existence of a single user quasi-static AWGN code of rate $S$, blocklength $\frac{1}{\mu}$ and probability of error $\epsilon$ using the bound from [@yang2014quasi].  The simulations of the single user bound is performed using codes from [@Spectre].  TIN is computed using a method similar to theorem \[th:scaling\_CSIR\]. 

From these figures, we clearly observe the *perfect MUI cancellation* effect mentioned in the introduction.  As $\mu$ increases from $0$, the $\mathcal{E}^*$ is almost a constant (slightly increasing for the achievability bounds) but then undergoes a “phase transition” where $\mathcal{E}^*$ increases sharply.  Hence this suggests there is a certain $\mathcal{E}_{\mathrm{s.u.}}=\mate_{\mathrm{s.u.}}(k,\epsilon)$ and $\mu_{\mathrm{s.u.}}>0$ such that $\mathcal{E}^*=\mathcal{E}_{\mathrm{s.u.}}$ for all $\mu<\mu_{\mathrm{s.u.}}$. Further, standard schemes for multiple-access like TDMA and TIN do not have this behavior.  Moreover, although these suboptimal schemes have an optimal trade-off at $\mu\to 0$ they show a significant suboptimality at higher $\mu$. We note again that this perfect MUI cancellation which was observed in standard GMAC [@polyanskiy2017perspective; @polyanskiy2018_course] is also present in the more practically relevant quasi-static fading model.  So, we suspect that this effect is a characteristic of the many-user MAC. 

The fact that orthogonalization is not optimal is one of the key practical implications of our work.  It was observed before in the GMAC and here we again witness it in the more relevant QS-MAC.  How to understand this suboptimality?  First, in the fading case we have already seen this effect even in the classical regime (but under PUPE) – see .  To give another intuition we consider a $K=\mu n$ user binary adder MAC

$$\label{eq:adder_MAC}
Y=\sum_{i=1}^{K}X_i$$

where $X_i\in \{0,1\}$ and addition is over $\mathbb{Z}$. Now, using TDMA on this channel, each user can send at most $n/K=1/\mu$ bits.  Hence the message size is bounded by

$$\label{eq:msg_TDMA}
\log M\leq \frac{1}{\mu}.$$

Next, let us consider TIN.  Assume $X_i{\mathbin{\overset{}{\kern\z@\sim}}}\mathrm{Ber}(1/2)$. For user 1, we can treat $\sum_{i=2}^{\mu n}X_i$ as noise.  By central limit theorem, this noise can be approximated as $\sqrt{\frac{1}{4}\mu n}Z$ where $Z{\mathbin{\overset{}{\kern\z@\sim}}}N(0,1)$. Thus we have a binary input AWGN (BIAWGN) channel $$\label{eq:BIAWGN}
Y=X_1+\sqrt{\frac{1}{4}\mu n}Z.$$ Therefore, the message size is bounded as

[LLL]{} \[eq:msg\_TIN\] M &n C\_(1+)\
& (1+)

where $C_{\mathrm{BIAWGN}}$ is the capacity of the BIAWGN channel.  Note that in both the above schemes the achievable message size is a constant as $n\to\infty$.

On the other hand, the true sum-capacity of the $K$-user adder MAC is given by $$C_{sum} = \max_{X_1 , \cdots , X_K} H(X_1 + \cdots +X_K)\,.$$ As shown in [@shepp1981entropy] this maximum as achieved at $X_i \stackrel{iid}{\sim} \mathrm{Ber}(1/2)$. Since the the entropy of binomial distributions [@knessl1998integral] can be computed easily, we obtain $$C_{sum} = \frac{1}{2} \log K + o(\log K)\,.$$ In particular, for our many-user MAC setting we obtain from the Fano inequality (and assuming PUPE is small) $$\log M \lessapprox \frac{\log (\mu n)}{2\mu }\,.$$ Surprisingly, there exist explicit codes that achieve this limit and with a very low-complexity (each message bit is sent separately),– a construction rediscovered several times [@lindstrom1965combinatorial; @cantor1966determination; @khachatrian1995new].  Hence the optimal achievable message size is $$\label{eq:msg_lindstrom}
\log M \approx \frac{\log n}{2\mu}\to\infty$$ as $n\to\infty$. And again, we see that TDMA and TIN are severely suboptimal for the many-user adder MAC as well. 

We use the following two well known results. 

If $f:\mathbb{R}^n\to [0,\infty]$ is a measurable function (with borel measures) then $$\label{eq:4}
\int_{\mathbb{R}^n}f(x)dx=\int_{(0,\infty)\times S^{n-1}}f(r\omega)r^{n-1} dr d\sigma(\omega)$$ where $\sigma$ is the uniform surface measure on $S^{n-1}$.

If $f,g:\mathbb{R}^d\to \mathbb{R}$ such that $g$ is smooth and its gradient does not vanish then $$\label{eq:5}
\int_{\mathbb{R}^d}f(x)\delta(g(x))dx=\int_{g^{-1}(0)}\frac{f(u)}{\|\nabla g \|}d\sigma(u)$$ where $\sigma$ is the surface measure on $g^{-1}(0)$.

[^1]: This paper \[in part and compressed form\] is accepted to be published at IEEE International Symposium on Information Theory (ISIT) 2019 [@kowshik2019quasi]

[^2]: Parts of the results on classical regime in this paper (theorems \[th:cap\_joint\] \[th:pu1\]) have appeared in the one of the authors’ Masters thesis [@kowshik2018coding]

[^3]: In this paper we do not distinguish between TDMA, FDMA or any other orthogonalization strategy.  From here on, all orthogonalization strategies will be referred to as “TDMA”

[^4]: Note that pseudo-random CDMA systems without multi-user detection and large load factor provide an efficient implementation of TIN.  So throughout our discussions, conclusions about TIN also pertain to CDMA systems of this kind.