Explicit matrices with the restricted isometry property

A matrix has the restricted isometry property of order k if it approximately preserves the length of every vector with at most k nonzero coordinates. Can a deterministic construction approach the sparsity achieved by random matrices while using far fewer rows than columns?

Why it matters and what counts as progress

Why it matters: Such matrices let compressed sensing preserve sparse signals after taking fewer measurements. Deterministic constructions give a way to choose the measurements without a random draw.

What counts as progress: Construct an explicit family with increasing sparsity order and distortion tending to zero while the ratio of rows to columns tends to zero. A lower bound can rule out a specified construction or class of methods.

How the problem developed

  1. 2007 · Problem statement [5]

    Terence Tao Asked for deterministic constructions comparable to random restricted isometries.

  2. 2011 · Square-root barrier surpassed [6]

    Jean Bourgain and colleagues Used cancellation to obtain an explicit family with sparsity exponent above one half.

  3. 10 Nov 2026 · Two-thirds sparsity exponent [1][2][3]

    Christian Kümmerle and Dustin G. Mixon with GPT-6 Astra Posted an explicit family with vanishing distortion and sparsity exponent approaching two thirds.

AI contribution

Sources

  1. Kümmerle and Mixon’s manuscript
  2. AI and formalization declaration
  3. Lean development for the matrix construction
  4. The authors’ explanation of the hybrid estimate
  5. Tao’s deterministic matrix question
  6. Bourgain and colleagues’ explicit constructions
  7. Zahl’s sphere and line incidence theorem
Publication history