Fourier Ratio and Restricted Isometry via Entropic Descent
Abstract
In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's Λ(p) selection theorem), entropic mirror descent gives an improved restricted isometry bound, improving sampling and recovery bounds in the Fourier Ratio program. Let H be a complex n× n matrix with H*H=nI and |Hij|=1. For fixed 0<ε<1/4 and A0>0, independent Bernoulli row selection with expected cardinality Cε,A0rlog2en/rlog(2r)≤ m≤ n/2 preserves, after normalization by √m, the squared norm of every complex vector y with |y|1≤√r|y|2 within a factor 1±ε, with failure probability at most Cn−A0. This includes every r-sparse vector and also fully supported ones; support size enters only through this inequality. For y=f̂ the condition is exactly FR(f)2≤ r, where FR(f)=|f̂|1/|f̂|2, giving uniform energy sampling and approximate recovery even for signals with full Fourier support. The same holds for a uniform subset of prescribed cardinality, and for discrete Fourier and real Hadamard matrices. At fixed accuracy the bound removes one sparsity logarithm from the earlier count and replaces log n by log2en/r; for Walsh matrices it matches, up to constants, the lower bound of Błasiok et al.\ in their range. One relative-entropy potential controls the corrections of an amplitude predictor at every scale; counting them on the symmetric difference of two samples gives the uniform estimate. We also prove the sufficient bound CA0ε−5rlog2en/rlog2r/ε, and stable sparse recovery from Cslog2en/slog(2s) measurements, with error controlled by the noise and the best s-term approximation.
Related
- Rank-one Factored Gradient Descent without Restricted Isometry: Application to Quantum Pure State Tomography on Multi-Qubits
- Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
- Even-degree Hermitian Ikeda lifts via Fourier-Jacobi descent
BibTeX
@misc{burstein2026fourier,
title = {{Fourier Ratio and Restricted Isometry via Entropic Descent}},
author = {Will Burstein and Alex Iosevich and Ben Krause},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.22568},
eprint = {2609.22568},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22568},
}
RIS
TY - UNPB
TI - Fourier Ratio and Restricted Isometry via Entropic Descent
AU - Will Burstein
AU - Alex Iosevich
AU - Ben Krause
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2609.22568
UR - https://arxiv.org/abs/2609.22568
AB - In this second paper on descent methods as proof mechanisms in harmonic analysis (the first treated Bourgain's Λ(p) selection theorem), entropic mirror descent gives an improved restricted isometry bound, improving sampling and recovery bounds in the Fourier Ratio program. Let H be a complex n× n matrix with H^*H=nI and |H_ij|=1. For fixed 0<ε<1/4 and A_0>0, independent Bernoulli row selection with expected cardinality C_ε,A_0rlog2en/rlog(2r)≤ m≤ n/2 preserves, after normalization by √m, the squared norm of every complex vector y with |y|_1≤√r|y|_2 within a factor 1±ε, with failure probability at most Cn^−A_0. This includes every r-sparse vector and also fully supported ones; support size enters only through this inequality. For y=f̂ the condition is exactly FR(f)^2≤ r, where FR(f)=|f̂|_1/|f̂|_2, giving uniform energy sampling and approximate recovery even for signals with full Fourier support. The same holds for a uniform subset of prescribed cardinality, and for discrete Fourier and real Hadamard matrices. At fixed accuracy the bound removes one sparsity logarithm from the earlier count and replaces log n by log2en/r; for Walsh matrices it matches, up to constants, the lower bound of Błasiok et al.\ in their range. One relative-entropy potential controls the corrections of an amplitude predictor at every scale; counting them on the symmetric difference of two samples gives the uniform estimate. We also prove the sufficient bound C_A_0ε^−5rlog2en/rlog2r/ε, and stable sparse recovery from Cslog2en/slog(2s) measurements, with error controlled by the noise and the best s-term approximation.
ER -