##
**LASSO risk and phase transition under dependence.**
*(English)*
Zbl 07633944

Summary: We consider the problem of recovering a \(k\)-sparse signal \(\beta_0\in \mathbb{R}^p\) from noisy observations \(\mathbf{y}=\mathbf{X}\beta_0+\mathbf{w} \in \mathbb{R}^n\). One of the most popular approaches is the \(l_1 \)-regularized least squares, also known as LASSO. We analyze the mean square error of LASSO in the case of random designs in which each row of \(\mathbf{X}\) is drawn from distribution \(N(0, \Sigma)\) with general \(\Sigma\). We first derive the asymptotic risk of LASSO for \(\mathbf{w}\neq 0\) in the limit of \(n, p\to \infty\) with \(n/ p\to \delta \in [0,\infty)\). We then examine conditions on \(n, p\), and \(k\) for LASSO to exactly reconstruct \(\beta_0\) in the noiseless case \(\mathbf{w}=0\). A phase boundary \(\delta_c=\delta (\epsilon)\) is precisely established in the phase space defined by \(0\leq \delta, \epsilon \leq 1\), where \(\epsilon =k/p\). Above this boundary, LASSO perfectly recovers \(\beta_0\) with high probability. Below this boundary, LASSO fails to recover \(\beta_0\) with high probability. While the values of the non-zero elements of \(\beta_0\) do not have any effect on the phase transition curve, our analysis shows that \(\delta_c\) does depend on the signed pattern of the nonzero values of \(\beta_0\) for general \(\Sigma \neq \mathbf{I}_{p\times p}\). This is in sharp contrast to the previous phase transition results derived in i.i.d. case with \(\Sigma = \mathbf{I}_{p\times p}\) where \(\delta_c\) is completely determined by \(\varepsilon\) regardless of the distribution of \(\beta_0\). Underlying our formalism is a recently developed efficient algorithm called approximate message passing (AMP) algorithm. We generalize the state evolution of AMP from i.i.d. case to general case with \(\Sigma \neq \mathbf{I}_{p\times p}\). Extensive computational experiments confirm that our theoretical predictions are consistent with simulation results on moderate size system.

### MSC:

62F12 | Asymptotic properties of parametric estimators |

### References:

[1] | Baddeley, A. (1977). Integrals on a moving manifold and geometrical probability. Advances in Applied Probability 9(3), 588-603. · Zbl 0377.60013 |

[2] | Barbier, J., F. Krzakala, N. Macris, L. Miolane, and L. Zdeborová (2019). Optimal errors and phase transitions in high-dimensional generalized linear models. Proceedings of the National Academy of Sciences 116(12), 5451-5460. · Zbl 1416.62421 |

[3] | Barbier, J. and N. Macris (2019, Aug). The adaptive interpolation method: a simple scheme to prove replica formulas in bayesian inference. Probability Theory and Related Fields 174(3), 1133-1185. · Zbl 1478.60253 |

[4] | Bayati, M., M. Lelarge, and A. Montanari (2015, 04). Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25(2), 753-822. · Zbl 1322.60207 |

[5] | Bayati, M. and A. Montanari (2011, Feb). The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory 57(2), 764-785. · Zbl 1366.94079 |

[6] | Bayati, M. and A. Montanari (2012). The lasso risk for gaussian matrices. IEEE Trans. Information Theory 58(4), 1997-2017. · Zbl 1365.62196 |

[7] | Berthier, R., A. Montanari, and P.-M. Nguyen (2019, 01). State evolution for approximate message passing with non-separable functions. Information and Inference: A Journal of the IMA 00, 1-47. |

[8] | Blanchard, J. D., C. Cartis, and J. Tanner (2011). Compressed sensing: How sharp is the restricted isometry property? SIAM Review 53(1), 105-125. · Zbl 1214.41008 |

[9] | Celentano, M., A. Montanari, and Y. Wei (2020). The lasso with general gaussian designs with applications to hypothesis testing. |

[10] | Donoho, D. and J. Tanner (2009). Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 367(1906), 4273-4293. · Zbl 1185.94029 |

