Résumé IA · arXiv: 2611.14475v1 · math.FA

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

Christian Kümmerle, Dustin G. Mixon
Article original Soumis à arXiv le 10 Nov. 2026 16 pages Licence : NONEXCLUSIVE-DISTRIB 1.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article construit explicitement des matrices réelles satisfaisant la propriété d’isométrie restreinte jusqu’à k = m^{2/3-o(1)}, et établit une barrière de même ordre pour les méthodes indépendantes des phases.

Question

Comment dépasser l’exposant 1/2 des constructions explicites antérieures en contrôlant les constantes d’isométrie restreinte sans exploiter les phases du Gramien ? Jusqu’où peut-on aller avec une telle approche ?

Méthode

Les auteurs combinent la borne de Gershgorin pour les petites entrées du Gramien et une estimation de type flat RIP pour les grandes entrées, ramenant le contrôle à la densité des petits sous-graphes d’un graphe fortement régulier. Ils sélectionnent un sous-ensemble de sommets du graphe elliptique affine VO₄⁻(p) à l’aide d’un résultat de Zahl et de graphes de la norme sur F_{p³}; pour p premier congru à 3 modulo 4, ils prennent L = ⌊log p⌋, n = Lp³ et k = ⌊p²/(log p)⁶⌋.

Résultats

  • Résultat La construction fournit des matrices réelles explicites dont la constante d’isométrie restreinte tend vers zéro pour k = m^{2/3-o(1)}, tandis que le rapport m/n tend vers zéro.
  • Interprétation des auteurs La borne hybride réduit l’obtention d’une isométrie restreinte au contrôle du nombre d’arêtes dans les sous-graphes induits par de petits ensembles de sommets.
  • Résultat Pour des matrices à colonnes unitaires, le contrôle de la valeur absolue entrée par entrée du Gramien impose k = o(m^{2/3}) lorsque m tend vers l’infini et m/n tend vers zéro.
  • Résultat Les sous-trames à deux distances utilisées dans la construction ne franchissent pas l’exposant 2/3, même lorsque leur cohérence est au moins de l’ordre de m^{-1/3}.
  • Interprétation des auteurs Les auteurs identifient l’estimation des sommes rectangulaires avec leurs phases comme une piste possible pour dépasser la barrière de 2/3.

Limites

  • La méthode qui ignore les phases atteint sa limite à l’ordre 2/3; le papier ne construit pas de famille dépassant cet exposant.
    Voir le passage dans l’article
    By Theorem 4, we have reached the limit of phase agnosticism.
  • Le dépassement de 2/3 par une méthode exploitant les phases reste une question ouverte dans l’article.

Portée

Le résultat établit qu’une preuve fondée sur les valeurs absolues du Gramien peut dépasser la barrière classique de la racine carrée et atteindre l’exposant 2/3. Les auteurs montrent aussi que cette approche, et leur construction particulière à deux distances, ne peuvent aller au-delà de cet ordre sans tenir compte des phases.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : isométrie restreinte matrices explicites vecteurs clairsemés graphes fortement réguliers annulation des phases

Pour aller plus loin

  • Résumé Complet
  • Résumé vulgarisé
  • Article de blog
  • Abstract original
