# Phase Transitions in Recovery of Structured Signals from Corrupted Measurements

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

## Key facts

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

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

- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [The Squared-Error of Generalized LASSO: A Precise Analysis](https://mlsanity.com/paper/1311.0830/) (2013)
- [Corrupted Sensing: Novel Guarantees for Separating Structured Signals](https://mlsanity.com/paper/1305.2524/) (2013)

## Abstract (arXiv)

This paper is concerned with the problem of recovering a structured signal from a relatively small number of corrupted random measurements. Sharp phase transitions have been numerically observed in practice when different convex programming procedures are used to solve this problem. This paper is devoted to presenting theoretical explanations for these phenomenons by employing some basic tools from Gaussian process theory. Specifically, we identify the precise locations of the phase transitions for both constrained and penalized recovery procedures. Our theoretical results show that these phase transitions are determined by some geometric measures of structure, e.g., the spherical Gaussian width of a tangent cone and the Gaussian (squared) distance to a scaled subdifferential. By utilizing the established phase transition theory, we further investigate the relationship between these two kinds of recovery procedures, which also reveals an optimal strategy (in the sense of Lagrange theory) for choosing the tradeoff parameter in the penalized recovery procedure. Numerical experiments are provided to verify our theoretical results.