2014/01/25 by Thrampoulidis, Christos, Oymak, Samet, Hassibi, Babak
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1401.6578
Consider estimating a structured signal x0 from linear, underdetermined and noisy measurements y=Ax0+z, via solving a variant of the lasso algorithm: x=argminx\ ‖y-Ax‖2+λf(x)\. Here, f is a convex function aiming to promote the structure of x0, say ℓ1-norm to promote sparsity or nuclear norm to promote low-rankness. We assume that the entries of A are independent and normally distributed and make no assumptions on the noise vector z, other than it being independent of A. Under this generic setup, we derive a general, non-asymptotic and rather tight upper bound on the ℓ2-norm of the estimation error ‖x-x0‖2. Our bound is geometric in nature and obeys a simple formula; the roles of λ, f and x0 are all captured by a single summary parameter δ(λ∂((f(x0))), termed the Gaussian squared distance to the scaled subdifferential. We connect our result to the literature and verify its validity through simulations.