Exercises

$M_{\text{LS}} \geq L = 64$ pilots.

$M_{\text{CS}} \approx 3 \times 4 \times \log_2(16) = 3 \times 4 \times 4 = 48$. With a tighter constant (e.g.\ 2) one gets $M \approx 32$.

CS saves roughly $25\text{-}50\%$ of pilots relative to LS for this channel.

$\log(1000/20) = \log(50) \approx 3.9$.

$M \sim 20 \times 3.9 \approx 78$ pilots (before SNR factor). With SNR penalty factor $\approx 3$ at low SNR, $M \approx 240$.

Group 1: $\sqrt{1^2+0^2}=1$. Group 2: $\sqrt{4+4}=2\sqrt{2}$. Group 3: $0$. Group 4: $\sqrt{1+1}=\sqrt{2}$.

$\|\mathbf{x}\|_{2,1} = 1 + 2\sqrt{2} + 0 + \sqrt{2} = 1 + 3\sqrt{2} \approx 5.24$.

MUSIC relies on the eigenstructure of the sample covariance; a single snapshot gives rank 1, so subspace separation fails. CS treats the snapshot as $N_a$ measurements of a $K$-sparse angular vector and recovers the DOAs directly without covariance estimation.

$\nabla_{\mathbf{x}_g} \|\mathbf{x}_g\|_2 = \mathbf{x}_g/\|\mathbf{x}_g\|_2$ for $\mathbf{x}_g \neq \mathbf{0}$; at $\mathbf{x}_g = \mathbf{0}$ the subdifferential is the unit ball $\{\mathbf{v} : \|\mathbf{v}\|_2 \leq 1\}$.

$\text{prox}_{\lambda\|\cdot\|_2}(\mathbf{z}_g) = (1 - \lambda/\|\mathbf{z}_g\|_2)_+ \, \mathbf{z}_g$ — group soft-thresholding: shrink the whole group toward zero if $\|\mathbf{z}_g\|_2 \leq \lambda$, otherwise scale by $(1 - \lambda/\|\mathbf{z}_g\|_2)$.

Plain $\ell_1$: supports of size $KB$ among $GB$ entries, so $\log \binom{GB}{KB} \approx KB \log(G/K)$ when $B \ll G$. Group LASSO: $K$ groups out of $G$: $\log\binom{G}{K} \approx K\log(G/K)$ plus $KB$ bits per coefficient. Hierarchical: $K$ groups plus $s$ per group: $K\log(G/K) + Ks\log(B/s) + Ks$.

Plain $\ell_1 \gtrsim KB\log(G/K)$. Group $\gtrsim K\log(G/K) + KB$. Hierarchical $\gtrsim K\log(G/K) + Ks\log(B/s) + Ks$. Hierarchical is best when $s \ll B$, saving a factor $\approx B/s$ over group.

$i^\star = \arg\max_i |\boldsymbol{\phi}_i^H \mathbf{r}^{(k-1)}|$; $\mathcal{S}^{(k)} = \mathcal{S}^{(k-1)} \cup \{i^\star\}$.

$\hat{\mathbf{h}}_{\mathcal{S}^{(k)}} = (\boldsymbol{\Phi}_{\mathcal{S}^{(k)}}^H \boldsymbol{\Phi}_{\mathcal{S}^{(k)}})^{-1} \boldsymbol{\Phi}_{\mathcal{S}^{(k)}}^H \mathbf{y}$.

$\mathbf{r}^{(k)} = \mathbf{y} - \boldsymbol{\Phi}_{\mathcal{S}^{(k)}} \hat{\mathbf{h}}_{\mathcal{S}^{(k)}}$. By construction $\mathbf{r}^{(k)} \perp \boldsymbol{\phi}_i$ for all $i \in \mathcal{S}^{(k)}$ — orthogonality is the "O" in OMP.

$|\mathbf{a}(\theta)^H \mathbf{a}(\theta_0)|^2 = |\sum_{n=0}^{N_a-1} e^{j\pi n (\sin\theta - \sin\theta_0)}|^2 = \frac{\sin^2(N_a \pi \Delta/2)}{\sin^2(\pi \Delta/2)}$, where $\Delta = \sin\theta - \sin\theta_0$.

First null at $\Delta = 2/N_a$, so mainlobe width in $\sin\theta$ is $2/N_a = 0.25$.

Near $\theta_0 = 30^\circ$, $d\sin\theta/d\theta = \cos 30^\circ \approx 0.866$. $\Delta\theta \approx 0.25/0.866 \approx 0.289$ rad $\approx 16.5^\circ$.

