The LASSO Risk for Gaussian Matrices
The LASSO Risk for Gaussian Matrices
复制标题
DOI：
10.1109/tit.2011.2174612
复制
发表时间：
2012-04-01
影响因子：
2.5
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Bayati, Mohsen;Montanari, Andrea
我们认为学习系数矢量x（o）的问题是噪声线性观察y = ax（o） + w的r-n元素，是r-n的元素。在许多情况下（从模型选择到图像处理），希望在CAP上构造稀疏的估计器（X）。在这种情况下，一种流行的方法在于解决L（1）二次化最小二乘问题，称为Lasso或基础追踪Denoising。对于增加维度的矩阵序列a的序列a具有独立的高斯条目，我们证明了归一化的风险套索的收敛到极限，我们获得了此限制的明确表达式。我们的结果是，对于随机实例，套索的渐近平方误差的明确公式的第一个严格推导。证明技术基于对最近开发的有效算法AMP的分析，它灵感来自图形模型思想。对真实数据矩阵的构图表明，我们的结果可能与广泛的实用应用程序相关。
We consider the problem of learning a coefficient vector x(o) is an element of R-N from noisy linear observation y = Ax(o) + w is an element of R-n. In many contexts (ranging from model selection to image processing), it is desirable to construct a sparse estimator (x) over cap. In this case, a popular approach consists in solving an l(1)-penalized least-squares problem known as the LASSO or basis pursuit denoising.For sequences of matrices A of increasing dimensions, with independent Gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. Our result is the first rigorous derivation of an explicit formula for the asymptotic mean square error of the LASSO for random instances. The proof technique is based on the analysis of AMP, a recently developed efficient algorithm, that is inspired from graphical model ideas.Simulations on real data matrices suggest that our results can be relevant in a broad array of practical applications.