# One condition for solution uniqueness and robustness of both l1-synthesis and l1-analysis minimizations

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

## Key facts

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

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

- [Learning Product Graphs from Spectral Templates](https://mlsanity.com/paper/2211.02893/) (2022)
- [LogSpecT: Feasible Graph Learning Model from Stationary Signals with Recovery Guarantees](https://mlsanity.com/paper/2305.01379/) (2023)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)

## Abstract (arXiv)

The ℓ1-synthesis model and the ℓ1-analysis model recover structured signals from their undersampled measurements. The solution of former is a sparse sum of dictionary atoms, and that of the latter makes sparse correlations with dictionary atoms. This paper addresses the question: when can we trust these models to recover specific signals? We answer the question with a condition that is both necessary and sufficient to guarantee the recovery to be unique and exact and, in presence of measurement noise, to be robust. The condition is one--for--all in the sense that it applies to both of the ℓ1-synthesis and ℓ1-analysis models, to both of their constrained and unconstrained formulations, and to both the exact recovery and robust recovery cases. Furthermore, a convex infinity--norm program is introduced for numerically verifying the condition. A comprehensive comparison with related existing conditions are included.