For each fixed block support, a Gaussian matrix acts as a near-isometry on the $KB$-dim subspace with probability $1 - 2e^{-c\delta^2 M}$ provided $M \geq c_0 KB/\delta^2$.

There are $\binom{G}{K} \leq (eG/K)^K$ block supports. Union bound requires $M \geq c_0 (KB + K\log(G/K))/\delta^2$ for simultaneous isometry.

Compared to plain $s\log(N/s) = KB\log(G/K) + KB\log B$, block-RIP saves a factor $\log B$ — the benefit of grouped structure.

Each chunk of $B/L$ bits indexes a $2^{B/L}$-sized sub-dictionary. Parallel CS recovery is run independently in each of the $L$ slots.

LASSO / AMP recovery is $O(M \cdot 2^{B/L})$ per slot, total $O(L M \cdot 2^{B/L})$ — exponentially faster than a single $O(M \cdot 2^B)$ recovery when $L \geq 2$.

The outer tree code requires extra parity and an $O(K_a^2)$-level belief-propagation stitcher. The tradeoff: polynomial overhead in $K_a$, exponential saving in $B$.

For each source angle $\theta_k$ we need a polynomial $q(\theta)$ with $|q(\theta)| \leq 1$ everywhere and $q(\theta_k) = \text{sign}(c_k)$. Candès and Fernandez-Granda (2014) constructed such a polynomial as a bump-function around each $\theta_k$ with controlled derivative bounds.

For the construction to satisfy $|q| \leq 1$ strictly off-support, neighbouring bumps must not overlap, which requires $|\sin\theta_i - \sin\theta_j| \geq c/N_a$.

KKT conditions with this dual certificate imply the atomic-norm primal has the $K$-sparse representation at $\{\theta_k\}$ as its unique optimum. $\blacksquare$

If $\boldsymbol{\Sigma}_y = \boldsymbol{\Sigma}_{-k} + \gamma_k \boldsymbol{\phi}_k \boldsymbol{\phi}_k^H$, then $\boldsymbol{\Sigma}_y^{-1} = \boldsymbol{\Sigma}_{-k}^{-1} - \frac{\gamma_k \boldsymbol{\Sigma}_{-k}^{-1}\boldsymbol{\phi}_k \boldsymbol{\phi}_k^H \boldsymbol{\Sigma}_{-k}^{-1}}{1 + \gamma_k \boldsymbol{\phi}_k^H \boldsymbol{\Sigma}_{-k}^{-1}\boldsymbol{\phi}_k}$.

Substituting into $\mathcal{L}$ yields $f(\gamma_k) = \log(1 + \gamma_k u_k) - \gamma_k v_k/(1+\gamma_k u_k) + \text{const}$, with $u_k = \boldsymbol{\phi}_k^H\boldsymbol{\Sigma}_{-k}^{-1}\boldsymbol{\phi}_k$, $v_k = \boldsymbol{\phi}_k^H\boldsymbol{\Sigma}_{-k}^{-1}\widehat{\boldsymbol{\Sigma}}_y\boldsymbol{\Sigma}_{-k}^{-1}\boldsymbol{\phi}_k$.

$f''(\gamma_k) > 0$ for $\gamma_k \geq 0$; the minimizer is $\gamma_k^\star = \max(0, (v_k - u_k)/u_k^2)$. Iterate coordinate-by-coordinate until convergence. This is the Fengler-Haghighatshoar-Jung-Caire algorithm.

$\mathbf{h}(f) = \sum_\ell \alpha_\ell e^{-j2\pi f \tau_\ell} \mathbf{a}(\theta_\ell)$. The angles $\theta_\ell$ are frequency-agnostic (geometry); only the complex gains differ between UL and DL.

Estimate UL support $\{\theta_\ell\}$ via CS on uplink pilots. DL channel estimation then reduces to estimating $L$ complex gains — a problem of dimension $L$, not $G$.

DL pilots needed: $M_{\text{DL}} \sim L$ (gain estimation) rather than $L\log(G/L)$ (support + gains). For massive MIMO with $G = 256$ angular bins and $L \approx 5$ paths, this reduces DL pilot overhead by $\approx \log 50 \approx 6\times$.

$\hat{\mathbf{x}} = \arg\min \|\mathbf{x} - \mathbf{z}\|_2^2$ subject to $\mathbf{x}$ supported on $\leq K$ groups, each with $\leq s$ nonzero entries.

Fix active-group set $\mathcal{G}$. Inside group $g$, best $s$-sparse approximation of $\mathbf{z}_g$ is its top-$s$ coordinates. In-group error: $\sum_{i \notin \text{top-}s(g)} |z_{g,i}|^2$.