L’article étudie dans quelle mesure il est possible de construire explicitement des matrices qui préservent presque la norme des vecteurs clairsemés, une propriété connue sous le nom d’isométrie restreinte (RIP). Les auteurs cherchent à obtenir des matrices de plus en plus grandes, comportant beaucoup plus de colonnes que de lignes, tout en faisant tendre leur constante d’isométrie restreinte vers zéro. Avant ces travaux, les constructions explicites inconditionnelles préservaient essentiellement les vecteurs ayant un nombre de coordonnées non nulles de l’ordre de la racine carrée du nombre de lignes, avec seulement de légères améliorations de l’exposant. Les auteurs visent un exposant supérieur sans s’appuyer sur l’annulation des phases des produits scalaires entre les colonnes. Leur méthode combine deux estimations. Pour les petits produits scalaires, ils utilisent l’inégalité de Gershgorin, qui borne la norme spectrale à partir des sommes des valeurs absolues dans les lignes ou les colonnes. Pour les grands produits scalaires, ils recourent à une estimation liée au RIP plat, formulée à l’aide de sommes sur des ensembles de colonnes. En remplaçant les produits scalaires par leurs valeurs absolues, ils ramènent cette seconde étape à un problème de graphes : les arêtes représentent les produits scalaires importants, et chaque petit ensemble de sommets doit induire peu d’arêtes. Une estimation générale relie la croissance du nombre d’arêtes dans ces sous-graphes à la qualité de l’isométrie obtenue. Les auteurs établissent également une limite fondamentale pour les méthodes indépendantes des phases. Pour toute matrice à colonnes unitaires, si le nombre de lignes \(m\) tend vers l’infini et si le rapport entre le nombre de lignes et le nombre de colonnes tend vers zéro, alors une constante d’isométrie tendant vers zéro exige que le nombre \(k\) de coordonnées préservées soit inférieur à \(m^{2/3}\), à un facteur lui-même tendant vers zéro près. Cette borne concerne une mesure plus forte que la constante habituelle, obtenue en prenant les valeurs absolues des entrées de la matrice de Gram. Elle montre que les méthodes qui ignorent les phases ne peuvent dépasser l’exposant \(2/3\). La construction atteint ce seuil à des facteurs sous-polynomiaux près. Elle repose sur un cadre serré réel dont les produits scalaires hors diagonale prennent deux valeurs distinctes. Ce cadre est obtenu à partir d’un graphe fortement régulier associé à la géométrie affine elliptique en dimension quatre sur un corps fini. Pour un nombre premier \(p\) congru à \(3\) modulo \(4\), le graphe possède \(p^4\) sommets, tandis que le cadre comporte environ \(p^3\) lignes. Les produits scalaires prennent des valeurs de tailles respectives approximativement égales à \(p^{-1}\) et \(p^{-2}\). Les auteurs sélectionnent ensuite des sommets de manière à éviter les sous-graphes trop denses. Ils s’appuient sur un résultat de Zahl concernant les configurations géométriques du graphe, puis construisent explicitement un ensemble à l’aide de la norme d’une extension de corps de degré trois. Tout petit ensemble sélectionné, de taille au plus \(p^2\), induit au plus un nombre d’arêtes proportionnel à \(\log p\) multiplié par la puissance \(3/2\) de sa taille.

Cette synthèse vous a-t-elle été utile ?

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Figures et graphiques

Posez une question sur une figure en indiquant son numéro ou en utilisant son bouton de question pour demander une analyse visuelle. Au maximum deux figures et quatre panneaux par question. Les valeurs lues sur les graphiques sont approximatives ; vérifiez les données originales.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui
Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero Guide Zotero
Alertes de citation Guide des alertes de citations
Qui travaille dessus ?

Parmi les 23 articles autour de celui-ci, le nom qui revient le plus : D. Mixon (4 articles)

6 autres personnes en signent plusieurs. La carte complète ajoute leurs institutions et leurs approches, d’après les articles des dernières années.

Continuer avec Google Créez un compte gratuit : votre première carte est offerte
Lettre hebdomadaire Présenté dans « Mathématiques et statistiques cette semaine » du 16 novembre 2026. Mathématiques et statistiques cette semaine : des équations aux formes optimales · En recevoir une par email gratuitement

Les articles autour de celui-ci

