Restricted Isometry Property for General p-Norms

2014/07/08 by Allen-Zhu, Zeyuan, Gelashvili, Rati, Razenshteyn, Ilya · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Numerical Analysis (math.NA) #Probability (math.PR)

paper · doi:10.48550/arxiv.1407.2178

Abstract

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 \widetildeΘ(k^p) for all p∈ [1,∞)∖ \2\, as opposed to \widetildeΘ(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.

Cited by

• Restricted Quasiconvexity Isometry Property for Symmetric α-Stable Random Matrices

Related

• On Model-Based RIP-1 Matrices
• Sparsity and ℓ_p-Restricted Isometry
• Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness