Chapter Summary

Chapter Summary

Key Points

• 1.

  Statistical and computational thresholds can differ. The information-theoretic sample complexity $\lambda_{\text{stat}}$ (Fano, matching MLE) is a lower bound on what any polynomial-time estimator can achieve. For sparse PCA, planted clique, and tensor PCA, a strict gap $\lambda_{\text{comp}} > \lambda_{\text{stat}}$ is either proven (under planted clique) or widely conjectured — extending the minimax story of Chapters 19 and 22.

• 2.

  Lasso is gap-free; sparse PCA is not. Moving from a linear observation model to a quadratic (covariance) one can convert a gap-free problem into a gap-full one. This is why $\ell_1$-based channel estimation (Chapter 15) works at the information-theoretic rate in practice, while spectral sparse-PCA recovery plateaus at the computational rate.

• 3.

  Regret is the right metric when the environment is changing. The multiplicative weights update achieves $R_T = \mathcal{O}(\sqrt{T\ln N})$ against the best fixed expert — a bound that is distribution-free and convex. Online convex optimization extends this to any convex loss and any convex decision set, making it the operational generalization of stochastic gradient descent for non-stationary wireless scenarios.

• 4.

  Bandits trade off exploration and exploitation. UCB1 achieves $\mathcal{O}(\sqrt{KT\log T})$ pseudo-regret on $K$-arm stochastic bandits — asymptotically optimal up to the log factor. In cell-edge beam management, Thompson sampling and UCB variants replace exhaustive sweeps and directly address the exploration–exploitation tension of 5G/6G codebook search.

• 5.

  Consensus on a graph converges at the spectral-gap rate. The averaging iteration $\mathbf{x}^{(t+1)} = \mathbf{W}\mathbf{x}^{(t)}$ converges if $\mathbf{W}$ is doubly stochastic with the all-ones eigenvalue simple, at geometric rate $|\lambda_2(\mathbf{W})|$. Metropolis–Hastings weights give an explicit optimal choice; randomized gossip attains the same rate asynchronously.

• 6.

  Distributed Kalman filtering reduces to consensus-plus-innovations. Each node computes a local innovation; a consensus step fuses the state estimates across neighbors. Cell-free massive MIMO uplink estimation is the canonical wireless instance: access points share channel estimates over a backhaul graph, each running a local LMMSE filter augmented with a consensus exchange.

• 7.

  Reading estimation papers is a meta-skill. Four questions decode any paper: signal model, criterion, benchmark, regime. The recurring pitfalls — CRB confused with achievable MSE, threshold-effect extrapolation, unmatched complexity, SNR definition drift, missing confidence bands — are the failure modes the reader should scan for on every pass.

• 8.

  The six-item simulation checklist is a scientific contract. A fair comparison fixes the SNR definition, matches the complexity budget, uses the strongest baseline available, reports Monte-Carlo counts and confidence bands, shares random realizations across methods, and tunes hyperparameters on a held-out set. Papers that fail any item should be read with skepticism — and papers that satisfy all six should be modeled.