Les voir sur une carte

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

  1. Proche Base de cet article Cité par cet article
    Explicit constructions of RIP matrices and related problems
    J. Bourgain, S. Dilworth, Kevin Ford et al. · 2010 · arXiv.org · preprint, non relu par les pairs · cité 257 fois · Pas encore résumé

    Explicit constructions of RIP matrices and related problems dépasse la borne liée à la cohérence avec des matrices explicites, tandis que cet article pousse le contrôle jusqu’à l’exposant 2/3.

    Résumé scientifique

    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. Proche Base de cet article Cité par cet article
    Explicit RIP matrices: an update
    Kevin Ford, D. Kutzarova, G. Shakan · 2021 · Acta Mathematica Hungarica · cité 2 fois · Pas encore résumé

    Explicit RIP matrices: an update améliore les paramètres de constructions explicites par combinatoire additive, sujet que cet article prolonge en visant un exposant supérieur.

    Résumé scientifique

    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. Proche Base de cet article Cité par cet article
    Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck
    D. Mixon · 2014 · arXiv.org · preprint, non relu par les pairs · cité 29 fois · Pas encore résumé

    Explicit Matrices with the Restricted Isometry Property: Breaking the Square-Root Bottleneck examine une construction dépassant le seuil racine carrée, que cet article étend à l’exposant 2/3.

    Résumé scientifique

    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. Proche Autre approche du problème Cité par cet article
    A conditional construction of restricted isometries
    A. Bandeira, D. Mixon, Joel Moreira · 2014 · arXiv.org · preprint, non relu par les pairs · cité 27 fois · Pas encore résumé

    A conditional construction of restricted isometries utilise une transformée de Fourier discrète restreinte aux résidus quadratiques, au lieu des graphes fortement réguliers de cet article.

    Résumé scientifique

    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. Proche Autre approche du problème
    Derandomizing restricted isometries via the Legendre symbol
    Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon et al. · 2014 · Combinatorics · cité 16 fois · Résumé IA disponible

    Derandomizing restricted isometries via the Legendre symbol réduit les bits aléatoires d’une matrice de Bernoulli, tandis que cet article construit des matrices explicites.

    Résumé scientifique

    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. Proche Article de revue Cité par cet article
    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 · cité 141 fois · Pas encore résumé

    The Road to Deterministic Matrices with the Restricted Isometry Property examine plusieurs techniques déterministes pour établir la RIP, dont les constructions explicites étudiées ici.

    Résumé scientifique

    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. Proche* Contexte plus large Cité par cet article
    Breaking the k2 barrier for explicit RIP matrices
    J. Bourgain, S. Dilworth, Kevin Ford et al. · 2011 · Symposium on the Theory of Computing · cité 28 fois · Pas encore résumé

    Breaking the k2 barrier for explicit RIP matrices traite aussi de constructions RIP explicites et de leurs limites, mais son résumé ne précise pas de méthode.

  8. Proche* Contexte plus large Cité par cet article
    A Simple Proof of the Restricted Isometry Property for Random Matrices
    Richard Baraniuk, M. Davenport, R. DeVore et al. · 2008 · Constructive Approximation · cité 2 610 fois · Pas encore résumé

    A Simple Proof of the Restricted Isometry Property for Random Matrices porte sur la RIP, mais son résumé ne précise ni méthode ni résultat à comparer.

Les travaux antérieurs sur lesquels il s’appuie

  1. Apparenté Contexte plus large Utilisé en profondeur par cet article
    Sharp Bounds for Guiduli-Type Hereditary Spectral Problems
    Dong-Xiu Cai, Ji Zeng, Xiao-Dong Zhang · 2026 · cité 1 fois · Pas encore résumé

    Sharp Bounds for Guiduli-Type Hereditary Spectral Problems étudie les rayons spectraux sous contraintes de densité des sous-graphes, notion liée à la réduction utilisée ici.

    Résumé scientifique

    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. Apparenté Contexte plus large
    On Minkowski space and finite geometry
    M. Orel · 2014 · Journal of Combinatorial Theory · cité 4 fois · Pas encore résumé

    On Minkowski space and finite geometry étudie des applications préservant la relation de lumière dans des espaces finis, sans traiter la propriété d’isométrie restreinte.

    Résumé scientifique

    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. Apparenté Contexte plus large
    Discrete norms of a matrix and the converse to the Expander Mixing Lemma
    V. Lev · 2014 · arXiv: Combinatorics · preprint, non relu par les pairs · cité 4 fois · Pas encore résumé

    Discrete norms of a matrix and the converse to the Expander Mixing Lemma établit des bornes de normes matricielles discrètes, sujet voisin du contrôle matriciel de cet article.

    Résumé scientifique

    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. Apparenté Contexte plus large
    Finite two-distance tight frames
    A. Barg, A. Glazyrin, Kasso Okoudjou et al. · 2014 · arXiv: Functional Analysis · preprint, non relu par les pairs · cité 48 fois · Pas encore résumé

    Finite two-distance tight frames relie les graphes fortement réguliers aux cadres serrés à deux distances, tandis que cet article exploite ces graphes pour construire des matrices RIP.

    Résumé scientifique

    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. Apparenté Contexte plus large
    Steiner equiangular tight frames
    M. Fickus, D. Mixon, J. Tremain · 2010 · Linear Algebra and its Applications · cité 214 fois · Pas encore résumé

    Steiner equiangular tight frames construit des familles explicites de cadres serrés, mais ne traite pas la propriété d’isométrie restreinte.

    Résumé scientifique

    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…

Comment ces articles sont-ils trouvés ?

Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.

Mis à jour le 16 novembre 2026.

Le guide illustré des articles autour d’un article

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.