Estimating structured signals in sparse noise: A precise noise sensitivity analysis

We consider the problem of estimating a structured signal x_0 from linear, underdetermined and noisy measurements y = Ax_0 + z, in the presence of sparse noise z. A natural approach to recovering x_0, that takes advantage of both the structure of xo and the sparsity of z is solving: x = arg min_x ||y − Ax||1 subject to f(x) ≤ f(x_0) (constrained LAD estimator). Here, f is a convex function aiming to promote the structure of x_0, say ℓ_1-norm to promote sparsity or nuclear norm to promote low-rankness. We assume that the entries of A and the non-zero entries of z are i.i.d normal with variances 1 and σ^2, respectively. Our analysis precisely characterizes the asymptotic noise sensitivity ||x – x_0||^2_2/σ^2 in the limit σ^2 → 0. We show analytically that the LAD method outperforms the more popular LASSO method when the noise is sparse. At the same time its performance is no more than π/2 times worse in the presence of non-sparse noise. Our simulation results verify the validity of our theoretical predictions.