Information-Theoretic Limits of High-Dimensional Noisy Sparsity Recovery

⚠️ Curated Limitations & Negative Results

• Computational Intractability of the Optimal Projection Decoder: Achieving the sufficient sample complexity of Theorem 1 via phi_opt(Y) = argmin_{|U|=s} ||Pi_U^perp Y||_2^2 requires evaluating all binom(p, s) candidate supports of size s (Section 1.2, p. 4; Section 2.2, p. 6), which is computationally intractable for large (p, s).
• Standard Gaussian Design and Exact 0-1 Support-Recovery Loss Scope: Theorems 1 and 2 assume i.i.d. standard Gaussian measurement matrices X_{ij} ~ N(0, 1), known support size s = |S|, and exact 0-1 support recovery rho(beta_hat, beta*) rather than partial support recovery or l_2 estimation loss.
• Primary-Source Typographical Notes in Wainwright (2009, arXiv:math/0702301v2): Verified four self-correcting typographical details during full-text inspection and numerical verification: (1) Section 2.2 (p. 6, Equation 9) writes f(U; Y, X, beta*) = argmin_{beta_U} {||Y - X_U beta_U||_2^2} using argmin_{beta_U} instead of min_{beta_U} for the scalar minimum residual squared norm f(U) = ||Pi_U^perp Y||_2^2 (confirmed in Appendix A, p. 13, where beta_hat_U = [X_U^T X_U]^{-1} X_U^T Y and f(U) = ||Y - X_U beta_hat_U||_2^2 = ||Pi_U^perp Y||_2^2); (2) Section 2.2 (p. 7, Proof of Lemma 2, line 4) contains a duplicated word 'with with' and writes 'mean vector W' for the rescaled vector ||beta*_{S \ U}||_2^{-1}(X_{S \ U} beta*_{S \ U} + W), whose conditional mean given W is ||beta*_{S \ U}||_2^{-1} W (matching nu = ||beta*_{S \ U}||_2^{-2} ||Pi_U^perp W||_2^2 two lines below); (3) Section 2.2 (p. 8, bottom display) writes ||Pi_U^perp W||_2^2 - ||Pi_S^perp W||_2^2 = ||Pi_U W||_2^2 - ||Pi_S W||_2^2 (since Pi_U^perp = I - Pi_U, ||Pi_U^perp W||_2^2 - ||Pi_S^perp W||_2^2 = ||Pi_S W||_2^2 - ||Pi_U W||_2^2, which has the same symmetric difference-of-chi_k^2 distribution); and (4) Section 2.3 (p. 11, bottom display, vs. p. 12, Equation 30) includes the factor 1/2 from D(P_i || P_j) = (1/2) Z_{U,V} on p. 11, so substituting Z <= 4 M^2(beta*) s n yields 2 M^2(beta*) s n / log[N - 1] (written 4 M^2(beta*) s n / log[N - 1] in Equation 30 on p. 12).
• All 16 pages of Wainwright (2009, IEEE Trans. Inf. Theory 55(12):5728-5741, arXiv:math/0702301v2) were read. Constructed numerical checks in research/discovery/information-theoretic-limits-high-dimensional-noisy-sparsity-recovery-boundaries.py verify (1) exact equality between ordinary-least-squares minimum residual squared norm f(U), orthogonal projection norm ||Pi_U^perp Y||_2^2, and Lemma 1 test statistic Delta(U), as well as the orthogonal-projection difference sign identity; (2) Birge's non-central chi-squared Chernoff exponent lower bound on the conditioning event A and the exact Vandermonde overlap sum sum_{k=1}^s binom(s, k) binom(p - s, k) = binom(p, s) - 1; and (3) expected conditional KL divergence n M^2(beta*)(s - |U cap V|) <= n s M^2(beta*) and the diverging sample complexity ratio n_Lasso / n_IT in the linear sparsity regime s = alpha p.