A new mathematical analysis says the number of distinct weighted point evaluations needed to meet a weighted L2 Marcinkiewicz–Zygmund inequality can be quadratic in the dimension of a function space in the worst case. For an m-dimensional complex space at relative distortion ε, the paper bounds the required number N(m, ε) between max{m, m(m + 1)(1 − ε²)/[2(1 + mε²)]} and min{m², 5m/ε²}, for m ≥ 2 and 0 < ε < 1.
The result describes a trade-off rather than one fixed sample count. At smaller distortion, the paper says the necessary scale is quadratic in m; at larger distortion, the lower bound follows an m/ε² pattern. Across these regimes, it gives the constant-factor comparison (1/8)min{m², m/ε²} ≤ N(m, ε) ≤ 5min{m², m/ε²}, with the transition occurring around ε ≍ m−1/2.
At zero distortion, the complex case has an exact answer: N(m, 0) = m² for every m ≥ 1. The paper obtains this endpoint through a separate construction based on Hermitian matrices.
A problem framed through matrices
The objects being analyzed are finite function spaces generated by unit-norm tight frames over real or complex subspaces.
To study the sampling condition, the paper rewrites the weighted Marcinkiewicz–Zygmund inequality as a Loewner-order bound on a discrete Gram matrix M. In ordinary terms, this turns the sampling requirement into a structured comparison between matrices.
The lower-bound machinery uses a trace-variance inequality for weighted subframes of unit-norm tight frames. This lets the analysis derive obstructions from specially chosen frame-generated spaces that are difficult to discretize with few points.
Special constructions sharpen the picture
One family examined is the equiangular tight frame, or ETF, a special kind of tight frame. For any unit-norm tight frame with N vectors in an m-dimensional space, the centered-projector spectral gap obeys γΦ ≤ N(m − 1)/[m(N − 1)], and equality holds exactly for ETFs. In the paper’s analysis, ETFs are therefore extremal for this gap bound when they exist.
A named construction gives a concrete near-maximal example in some dimensions. When m − 1 is a prime power, the Singer construction produces an ETF with m = q + 1 and N = q² + q + 1 = m² − m + 1, alongside a corresponding lower bound on the number of points needed.
The strongest ETF statement is conditional. If a maximal complex ETF exists in C^m, it has N = m² and yields the lower bound n ≥ max{m, m²(1 − ε²)/(1 + mε²)}. Whether such maximal complex ETFs exist in every dimension is left open by Zauner’s conjecture, which the paper says remains unresolved.
The all-dimension construction behind the main theorem comes from the edges of a complete graph. Its centered-projector gap satisfies γΦ ≥ 1/2, with equality for m ≥ 3, and the weighted MZ condition becomes equivalent to spectral sparsification of that graph: selecting and weighting fewer edges while preserving the relevant spectrum.
What the bounds say about least squares
The paper also translates the sampling results into a statement about weighted least-squares calculations. For the ETF and complete-graph spaces, when m ≤ n ≤ N/2 and the normal matrix M is positive definite, it gives a lower bound on the scale-invariant distortion, ε⋆(M)² ≥ (N − n)/(N + βn). Here β is N − m for the ETF space and m for the graph space. The same result gives a certified iteration lower bound, niter(M) ≥ ⌈2 log(δ/2)/log(m/(24n))⌉, for 0 < δ < 1.
For any m-dimensional function space and any integer n > m, a constructive result supplies at most n points whose normal matrix meets the upper certificate niter(M) ≤ ⌈2 log(δ/2)/log(m/n)⌉, again for 0 < δ < 1. These are condition-number-based certificates used with LSQR, not guarantees that every actual run will take that many iterations.
The arithmetic message is more modest than simply saying that more points are better. If matrix-vector cost grows like nα for α > 0, the modeled cost factor xα/log x, with x = n/m > 1, is minimized at x = exp(1/α). The paper therefore interprets the trade-off as favoring a small oversampling factor, although extra evaluation, acquisition and construction costs can change the preferred choice.
A worst-case result, not a universal sample count
The bounds concern a supremum over m-dimensional spaces and specified frame-generated examples. They do not say that every function space requires the worst-case number of points; more structured spaces may admit perfect discretization. Nor do they establish maximal ETF existence in every dimension or show that actual LSQR runs must use the lower-bounded number of iterations.
The document is an arXiv version 1 preprint dated 26 August 2026. The supplied acknowledgments thank Matthew Fickus and mention an AI interaction, but identify no funding source.
Paper data and sources
Original title: Required Number of Points in $L_2$ Marcinkiewicz-Zygmund Inequalities
Authors: Felix Bartel
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text