betaFeedback

WorksMathematics

Explicit restricted isometries with k=m2/3−o(1)k=m^{2/3-o(1)}

Abstract

We construct an explicit family of real m×nm\times n restricted isometries with m→∞m\to\infty, m/n→0m/n\to 0, δk→0δ_k\to 0, and k=m2/3−o(1)k=m^{2/3-o(1)}. We combine Gershgorin's circle theorem with a flat RIP estimate to reduce the problem to choosing a large vertex set in a strongly regular graph with the property that every small subset spans few edges. We select this vertex set using an incidence geometric result due to Zahl. The proof only uses the entrywise absolute value of the Gram matrix despite the conventional wisdom that such proof techniques exhibit a barrier of m1/2m^{1/2}. We prove that this barrier is actually m2/3m^{2/3}, and we show that our particular construction exhibits the same barrier.

Paper details

vlnc:W_vrm78hhu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…