Error as a function of $\mathcal{G}$: $\sum_{g \notin \mathcal{G}} \|\mathbf{z}_g\|_2^2 + \sum_{g \in \mathcal{G}} \sum_{i\notin\text{top-}s(g)} |z_{g,i}|^2$. Minimised by picking the $K$ groups maximising $\|\mathbf{z}_g\|_2^2 - \sum_{i\notin\text{top-}s(g)} |z_{g,i}|^2 = \text{top-}s\text{-energy of } g$.

Thus the two-level procedure — inner top-$s$, outer top-$K$ by in-group energy — is jointly optimal. $\blacksquare$

The Gaussian width of the $K$-sparse unit ball in $\mathbb{C}^G$ is $\omega_K \asymp \sqrt{K \log(G/K)}$.

When angles are separated by $\gtrsim 1/N_a$, columns of $\mathbf{A}$ have mutual coherence $\mu \lesssim 1/\sqrt{N_a}$, enabling RIP-like concentration.

Candès-Plan's matrix-from-random-samples result gives $N_a \geq c \omega_K^2 = c K \log(G/K)$ for successful $\ell_1$ recovery. $\blacksquare$

Polyanskiy (2017) derives the achievable finite-blocklength $E_b/N_0$ bound via a converse on typical-set decoding of an i.i.d.\ MAC with $K_a$ active users. As $n\to\infty$ with $K_a/n$ fixed, the bound converges to a constant depending on the per-user error target.

Coded CS uses i.i.d.\ Gaussian codebooks and AMP-based decoding (Amalladinne et al.), which in the large-system limit achieves the i.i.d.-Gaussian-input MAC capacity via state evolution. Thus coded CS matches Polyanskiy's bound to within the AMP-MMSE gap.

Closing the small residual gap to Polyanskiy's bound is an open research direction; current best approaches combine HiHTP with outer LDPC codes.

$\mathbf{y} = \sum_k \boldsymbol{\phi}_k h_k x_k + \mathbf{w}$ where each active user contributes a pilot-channel-data product. This is a bilinear sparse-recovery problem.

Without constraints, $(h_k, x_k)$ is determined only up to a complex scalar per user. Identifiability is restored by (a) known pilot symbols, (b) finite alphabets, or (c) multiple receive antennas (MMV structure).

Expectation-maximization, bilinear AMP (BiG-AMP), and Caire's joint AD-and-decoding framework combine CS recovery with data-symbol constellation constraints.

With $K=1$, outer-group selection is trivial; HiHTP picks the single group $g$ with the largest in-group top-$s$ energy. Inside that group, HiHTP reduces to HTP.

HTP on a $B$-dimensional ambient space with $s$-sparse signal needs $M \gtrsim s\log(B/s)$ by Foucart's analysis.

Plain CS on the full ambient $GB$-space needs $M \gtrsim s\log(GB/s)$. HiHTP exploits the known outer-group support to remove the $\log G$ factor — a pure structural gain. $\blacksquare$

$\widehat{\boldsymbol{\Sigma}}_y = \frac{1}{N_r}\mathbf{Y}\mathbf{Y}^H \to \mathbf{E}\boldsymbol{\Sigma}_y$ almost surely as $N_r \to \infty$ (assuming ergodic LSFC).

The ML objective $\log\det + \mathrm{tr}(\cdot)$ becomes deterministic; at $\widehat{\boldsymbol{\Sigma}}_y = \boldsymbol{\Sigma}_y$ its minimum is attained at the true LSFC vector $\boldsymbol{\gamma}^\star$.

Even for $K_a > M$, the Fisher information of $\boldsymbol{\gamma}$ via the $M^2$ covariance entries remains non-singular in generic pilot books — this is why the covariance detector breaks the $M$ barrier. This is the core CommIT result.

The atomic norm is the support function of the polar $\mathcal{A}^\circ$, so $\|\mathbf{u}\|_\mathcal{A} = \sup_{\mathbf{q} \in \mathcal{A}^\circ} \Re\langle\mathbf{q},\mathbf{u}\rangle$. Plugging in and noting $\mathcal{A}^\circ = \{\mathbf{q} : |\mathbf{q}^H\mathbf{a}(\theta)| \leq 1\ \forall\theta\}$ yields the dual.

$q(\theta) = \mathbf{q}^H \mathbf{a}(\theta)$ is a trigonometric polynomial of degree $N_a - 1$. The constraint $|q(\theta)| \leq 1$ for all $\theta$ is the bounded-real lemma LMI.

The optimal $q(\theta)$ touches $\pm 1$ precisely at the true source angles; these are the active contact points that certify primal optimality. Reading off the touch points gives the DOA estimates.