# Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2013.

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

- [Inference-Time Search Using Side Information for Diffusion-Based Image Reconstruction](https://mlsanity.com/paper/2510.03352/) (2025)
- [System Identification via Nuclear Norm Regularization](https://mlsanity.com/paper/2203.16673/) (2022)

## Abstract (arXiv)

This paper considers the linear inverse problem where we wish to estimate a structured signal x from its corrupted observations. When the problem is ill-posed, it is natural to make use of a convex function f(·) that exploits the structure of the signal. For example, ℓ1 norm can be used for sparse signals. To carry out the estimation, we consider two well-known convex programs: 1) Second order cone program (SOCP), and, 2) Lasso. Assuming Gaussian measurements, we show that, if precise information about the value f(x) or the ℓ2-norm of the noise is available, one can do a particularly good job at estimation. In particular, the reconstruction error becomes proportional to the "sparsity" of the signal rather than the ambient dimension of the noise vector. We connect our results to existing works and provide a discussion on the relation of our results to the standard least-squares problem. Our error bounds are non-asymptotic and sharp, they apply to arbitrary convex functions and do not assume any distribution on the noise.