Restricted isometry property - Wikipedia
restricted-isometry-propertycompressed-sensingsparse-recoverylinear-algebrarandom-matrices
Abstraction: Near-isometry condition on matrices enabling sparse signal recovery
Key points:
- RIP with constant δ_s: for every m×s submatrix A_s and every s-dimensional vector y, (1-δ_s)||y||^2 ≤ ||A_s y||^2 ≤ (1+δ_s)||y||^2
- Equivalent to requiring all eigenvalues of A_s^T A_s lie in [1-δ_s, 1+δ_s] for every s-column submatrix
- Introduced by Emmanuel Candès and Terence Tao for compressed sensing; sufficient for stable sparse signal recovery via linear programming
- Computing RIP constants is strongly NP-hard and NP-hard to approximate; no efficient deterministic constructions known
- Random Gaussian, Bernoulli, and partial Fourier matrices satisfy RIP with exponentially high probability with m nearly linear in sparsity s
- Tightest upper bounds on RIP constants are for Gaussian matrices, computable via Wishart matrix eigenvalue distributions
Connections: Compressed Sensing · Sparse Recovery
Source: http://en.wikipedia.org/wiki/Restricted_isometry_property