The squared-error of generalized LASSO: A precise analysis
Authors:
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1002-1009
Abstract
We consider the problem of estimating an unknown but structured signal x 0 from its noisy linear observations y = Ax 0 + z ∈ ℝ m . To the structure of x 0 is associated a structure inducing convex function f(·). We assume that the entries of A are i.i.d. standard normal N(0, 1) and z ~ N(0, σ 2 I m ). As a measure of performance of an estimate x* of x 0 we consider the “Normalized Square Error” (NSE) ∥x* - x 0 ∥ 2 2 /σ 2 . For sufficiently small σ, we characterize the exact performance of two different versions of the well known LASSO algorithm. The first estimator is obtained by solving the problem argmin x ∥y - Ax∥ 2 + λf(x). As a function of λ, we identify three distinct regions of operation. Out of them, we argue that “R ON ” is the most interesting one. When λ ∈ R ON , we show that the NSE is D f (x 0 , λ)/m-D f (x 0 , λ) for small σ, where D f (x 0 , λ) is the expected squared-distance of an i.i.d. standard normal vector to the dilated subdifferential λ · ∂f(x 0 ). Secondly, we consider the more popular estimator argmin x 1/2∥y - Ax∥ 2 2 . + στ f(x). We propose a formula for the NSE of this estimator by establishing a suitable mapping between this and the previous estimator over the region R ON . As a useful side result, we find explicit formulae for the optimal estimation performance and the optimal penalty parameters λ* and τ*.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- The squared-error of generalized LASSO: A precise analysis2013
- The LASSO Risk for Gaussian MatricesIEEE Transactions on Information Theory, 2011
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completionThe Annals of Statistics, 2011
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed SensingIEEE Transactions on Information Theory, 2011
- Matrix Completion With NoiseProceedings of the IEEE, 2010
- Block-Sparse Signals: Uncertainty Relations and Efficient RecoveryIEEE Transactions on Signal Processing, 2010
- The Dantzig selector: Statistical estimation when p is much larger than nThe Annals of Statistics, 2007
- High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to DimensionDiscrete & Computational Geometry, 2005
- Applications of second-order cone programmingLinear Algebra and its Applications, 1998
- On Milman's inequality and random subspaces which escape through a mesh in ℝ n1988