# Simple Error Bounds for Regularized Noisy Linear Inverse Problems

arXiv: https://arxiv.org/abs/1401.6578 · HTML: https://mlsanity.com/paper/1401.6578/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2014.

## Built on by (most cited first, 1 of 1)

- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)

## Abstract (arXiv)

Consider estimating a structured signal x0 from linear, underdetermined and noisy measurements y=Ax0+z, via solving a variant of the lasso algorithm: hatx=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 |hatx-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 δ(λpartial((f(x0))), termed the Gaussian squared distance to the scaled subdifferential. We connect our result to the literature and verify its validity through simulations.