# Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices

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

## Key facts

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

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

- [Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss](https://mlsanity.com/paper/2202.02063/) (2022)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning](https://mlsanity.com/paper/2309.04626/) (2023)
- [Compressive Fourier collocation methods for high-dimensional diffusion equations with periodic boundary conditions](https://mlsanity.com/paper/2206.01255/) (2022)
- [Solving Inverse Problems with Conditional-GAN Prior via Fast Network-Projected Gradient Descent](https://mlsanity.com/paper/2109.01105/) (2021)
- [Math for AI safety: an invitation for mathematicians](https://mlsanity.com/paper/2609.15289/) (2026)

## Abstract (arXiv)

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while leads to sharp results. It is shown that for any given constant t≥ 4/3, in compressed sensing δtkA < √(t-1)/t guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained ℓ1 minimization, and similarly in affine rank minimization δtrM< √(t-1)/t ensures the exact reconstruction of all matrices with rank at most r in the noiseless case via the constrained nuclear norm minimization. Moreover, for any ε>0, δtkA<√fract-1t+ε is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar result also holds for matrix recovery. In addition, the conditions δtkA < √(t-1)/t and δtrM< √(t-1)/t are also shown to be sufficient respectively for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.