Source-linked AI summary
Explicit constructions of RIP matrices and related problems
Jean Bourgain, S. J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova
TL;DR
The paper seeks explicit RIP matrices beyond the small-coherence barrier. It uses additive-combinatorial estimates and related elementary constructions to obtain improved RIP, Turán power-sum, Fourier-coefficient, and spherical-code parameters in stated ranges.
Problem
The paper addresses the open problem of constructing explicit RIP matrices and the limitations of prior constructions based on small coherence.
Method
The paper combines additive-energy, product-set sumset, and exponential-sum estimates with elementary constructions related to Turán’s power-sum problem and Fourier coefficients.
Results
Theorem 1 provides explicit RIP matrices with n ≤ k^{2−ε′0} for 0 ≤ k ≤ N^{1/2+ε′0}, while the constructions also yield coherence close to the cited bound.
Takeaways & Limitations
The constructions extend explicit RIP results beyond the coherence barrier and provide elementary examples for Turán’s problem, thin Fourier-coefficient sets, and spherical codes.
Abstract
from arXiv · showhide
We give a new explicit construction of $n\times N$ matrices satisfying the Restricted Isometry Property (RIP). Namely, for some c>0, large N and any n satisfying N^{1-c} < n < N, we construct RIP matrices of order k^{1/2+c}. This overcomes the natural barrier k=O(n^{1/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 k-th moments are uniformly small for 1\le k\le N (Turan's power sum problem), which improves upon known explicit constructions when (\log N)^{1+o(1)} \le n\le (\log N)^{4+o(1)}. This latter construction produces elementary explicit examples of n by N matrices that satisfy RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (\log N)^{1+o(1)} \le n\le (\log N)^{5/2+o(1)}.
1. Introduction
The paper addresses the open problem of explicit RIP constructions by moving beyond the small-coherence barrier, while also developing related constructions for Turán’s power-sum problem and spherical codes.
- Motivation: The paper seeks explicit RIP matrices, whereas all previously known explicit examples relied on systems of unit vectors with small coherence.Small-coherence constructions connect RIP matrices to spherical codes and other applications.
- Motivation: δ = (k −1)µ: coherence directly yields an RIP guarantee of order k for matrices with unit-norm columns.This relationship underlies the paper’s comparison with coherence-based constructions.
- Main RIP construction: n = o(k^2): additive-combinatorial methods produce RIP matrices whose dimension is subquadratic in the RIP order.The paper’s main construction is presented as overcoming the coherence-based barrier.
- Main RIP construction: Theorem 1 gives effective, explicit n × N RIP matrices for n ≥ n0 and n ≤ N^{1+ε0}, with order specified by the theorem’s bound.The theorem is then reformulated to obtain n ≤ k^{2−ε′0} for 0 ≤ k ≤ N^{1/2+ε′0}.
- Main RIP construction: The proof combines additive-energy estimates, sumset bounds in product sets, and exponential-sum estimates for products with special additive structure.These ingredients are identified as the key components of the proof of Theorem 1.
- Related constructions: The paper also introduces elementary coherence constructions matching the cited bound up to a log log N factor, with applications to Turán’s problem and thin sets with small Fourier coefficients.The same construction gives better estimates than existing explicit constructions in certain parameter ranges.
- Related constructions: Theorem 3 yields explicit unit-modulus complex sets for Turán’s problem and, through coherence, explicit RIP matrices whose columns form a spherical code.These constructions improve on the cited comparison in the range n ≪ L^4, while requiring n to be prime.
2. Construction of the matrix in Theorem 1
The construction defines a finite-field matrix from structured sets and proves the estimates needed to obtain RIP for the stated parameter range.
- Matrix construction: The matrix Φ_p is a p×N matrix whose columns u_{a,b} are indexed by a∈A and b∈B in F_p.The construction uses the exponential function e_p and later extends Φ_p to an n×N matrix by appending zero rows.
- Matrix construction: The set A is defined as {x^2 + Ux : 1 ≤ x ≤ L}, with L=⌊p^α⌋ and U=L^(4m−1).The parameters are chosen under the stated conditions involving m, α, and sufficiently large p.
- Matrix construction: The set B is constructed from base-2M expansions with digits x_j∈{0,…,M−1}, giving a structured product-set model.The resulting set is related to a cube through its digit representation, and its elements are bounded relative to p.
- RIP conclusion: For sufficiently large parameters, Lemma 2 supplies a positive exponent ε1, and the resulting matrix has RIP order ⌊√n/2⌋ with δ=p^−ε1.Taking N≤n^(1+ε0), padding with zero rows, and applying Lemma 1 yields Theorem 1.
- Proof strategy: The proof of the main estimate separates contributions according to additive structure in subsets of B and phase dispersion from dilation weights.Large additive energy yields cancellation in the b variables, while the complementary case uses moment estimates and the additive properties of A.
3. The Flat-RIP property
The paper reduces RIP verification to flat vectors, then converts flat-RIP bounds into ordinary RIP with controlled loss in the order and constant.
- Definition and reduction: Flat-RIP requires the relevant bilinear estimates only for disjoint index sets of size at most k.The paper uses this property because it is closely related to testing vectors with zero-one entries and at most k ones.
- Conversion to RIP: Lemma 3 converts flat-RIP of order k and constant δ into RIP of order 2sk with constant 44sδ log k.The conversion applies for k≥2^10 and uses a decomposition of supports and coefficient levels.
- Proof mechanism: The proof handles nonnegative coefficients by dyadic partitioning and Cauchy–Schwarz estimates.The coefficient ranges are grouped into sets J_{i,ν} before summing the resulting bounds.
- Proof mechanism: For arbitrary complex coefficients, each support is partitioned into s subsets of size at most k, and the flat-RIP estimate is applied to these pieces.This produces the stated dependence on s in the final RIP constant and order.
- Scope: The reduction is sufficient for the paper’s purposes, although applying Lemma 1 directly could improve the RIP constant.The authors explicitly state that the stronger constant is unnecessary for their corollary.
4. Some definitions and results from additive combinatorics
This section develops additive-combinatorial tools for structured sets, relating additive energy, restricted sumsets, difference sets, and convolution estimates.
- Definitions: For subsets of an abelian group, sums, differences, restricted sums, additive energy, convolution, and L^r norms are defined for later estimates.Restricted sums retain only pairs specified by a relation F, while additive energy counts equal-sum pairs.
- Structured sets: The structured set B is Freiman-isomorphic to a digit cube, so sumset sizes in B can be studied through the corresponding cube.The bijection preserves additive relations and therefore preserves sizes of sums of subsets.
- Sumset estimates: For any nonempty set A, the sumset satisfies |A+A|≤|A−A|^2/|A|.This is the stated Plünnecke–Ruzsa estimate used among the additive-combinatorial tools.
- Energy and structure: Large additive energy forces a subset to contain a large piece with a comparatively small difference set.This follows by combining the energy-to-restricted-sumset lemma with a Balog–Szemerédi–Gowers-type result.
5. A sumset estimate in product sets
The section proves a sumset lower bound for product sets and derives additive and energy estimates for structured subsets of finite fields.
- Main estimate: Theorem 5 establishes |A + B| ≥ (|A||B|)^τ for arbitrary subsets A, B of C = {0, . . . , M − 1}^r.The exponent τ is defined through the theorem’s associated equation.
- Exponent behavior: The exponent’s asymptotic behavior is sharp in the sense that 2τ_M − 1 has the stated limiting behavior as M grows.The section notes that inequality (5.1) likely holds with the comparison exponent τ′, known for M = 2.
- Proof strategy: The proof uses UR-paths, which enumerate coordinatewise steps while controlling ordered products of nonnegative weights.The path construction is combined with rearrangement and Lemma 7.
- Proof strategy: The key analytic step verifies the required inequality through f(x) = x^2τ + (1 − x)^τ − 1 on the interval [0, 1].The argument uses the sign of the third derivative and zeros at 0, 1/M, and 1.
- Consequences: For structured sets, the estimate implies |B − B| ≥ p^β/5|B| whenever B ⊂ B and |B| > p^1/4.The set B is related to C through a Freiman isomorphism.
- Consequences: For S ⊂ B with |S| > p^1/3, the additive energy satisfies E(S, S) ≤ p^−β/50|S|^3.The proof obtains this by contradicting the preceding difference-set lower bound.
6. The proof of Lemma 2
The proof of Lemma 2 develops exponential-sum estimates by decomposing structured sets and exploiting dissociative additive relations.
- Case reduction: The argument first separates the case of small |A_1|M_1, where an earlier estimate directly yields the target bound.Otherwise it assumes |A_1|M_1 ≥ p^1/2−γ/10 and proceeds with the structured case.
- Analytic estimates: The estimates repeatedly apply Cauchy–Schwarz, Hölder’s inequality, and Parseval’s identity to bound the relevant double sums.These inequalities reduce the exponential-sum problem to controlled combinatorial expressions.
- Analytic estimates: The dissociative property makes the relevant additive relations trivial, which supplies the required bound for the associated moments or sums.The argument explicitly invokes this property after expanding the expressions involving elements of A_2.
- Set decomposition: A maximal subset B_0 is selected so that condition (6.5) holds, and the complement is analyzed using Lemmas 9 and 10.An enlargement argument shows that the complementary contribution must satisfy (6.6).
- Completion: Combining the resulting bounds with Corollaries 1 and 2 yields the needed lower bound on |B − B| and completes Lemma 2.The final parameter estimates use conditions (6.2)–(6.4) and the preceding inequalities.
7. Thin sets with small Fourier coefficients
This section constructs thin residue sets with small Fourier coefficients by combining prime-indexed multisets and proving their elements remain distinct modulo a larger prime.
- Distinctness: Lemma 11 guarantees distinct residues for r + s(p)(p − 1)q when q ≥ RP^2.Here p ranges over primes in (P/2, P], 1 ≤ r ≤ R, and s(p) lies in S_p.
- Construction: The construction uses multisets T = {r + s(p)(p − 1)q} modulo q, with Fourier bounds inherited from the component sets S_p.Lemma 12 states the setup when each S_p has size S and |f_Sp| ≤ ε.
- Fourier estimates: The proof estimates Fourier coefficients by separating divisibility cases for k and combining bounds for the factors A(k) and B(p, k).Prime-counting estimates control the number of large prime divisors that can contribute.
- Result: For sufficiently large prime N and N^−1/2 log^2 N ≤ μ < 1, Corollary 5 provides a residue set T with |f_T| ≤ μ.The construction also ensures T is a set rather than merely a multiset.
8. An explicit construction for Tur´an’s problem
The section constructs explicit complex numbers from prime-indexed residue sets and proves uniformly small power sums through the preceding Fourier estimates.
- Construction: For each prime q in (P_1/2, P_1], the construction supplies a multiset S_q of residues modulo q with a common size S.The sets are obtained from Lemma 14 and condition (8.1).
- Construction: The complex numbers are defined as the union of e(s/q) over s ∈ S_q and primes q in (P_1/2, P_1].This produces the multiset {z_1, . . . , z_n}.
- Moment bounds: For 1 ≤ k ≤ N, the proof separates primes dividing k from those not dividing k when estimating the k-th power sum.The latter case uses the Fourier bound from the component sets, while the former contributes S.
- Moment bounds: Combining the two cases with Proposition 4 yields the required uniform estimate for the power sums.The parameters R_0, P_0, and P_1 are chosen as in the proof of Theorem 2.