[11] | Donoho, D. L., I. Johnstone, and A. Montanari (2013, June). Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising. IEEE Trans. Inf. Theor. 59(6), 3396-3433. · Zbl 1364.94092 |

[12] | Donoho, D. L., A. Maleki, and A. Montanari (2009). Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences 106(45), 18914-18919. |

[13] | Donoho, D. L., A. Maleki, and A. Montanari (2011, Oct). The noise-sensitivity phase transition in compressed sensing. IEEE Transactions on Information Theory 57(10), 6920-6941. · Zbl 1365.94094 |

[14] | Donoho, D. L. and J. Tanner (2005). Sparse nonnegative solution of underdetermined linear equations by linear programming. Proceedings of the National Academy of Sciences 102(27), 9446-9451. · Zbl 1135.90368 |

[15] | Edelman, A. (1988). Eigenvalues and condition numbers of random matrices. SIAM Journal on Matrix Analysis and Applications 9(4), 543-560. · Zbl 0678.15019 |

[16] | Guo, D., D. Baron, and S. Shamai (2009, Sep.). A single-letter characterization of optimal noisy compressed sensing. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 52-59. |

[17] | Javanmard, A. and A. Montanari (2013). State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: A Journal of the IMA 2(2), 115-144. · Zbl 1335.94015 |

[18] | Javanmard, A. and A. Montanari (2014, Oct). Hypothesis testing in high-dimensional regression under the gaussian random design model: Asymptotic theory. IEEE Transactions on Information Theory 60(10), 6522-6554. · Zbl 1360.62074 |

[19] | Kabashima, Y., T. Wadayama, and T. Tanaka (2009). A typical reconstruction limit of compressed sensing based on Lp-norm minimization. Journal of Statistical Mechanics Theory and Experiment, L09003. |

[20] | Krzakala, F., M. Mézard, F. Sausset, Y. F. Sun, and L. Zdeborová (2012, May). Statistical-physics-based reconstruction in compressed sensing. Phys. Rev. X 2, 021005. |

[21] | Maleki, A., L. Anitori, Z. Yang, and R. G. Baraniuk (2013, July). Asymptotic analysis of complex lasso via complex approximate message passing (camp). IEEE Transactions on Information Theory 59(7), 4290-4308. · Zbl 1364.62188 |

[22] | Mezard, M. and A. Montanari (2009). Information, Physics, and Computation. New York, NY, USA: Oxford University Press, Inc. · Zbl 1163.94001 |

[23] | Rangan, S. (2011, July). Generalized approximate message passing for estimation with random linear mixing. In 2011 IEEE International Symposium on Information Theory Proceedings, pp. 2168-2172. |

[24] | Rangan, S., V. Goyal, and A. K. Fletcher (2009). Asymptotic analysis of map estimation via the replica method and compressed sensing. In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (Eds.), Advances in Neural Information Processing Systems 22, pp. 1545-1553. Curran Associates, Inc. |

[25] | Reeves, G. and H. D. Pfister (2016). The replica-symmetric prediction for compressed sensing with gaussian matrices is exact. In 2016 IEEE International Symposium on Information Theory (ISIT), pp. 665-669. |

[26] | Vershynin, R. (2011). Introduction to the non-asymptotic analysis of random matrices. · Zbl 1235.60009 |

[27] | Wainwright, M. J. (2009, May). Sharp thresholds for high-dimensional and noisy sparsity recovery using \[{\ell_1}\] -constrained quadratic programming (lasso). IEEE Transactions on Information Theory 55(5), 2183-2202. · Zbl 1367.62220 |

[28] | Weng, H., A. Maleki, and L. Zheng (2018, 12). Overcoming the limitations of phase transition by higher order analysis of regularization techniques. Ann. Statist. 46(6A), 3099-3129. · Zbl 1411.62194 |

[29] | Whittaker, E. T. and G. N. Watson (1996). A Course of Modern Analysis (4 ed.). Cambridge Mathematical Library. Cambridge University Press. |

[30] | Zheng, L., A. Maleki, H. Weng, X. Wang, and T. Long (2017, Nov). Does \[{\ell_p}\] -minimization outperform \[{\ell_1}\] -minimization? IEEE Transactions on Information Theory 63(11), 6896-6935. · Zbl 1390.94511 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.