The Squared-Error of Generalized LASSO: A Precise Analysis

We consider the problem of estimating an unknown signal x0 from noisy linear observations y = Ax0 + z∈ Rm. In many practical instances, x0 has a certain structure that can be captured by a structure inducing convex function f(·). For example, ℓ1 norm can be used to encourage a sparse solution. To estimate x0 with the aid of f(·), we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix A and the noise vector z have zero-mean normal distributions with variances 1 and σ2 respectively. For the LASSO estimator x^*, we attempt to calculate the Normalized Square Error (NSE) defined as frac|x^*-x0|22σ2 as a function of the noise level σ, the number of observations m and the structure of the signal. We show that, the structure of the signal x0 and choice of the function f(·) enter the error formulae through the summary parameters D(cone) and D(λ), which are defined as the Gaussian squared-distances to the subdifferential cone and to the λ-scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of f(x0) and is given by argminx|y-Ax|2~subject to~f(x)≤ f(x0). We prove that its worst case NSE is achieved when σrightarrow 0 and concentrates around fracD(cone)m-D(cone). Secondly, we consider argminx|y-Ax|2+λ f(x), for some λ≥ 0. This time the NSE formula depends on the choice of λ and is given by fracD(λ)m-D(λ). We then establish a mapping between this and the third estimator argminxfrac12|y-Ax|22+ λ f(x). Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE.