On Model-Based RIP-1 Matrices
The Restricted Isometry Property (RIP) is a fundamental property of a matrix enabling sparse recovery [5]. Informally, an m ×n matrix satisfies RIP of order k in the ℓ p norm if ∥ Ax ∥ p ≈ ∥ x ∥ p for any vector x that is k-sparse, i.e., that has at most k non-zeros. The minimal number of rows m...
Main Authors: | Indyk, Piotr, Razenshteyn, Ilya |
---|---|
Other Authors: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Format: | Article |
Language: | en_US |
Published: |
Springer-Verlag Berlin Heidelberg
2014
|
Online Access: | http://hdl.handle.net/1721.1/86917 https://orcid.org/0000-0002-3962-721X https://orcid.org/0000-0002-7983-9524 |
Similar Items
-
Explicit Construction of RIP Matrices Is Ramsey‐Hard
by: Gamarnik, David
Published: (2021) -
Explicit Construction of RIP Matrices Is Ramsey‐Hard
by: Gamarnik, David
Published: (2021) -
Approxiamate Nearest Neighbor Search in High Dimensions
by: Andoni, Alexandr, et al.
Published: (2021) -
Practical data-dependent metric compression with provable guarantees
by: Indyk, Piotr, et al.
Published: (2019) -
Sparse Recovery Using Sparse Matrices
by: Gilbert, Anna, et al.
Published: (2012)