Primal-Dual Witness Method and Sharp Thresholds for High-Dimensional Noisy Lasso Sparsity Recovery

⚠️ Curated Limitations & Negative Results

• Mutual Incoherence and Minimum Signal Magnitude Conditions: Theorem 1 requires the population covariance Sigma to satisfy the l_infinity mutual incoherence condition ||Sigma_{S^c S} (Sigma_{SS})^{-1}||_infty <= 1 - epsilon for epsilon in (0, 1] (Equation 18) and the minimum active-set magnitude rho_n := min_{i in S} |beta*_i| to dominate lambda_n + sqrt((log s)/n) (Equation 21); when mutual incoherence fails, exact signed support recovery via the Lasso is not guaranteed even when Restricted Eigenvalue conditions permit l_2 estimation.
• Threshold Gap for Non-Uniform Correlated Ensembles: While theta_l = theta_u = 1 yields a single sharp threshold for the isotropic Gaussian ensemble Sigma = I_p, for correlated Gaussian ensembles with C_max > 1 or epsilon < 1 (such as Toeplitz ensembles in Section 4, pp. 16-17, where theta_l < 1 < theta_u), Theorem 1 provides separate necessary (theta_l) and sufficient (theta_u) threshold constants.
• Primary-Source Typographical Notes in Wainwright (2009, arXiv:math/0605740v1): Verified six self-correcting typographical details during full-text inspection and numerical verification: (1) Section 2.1 (p. 4, Lemma 1, Equation 9b) writes |beta*_S + U_S| > 0 (and Appendix A, p. 18, line 8 writes beta_hat_S != 0) whereas exact signed support recovery sgn(beta_hat_S) = sgn(beta*_S) requires sgn(beta*_S + U_S) = sgn(beta*_S) (secured by the sufficient condition M(U) = {max_{i in S} |U_i| <= rho_n} in Equation 12 when strict inequality holds) and Appendix A (p. 18, line 13) drops the minus sign when writing lambda z_hat_{S^c} = X_{S^c}^T X_S (X_S^T X_S)^{-1}[(1/n) X_S^T w - lambda sgn(beta*_S)] - (1/n) X_{S^c}^T w = -V_{S^c} (whereas line 10 has -lambda z_hat_{S^c} on the RHS so +lambda z_hat_{S^c} = +V_{S^c}); (2) Section 2.3 (p. 6, last display) prints a stray token '|;' before -(1 - epsilon) + (1/lambda_n) min_j V_tilde_j; (3) Section 3.2.1 (p. 10) writes 'satisfying the conditions of Theorem 1(a)' in Corollary 1(b) instead of Theorem 1(b), and writes 's = O((log p)/p), as in Corollary 1' in the paragraph after Corollary 2, inverting s = O(p / log p); (4) Section 3.3.2 (p. 14, displays 2-4) writes 2 D_max lambda_n n / (n - s - 1) in place of mu*_i = 6 D_max lambda_n n / (n - s - 1), and Section 3.4 (p. 14, display 5) omits the tilde on V_tilde_j in the second line; (5) Appendix D.2 (p. 21, bottom line) writes 'as (n - s) -> 0' instead of (n - s) -> +infty, and Appendix D.5 (p. 23, line 13) defines B_i = e_i^T (Sigma_{SS})^{-1} b instead of B_i = (b^T (Sigma_{SS})^{-1} b)(e_i^T (Sigma_{SS})^{-1} e_i) while p. 24 writes (n - s)(n - s - 3) / n^2 in place of (n - s)(n - s - 3) / (n - s - 1)^2 in var(Y'_i); and (6) Appendix D.6 (p. 25, line 11) writes Sigma_{(S^c | S)} = [Sigma^{-1}]_{S^c S^c} omitting the outer inverse ([Sigma^{-1}]_{S^c S^c})^{-1} (though the eigenvalue lower bound Lambda_min(Sigma_{(S^c | S)}) >= 1/C_max still holds since Lambda_min(Sigma_{(S^c | S)}) >= Lambda_min(Sigma) = C_min >= 1/C_max for unit-diagonal Sigma).
• All 29 pages of Wainwright (2009, IEEE Trans. Inf. Theory 55(5):2183-2202, arXiv:math/0605740v1) were read. Constructed numerical checks in research/discovery/sharp-thresholds-high-dimensional-noisy-lasso-sparsity-recovery-boundaries.py verify (1) exact KKT primal-dual witness stationarity (residual 1.53e-16) and signed support recovery under M(V) and M(U); (2) exact collapse theta_l = theta_u = 1 for the standard Gaussian ensemble and 0 < theta_l < 1 < theta_u for the Toeplitz ensemble with rho = 0.10; and (3) idempotency and trace n - s of the projection R, asymptotic decay of the inverse-Wishart relative variance H_2 / (E[M_n])^2, and the exact Schur complement block-inverse identity (error 2.22e-16).