Open: explicit RIP matrices beyond the square-root barrier

ProofResearch⏱ ResearchHigh-Dim StatisticsHigh-Dim Probabilityopen problemrestricted isometryexplicit constructionderandomisation

Theory: Sparse Recovery, Compressed Sensing and the Lasso →

Problem

Random matrices satisfy the restricted isometry property of order $s$ with $m = O(s\log(d/s))$ rows, with high probability. Deterministic constructions are far weaker: standard coherence-based arguments certify RIP only up to $s = O(\sqrt m)$ .

Construct, explicitly and in polynomial time, an $m \times d$ matrix satisfying RIP of order $s = m^{1/2+\epsilon}$ for some fixed $\epsilon>0$ — or better, $s = \tilde O(m)$ , matching the random case.

This is an open problem. Nobody has a solution, and none is hidden below — what is recorded is the state of the argument. Progress on it would be publishable.

What is known

This problem is open. What follows is an account of what has been proved, what has only been measured, and where the argument stops — not a solution, because there is not one.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Derive the soft-thresholding operator	High-Dim Statistics	Proof	Intermediate	30 min
The geometry of l1 versus l2 constraints	High-Dim Statistics	Proof	Intermediate	30 min
Implement ISTA and verify the lasso rate run	High-Dim Statistics	Coding	Advanced	3 hours
Union bound over supports for the restricted isometry property	High-Dim Statistics	Proof	Advanced	1 hour
The lasso error vector lies in a cone abyss	High-Dim Statistics	Proof	Graduate	1 hour