# On robust recovery of signals from indirect observations

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 95 references that are in the map.
- First posted on arXiv 3 Jan 2025.

## Builds on (most cited first, 9 of 9)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (2019)
- [High Dimensional Robust Sparse Regression](https://mlsanity.com/paper/1805.11643/) (2018)
- [Corrupted Sensing: Novel Guarantees for Separating Structured Signals](https://mlsanity.com/paper/1305.2524/) (2013)
- [Robust Linear Regression: A Review and Comparison](https://mlsanity.com/paper/1404.6274/) (2014)
- [Multiscale scanning in inverse problems](https://mlsanity.com/paper/1611.04537/) (2016)
- [On Design of Polyhedral Estimates in Linear Inverse Problems](https://mlsanity.com/paper/2212.12516/) (2022)
- [Tight Computationally Efficient Approximation of Matrix Norms with Applications](https://mlsanity.com/paper/2110.04389/) (2021)

## Abstract (arXiv)

We consider an uncertain linear inverse problem as follows. Given observation ω=Ax_*+zeta where A∈ bf Rm× p and zeta∈ bf Rm is observation noise, we want to recover unknown signal x_*, known to belong to a convex set cal Xsubsetbf Rn. As opposed to the "standard" setting of such problem, we suppose that the model noise zeta is "corrupted" -- contains an uncertain (deterministic dense or singular) component. Specifically, we assume that zeta decomposes into zeta=Nnu_*+xi where xi is the random noise and Nnu_* is the "adversarial contamination" with known cal Nsubset bf Rn such that nu_*∈ cal N and N∈ bf Rm× n. We consider two "uncertainty setups" in which cal N is either a convex bounded set or is the set of sparse vectors (with at most s nonvanishing entries). We analyse the performance of "uncertainty-immunized" polyhedral estimates -- a particular class of nonlinear estimates as introduced in [15, 16] -- and show how "presumably good" estimates of the sort may be constructed in the situation where the signal set is an ellitope (essentially, a symmetric convex set delimited by quadratic surfaces) by means of efficient convex optimization routines.