AI summary · arXiv: 2611.14475v1 · math.FA

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

Christian Kümmerle, Dustin G. Mixon
Original paper Submitted to arXiv on 10 Nov. 2026 16 pages License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper constructs explicit real restricted isometries with sparsity k = m^{2/3-o(1)} and proves a matching 2/3 limit for methods that ignore Gram-matrix phases.

Question

Can explicit restricted isometries achieve sparsity exponents beyond the known square-root threshold while keeping the row-to-column ratio and restricted isometry constant vanishing? How far can arguments that use only entrywise absolute values go?

Method

The authors combine Gershgorin bounds with a flat-RIP estimate, reducing the construction to finding a large vertex set whose small subsets span few edges. They use a two-distance tight frame derived from the strongly regular graph VO_4^-(p), then select vertices using Zahl’s incidence result and a field-norm construction; for primes p congruent to 3 modulo 4, they take L = floor(log p), n = Lp^3, and k = floor(p^2/(log p)^6).

Findings

  • Result The construction gives an explicit family with vanishing aspect ratio and restricted isometry constant at sparsity k = m^{2/3-o(1)}.
    See the passage in the paper
    There is an explicit family of real $m\times n$ matrices with unit-norm columns such that $$m\longrightarrow\infty,\qquad\frac{m}{n}\longrightarrow 0,\qquad\delta_{k}\longrightarrow 0,\qquad k=m^{2/3-o(1)}.$$
  • Result For unit-norm columns, the paper proves that a phase-agnostic bound on the absolute Gram matrix cannot yield vanishing distortion when k is not o(m^{2/3}).
    See the passage in the paper
    In particular, if $m\to\infty$ and $m/n\to 0$, then $\Delta_{k}\to 0$ requires $k=o(m^{2/3})$.
  • Result The selected vertex sets have at most a constant multiple of L|U|^{3/2} edges for subsets U of size at most p^2.
    See the passage in the paper
    Every $U\subseteq V^{\prime}_{T}$ of size $s\leq p^{2}$ satisfies $e(U)\lesssim Ls^{3/2}$.
  • Result The particular two-distance tight-frame subframes used in the construction also fail to cross the 2/3 sparsity exponent, even if phase cancellation is considered.
    See the passage in the paper
    In particular, if $\mu\gtrsim m^{-1/3}$, then $\delta_{k}\to 0$ requires $k=o(m^{2/3})$.
  • Authors’ interpretation The authors identify estimating phased rectangular sums of large Gram entries as a possible direction for surpassing the barrier.
    See the passage in the paper
    To solve Problem 9, one might instead apply the hybrid estimate from Section 2: retain the induced $1$-norm for the small entries, but estimate the phased rectangular sums of the large entries using ideas from Bourgain et al. [5].

Limitations

  • The construction reaches the 2/3 exponent only up to a subpolynomial loss and does not establish an exponent greater than 2/3.
  • The explicit family is built from a particular strongly regular graph and selected subframes, so the result does not establish that all explicit constructions are limited to this exponent.
    See the passage in the paper
    Then for all sufficiently large $m$, it holds that $$\delta_{k}\geq\min\big\{\mu\sqrt{k-1},1\big\}$$ for every $1\leq k\leq n$.

Why it matters

The authors show that entrywise-absolute-value methods have a 2/3 barrier, rather than the previously presumed square-root barrier, and give an explicit construction attaining that exponent up to subpolynomial factors. Breaking the barrier requires methods that exploit phase cancellation, which the paper leaves as an open direction.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Compressed sensing restricted isometry property explicit matrix construction strongly regular graphs spectral norm

Read further

  • Comprehensive Summary
  • Layman's Summary
  • Blog article
  • Original abstract
