# Restricted Isometry Property for General p-Norms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2014.

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

- [On the well-spread property and its relation to linear regression](https://mlsanity.com/paper/2206.08092/) (2022)

## Abstract (arXiv)

The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an m × n matrix satisfies RIP of order k for the ℓp norm, if |Ax|p ≈ |x|p for every vector x with at most k non-zero coordinates. For every 1 ≤ p < ∞ we obtain almost tight bounds on the minimum number of rows m necessary for the RIP property to hold. Prior to this work, only the cases p = 1, 1 + 1 / log k, and 2 were studied. Interestingly, our results show that the case p = 2 is a "singularity" point: the optimal number of rows m is widetildeTheta(kp) for all p∈ [1,∞)setminus 2, as opposed to widetildeTheta(k) for k=2. We also obtain almost tight bounds for the column sparsity of RIP matrices and discuss implications of our results for the Stable Sparse Recovery problem.