具有 k=m^{2/3-o(1)} 的显式受限等距构造
Explicit restricted isometries with $k=m^{2/3-o(1)}$
Christian Kümmerle, Dustin G. Mixon
AI 速读 基于摘要
作者构造了一类显式实 m×n 受限等距矩阵,使稀疏度 k 达到 m^{2/3-o(1)},并说明仅用 Gram 矩阵逐元素绝对值的方法存在 m^{2/3} 的屏障。
math.FA · cs.IT · math.CO · math.MG
查看原文摘要
We construct an explicit family of real $m\times n$ restricted isometries with $m\to\infty$, $m/n\to 0$, $δ_k\to 0$, and $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 $m^{1/2}$. We prove that this barrier is actually $m^{2/3}$, and we show that our particular construction exhibits the same barrier.