Explicit restricted isometries with $k=m^{2/3-o(1)}$
Authors: Christian Kümmerle, Dustin G. Mixon
Abstract
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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Explicit constructions of RIP matrices and related problemsJ. Bourgain, S. Dilworth, Kevin Ford et al. · 2010 · arXiv.org · preprint, not peer reviewed · cited 257 times · Not summarized yet
Explicit constructions of RIP matrices and related problems develops explicit RIP matrices beyond the square-root sparsity scale, a construction context this paper advances.
Abstract
We give a new explicit construction ofn×N matrices satisfying the Restricted Isometry Property (RIP). Namely, for some e > 0, largeN , and anyn satisfyingN1−e ≤ n ≤ N , we construct RIP matrices of order k ≥ n1/2+e and constant δ = n−e. This overcomes the natural barrier k = O(n1/2) for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure. We also give a construction of sets of n complex numbers whose kth moments are uniformly small for 1 ≤ k ≤ N (Turan’s power sum problem), which…
-
Explicit RIP matrices: an updateKevin Ford, D. Kutzarova, G. Shakan · 2021 · Acta Mathematica Hungarica · cited 2 times · Not summarized yet
Explicit RIP matrices: an update improves explicit RIP parameters using additive combinatorics, in the construction line this paper studies.
Abstract
Leveraging recent advances in additive combinatorics, we exhibit explicit matrices satisfying the Restricted Isometry Property with better parameters. Namely, for ε=3.26·10-7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon=3.26\cdot 10^{-7}$$\end{document}, large k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{docu…
-
Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root BottleneckD. Mixon · 2014 · arXiv.org · preprint, not peer reviewed · cited 29 times · Not summarized yet
Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck develops the Bourgain et al. construction that this paper’s sparsity result advances.
Abstract
Matrices with the restricted isometry property (RIP) are of particular interest in compressed sensing. To date, the best known RIP matrices are constructed using random processes, while explicit constructions are notorious for performing at the “square-root bottleneck,” i.e., they only accept sparsity levels on the order of the square root of the number of measurements. The only known explicit matrix which surpasses this bottleneck was constructed by Bourgain, Dilworth, Ford, Konyagin, and Kutzarova in Bourgain et al. (Duke Math. J. 159:145–185, 2011). This chapter provides three contributions to advance the groundbreaking work of Bourgain et al.: (i) we develop an intuition for their matrix…
-
A conditional construction of restricted isometriesA. Bandeira, D. Mixon, Joel Moreira · 2014 · arXiv.org · preprint, not peer reviewed · cited 27 times · Not summarized yet
A conditional construction of restricted isometries uses Fourier rows indexed by quadratic residues to obtain RIP, rather than the graph-based construction here.
Abstract
We study the restricted isometry property of a matrix that is built from the discrete Fourier transform matrix by collecting rows indexed by quadratic residues. We find an $\epsilon>0$ such that, conditioned on a folklore conjecture in number theory, this matrix satisfies the restricted isometry property with sparsity parameter $K=\Omega(M^{1/2+\epsilon})$, where $M$ is the number of rows.
-
Derandomizing restricted isometries via the Legendre symbolAfonso S. Bandeira, Matthew Fickus, Dustin G. Mixon et al. · 2014 · Combinatorics · cited 16 times · AI summary available
Derandomizing restricted isometries via the Legendre symbol reduces randomness in Bernoulli RIP matrices, unlike this explicit graph-based construction.
Abstract
The restricted isometry property (RIP) is an important matrix condition in compressed sensing, but the best matrix constructions to date use randomness. This paper leverages pseudorandom properties of the Legendre symbol to reduce the number of random bits in an RIP matrix with Bernoulli entries. In this regard, the Legendre symbol is not special---our main result naturally generalizes to any small-bias sample space. We also conjecture that no random bits are necessary for our Legendre symbol--based construction.
-
The Road to Deterministic Matrices with the Restricted Isometry PropertyA. Bandeira, M. Fickus, D. Mixon et al. · 2012 · Journal of Fourier Analysis and Applications · cited 141 times · Not summarized yet
The Road to Deterministic Matrices with the Restricted Isometry Property evaluates deterministic RIP techniques and candidate matrices, a broader construction context.
Abstract
The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ET…
-
Breaking the k2 barrier for explicit RIP matricesJ. Bourgain, S. Dilworth, Kevin Ford et al. · 2011 · Symposium on the Theory of Computing · cited 28 times · Not summarized yet
Breaking the k2 barrier for explicit RIP matrices addresses the sparsity barrier for explicit RIP constructions that this paper studies.
-
A Simple Proof of the Restricted Isometry Property for Random MatricesRichard Baraniuk, M. Davenport, R. DeVore et al. · 2008 · Constructive Approximation · cited 2,610 times · Not summarized yet
A Simple Proof of the Restricted Isometry Property for Random Matrices concerns proving RIP for random matrices, rather than explicit constructions.
Prior work it builds on
-
Sharp Bounds for Guiduli-Type Hereditary Spectral ProblemsDong-Xiu Cai, Ji Zeng, Xiao-Dong Zhang · 2026 · cited 1 time · Not summarized yet
Sharp Bounds for Guiduli-Type Hereditary Spectral Problems studies spectral bounds under constraints on induced-subgraph edge counts, related to this paper’s graph selection argument.
Abstract
Guiduli asked in 1996 the following problem concerning the maximum spectral radius of a graph under hereditary density constraints. If an $n$-vertex graph $G$ satisfies $e(H)\le c|V(H)|^2$ for every subgraph $H$ of $G$, must one have $\lambda(G)\le 2cn$? More generally, what remains true when the exponent $2$ is replaced by a constant less than $2$? We study the natural power-law version of this question for all $1<p\le2$. For $1<p\le 2$, define \[ d_p(G)=\max_{\varnothing\ne S\subseteq V(G)}\frac{e(G[S])}{|S|^p}. \] We determine the sharp asymptotic upper bound for $\lambda(G)$ in terms of $d_p(G)$ and $n$. More precisely, every $n$-vertex graph $G$ with at least one edge satisfies \[ \lamb…
-
On Minkowski space and finite geometryM. Orel · 2014 · Journal of Combinatorial Theory · cited 4 times · Not summarized yet
On Minkowski space and finite geometry studies maps preserving light-like pairs in finite geometry, not restricted isometries.
Abstract
Abstract The main aim of this interdisciplinary paper is to characterize all maps on finite Minkowski space of arbitrary dimension n that map pairs of distinct light-like events into pairs of distinct light-like events. Neither bijectivity of maps nor preservation of light-likeness in the opposite direction, i.e. from codomain to domain, is assumed. We succeed in many cases, which include the one with n divisible by 4 and the one with n odd and ≥9, by showing that both bijectivity of maps and the preservation of light-likeness in the opposite direction are obtained automatically. In general, the problem of whether there exist non-bijective mappings that map pairs of distinct light-like event…
-
Discrete norms of a matrix and the converse to the Expander Mixing LemmaV. Lev · 2014 · arXiv: Combinatorics · preprint, not peer reviewed · cited 4 times · Not summarized yet
Discrete norms of a matrix and the converse to the Expander Mixing Lemma proves matrix norm estimates connected to graph spectra, but not RIP constructions.
Abstract
We define the discrete norm of a complex $m\times n$ matrix $A$ by $$ \|A\|_\Delta := \max_{0\ne\xi\in\{0,1\}^n} \frac{\|A\xi\|}{\|\xi\|}, $$ and show that $$ \frac c{\sqrt{\log h(A)+1}}\,\|A\| \le \|A\|_\Delta \le \|A\|, $$ where $c>0$ is an explicitly indicated absolute constant, $h(A)=\sqrt{\|A\|_1\|A\|_\infty}/\|A\|$, and $\|A\|_1,\|A\|_\infty$, and $\|A\|=\|A\|_2$ are the induced operator norms of $A$. Similarly, for the \emph{discrete Rayleigh norm} $$ \|A\|_P := \max_{\substack{0\ne\xi\in\{0,1\}^m \\ 0\ne\eta\in\{0,1\}^n}} \frac{|\xi^tA\eta|}{\|\xi\|\|\eta\|} $$ we prove the estimate $$ \frac c{\log h(A)+1}\,\|A\| \le \|A\|_P \le \|A\|. $$ These estimates are shown to be essentially b…
-
Finite two-distance tight framesA. Barg, A. Glazyrin, Kasso Okoudjou et al. · 2014 · arXiv: Functional Analysis · preprint, not peer reviewed · cited 48 times · Not summarized yet
Finite two-distance tight frames connects tight frames with strongly regular graphs, the frame structure used in this paper’s construction.
Abstract
A finite collection of unit vectors $S \subset \mathbb{R}^n$ is called a spherical two-distance set if there are two numbers $a$ and $b$ such that the inner products of distinct vectors from $S$ are either $a$ or $b$. We prove that if $a\ne -b,$ then a two-distance set that forms a tight frame for $\mathbb{R}^n$ is a spherical embedding of a strongly regular graph, and every strongly regular graph gives rise to two-distance tight frames through standard spherical embeddings. Together with an earlier work by S. Waldron on the equiangular case ({\em Linear Alg. Appl.}, vol. 41, pp. 2228-2242, 2009) this completely characterizes two-distance tight frames. As an intermediate result, we obtain a …
-
Steiner equiangular tight framesM. Fickus, D. Mixon, J. Tremain · 2010 · Linear Algebra and its Applications · cited 214 times · Not summarized yet
Steiner equiangular tight frames constructs sparse equiangular tight frames, a neighbouring frame-construction topic rather than RIP matrices.
Abstract
Abstract We provide a new method for constructing equiangular tight frames (ETFs). The construction is valid in both the real and complex settings, and shows that many of the few previously-known examples of ETFs are but the first representatives of infinite families of such frames. It provides great freedom in terms of the frame’s size and redundancy. This method also explicitly constructs the frame vectors in their native domain, as opposed to implicitly defining them via their Gram matrix. Moreover, in this domain, the frame vectors are very sparse. The construction is extremely simple: a tensor-like combination of a Steiner system and a regular simplex. This simplicity permits us to reso…
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 16 November 2026.