2013/11/04 by Oymak, Samet, Thrampoulidis, Christos, Hassibi, Babak · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1311.0830
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 (‖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 σ→ 0 and concentrates around (D(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 (D(λ))/(m-D(λ)). We then establish a mapping between this and the third estimator argminx\(1)/(2)‖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.