TOPICS
Search

Restricted Isometry Property

The restricted isometry property is a condition that a matrix approximately preserves the Euclidean norm of every vector having at most a prescribed number of nonzero coordinates (Candès and Tao 2005). For a matrix Phi and a positive integer k, its restricted isometry constant delta_k is the least nonnegative real number delta for which

(1-delta)||z||_2^2<=||Phiz||_2^2<=(1+delta)||z||_2^2

for every vector z with at most k nonzero coordinates. Suitably small restricted isometry constants control the stability of recovering such vectors from linear measurements in compressed sensing.

Kümmerle and Mixon (2026) report an explicit family of real matrices of size m×n with unit-norm columns such that m->infty, m/n->0, delta_k->0, and

k=m^(2/3-o(1)).

The entries can be generated deterministically in time polynomial in the matrix dimensions and the requested output precision. The notation o(1) denotes a quantity tending to zero. Kümmerle and Mixon (2026) credit GPT-6 Astra with developing the proof, which they subsequently checked and formalized.

See also

Compressed Sensing, Euclidean Norm, Matrix, Vector

Explore with Wolfram|Alpha

References

Candès, E. J. and Tao, T. "Decoding by Linear Programming." IEEE Trans. Inform. Th. 51, 4203-4215, 2005. https://doi.org/10.1109/TIT.2005.858979.Kümmerle, C. and Mixon, D. G. "Explicit Restricted Isometries with k=m^(2/3-o(1))." 10 Nov 2026. https://arxiv.org/abs/2611.14475v1.

Cite this as:

Weisstein, Eric W. "Restricted Isometry Property." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RestrictedIsometryProperty.html

Subject classifications