The paper addresses the construction of explicit measurement matrices for compressed sensing that preserve the lengths of all sufficiently sparse vectors. Random matrices can achieve sparsity nearly proportional to the number of rows, but previous explicit constructions reached only exponents close to one-half, with earlier advances beyond that threshold being marginal. The authors construct an explicit family of real matrices with a growing number of rows \(m\), a row-to-column ratio tending to zero, and a restricted isometry constant tending to zero for sparsity \(k=m^{2/3-o(1)}\). Their main technique combines two bounds on the spectral norm of a Gram-matrix submatrix. Gershgorin’s theorem controls small inner products through row sums, while a flat restricted-isometry estimate handles large ones. To avoid estimating cancellation among the signs of the large inner products, the authors take their absolute values and represent their locations as edges in a graph. They show that the spectral norm is controlled when every small vertex set in this graph spans sufficiently few edges. In their construction, the required edge bound is proportional to the three-halves power of the set size. The construction begins with a two-distance tight frame: its columns have unit norm, and every pair of distinct columns has an inner product of one of two magnitudes. The authors obtain this frame from an eigenspace of the strongly regular graph VO-four-minus over a finite field. For a prime \(p\equiv 3\pmod 4\), the graph has \(p^4\) vertices, and the resulting frame has about \(p^3\) rows. Its two inner-product magnitudes are approximately \(p^{-1}\) and \(p^{-2}\). The authors then select about \(L p^3\) columns, where \(L\) grows slowly, using the graph of the field norm from a cubic extension of the finite field. A key geometric ingredient is a result of Zahl: small vertex sets either have few relevant pencils, which are special affine lines, or contain many points on a pair of complementary conics. The selected columns avoid both configurations in a controlled way: each pencil or affine-plane conic contains only a bounded number of selected points per translate. This yields the required edge-density estimate for every subset of at most \(p^2\) vertices. Combining the edge-density estimate with the hybrid norm bound gives a restricted-isometry constant bounded, up to constants, by \[ L\frac{\sqrt{k\log k}}{p}+\frac{k}{p^2}. \] Taking \(L\) to be about \(\log p\) and \(k\) to be about \(p^2/(\log p)^6\) makes this bound tend to zero. Since \(m\) is about \(p^3\), the construction achieves \(k=m^{2/3-o(1)}\), while \(m/n\) tends to zero. The paper also establishes a limitation for methods that ignore phases. For any unit-column matrix, the authors define a phase-agnostic quantity using the spectral norm of the entrywise absolute values of the Gram-matrix deviations. They prove a lower bound showing that this quantity cannot tend to zero when \(k\) grows faster than \(m^{2/3}\) in the stated sparse, highly rectangular regime. This identifies a two-thirds barrier for phase-agnostic arguments, improving on the familiar square-root barrier associated with Gershgorin’s theorem alone. The authors further show that their two-distance tight-frame subframes cannot surpass this barrier, even when phases are taken into account. The construction is explicit in the sense that its columns and matrix can be generated deterministically in polynomial time to the requested precision.

Was this synthesis useful?

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Figures and plots

Ask about a figure by number or use its question button to request visual analysis. Up to two figures and four image panels per question. Values read from plots are approximate; check the original data.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today
Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero Zotero guide
Citation alerts Citation alerts guide
Who works on it?

Among the 23 papers around this one, the name that comes back most: D. Mixon (4 papers)

6 more people sign several of them. The full map adds their institutions and approaches, from the papers of the last years.

Continue with Google Create a free account: your first map is free
Weekly letter Presented in "Mathematics and statistics this week" of 16 November 2026. Mathematics and statistics this week: Arithmetic, crystals and the limits of shape · Receive one by email for free

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

  1. Close Groundwork for this paper Cited by this paper
    Explicit constructions of RIP matrices and related problems
    J. 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…

  2. Close Groundwork for this paper Cited by this paper
    Explicit RIP matrices: an update
    Kevin 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…

  3. Close Groundwork for this paper Cited by this paper
    Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck
    D. 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…

  4. Close Another approach to the problem Cited by this paper
    A conditional construction of restricted isometries
    A. 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.

  5. Close Another approach to the problem
    Derandomizing restricted isometries via the Legendre symbol
    Afonso 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.

  6. Close Broader context Cited by this paper
    The Road to Deterministic Matrices with the Restricted Isometry Property
    A. 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…

  7. Close* Same question Cited by this paper
    Breaking the k2 barrier for explicit RIP matrices
    J. 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.

  8. Close* Broader context Cited by this paper
    A Simple Proof of the Restricted Isometry Property for Random Matrices
    Richard 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

  1. Related Broader context Used in depth by this paper
    Sharp Bounds for Guiduli-Type Hereditary Spectral Problems
    Dong-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…

  2. Related Broader context
    On Minkowski space and finite geometry
    M. 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…

  3. Related Broader context
    Discrete norms of a matrix and the converse to the Expander Mixing Lemma
    V. 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…

  4. Related Groundwork for this paper
    Finite two-distance tight frames
    A. 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 …

  5. Related Broader context
    Steiner equiangular tight frames
    M. 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…

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.

The illustrated guide to the papers around a paper

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.