PaperlayerView exact revision on arXiv

Source-linked AI summary

Required Number of Points in $L_2$ Marcinkiewicz-Zygmund Inequalities

Felix Bartel

arXiv:2608.25886v1math.NA

TL;DR

The paper asks how many weighted point evaluations are required to discretize L2 norms in the worst case for m-dimensional complex function spaces. It develops tight-frame-based hard spaces and proves matching lower bounds, obtaining a Θ(min{m^2, m/ε^2}) worst-case rate and consequences for least-squares conditioning and LSQR estimates.

  • Problem

    The central question is whether some m-dimensional function spaces prevent reducing discretization distortion regardless of the chosen points and weights.

  • Method

    The paper constructs hard-to-discretize spaces from unit-norm tight frames and applies a trace-variance inequality to weighted subframes.

  • Results

    Θ(min{m^2, m/ε^2}) points are required up to absolute constants for 0 < ε < 1, exact discretization has worst-case value m^2, and ETF constructions strengthen some lower bounds.

  • Takeaways & Limitations

    The complete-graph edge frame supplies a hard construction in every dimension, while the bounds also inform weighted least-squares conditioning and standard LSQR iteration estimates.

  • Takeaways & Limitations

    The strongest trace-variance bound does not produce the exact value m^2 in every dimension, and the LSQR result is a lower bound on certified iteration counts rather than actual runs.

Abstract

from arXiv · show

We determine, up to absolute constants, the worst-case number of point evaluations required for a weighted $L_2$ Marcinkiewicz-Zygmund inequality for an $m$-dimensional complex function space. If $0<\varepsilon<1$ is the relative distortion, this number is $$Θ\Big(\min\Big\{m^2,\frac{m}{\varepsilon^2}\Big\}\Big),$$ and exact discretization has the sharp worst-case value $m^2$. While the upper bounds follow from recent constructions, our contribution is the construction of function spaces that are hard to discretize and yield matching lower bounds. We use a trace-variance inequality for weighted subframes of unit-norm tight frames. One such instance is the complete-graph edge frame, which yields a construction in every dimension. Singer equiangular tight frames improve the constant when $m-1$ is a prime power, while maximal equiangular tight frames give the strongest bound possible using our method whenever they exist. We also derive consequences for the conditioning of weighted least-squares systems and for standard condition-number-based iteration estimates when these systems are solved by LSQR.

1. Introduction

The paper studies worst-case weighted point-evaluation discretization for m-dimensional complex function spaces and proves that the distortion–sample trade-off is unavoidable. Hard spaces built from tight frames yield matching lower bounds, with consequences for weighted least squares and LSQR estimates.

  • Marcinkiewicz–Zygmund inequalities connect continuous L2 norms with finitely many weighted point evaluations and support approximation theory and weighted least-squares analysis.
  • The worst-case sampling complexity is the supremum over all m-dimensional complex function spaces, representing stable weighted norm discretization by point evaluations.
  • Structured spaces can achieve exact discretization with n = m, but the paper asks whether some spaces resist distortion reduction under every choice of points and weights.
  • Θ(min{m^2, m/ε^2}) points are necessary and sufficient up to absolute constants for 0 < ε < 1, while exact discretization has worst-case scale m^2.The phase transition occurs at ε ≍ m^-1/2: below it, m^2 points are necessary; above it, the lower bound has m/ε^2 behavior.
  • The lower bounds use trace variance for weighted subframes of unit-norm tight frames, with the complete-graph edge frame providing a construction in every dimension.For this frame, γΦ ≥ 1/2, with equality for m ≥ 3, and the MZ problem is equivalent to complete-graph spectral sparsification.
  • Singer ETFs improve the bound when m − 1 is a prime power, while maximal complex ETFs provide the strongest estimate obtainable from the trace-variance method when they exist.Singer ETFs have N = m^2 − m + 1 elements; maximal complex ETFs have N = m^2 elements, conditionally available in every dimension under Zauner’s conjecture.
  • For hard spaces, required sample counts appear in weighted least-squares conditioning and standard condition-number-based LSQR iteration estimates.The standard a priori iteration estimate may overstate actual LSQR iterations, which depend on the full spectrum and initial error.

2. Matrix formulation and the trace-variance obstruction

The paper converts weighted L2 MZ inequalities into weighted subframe conditions, then uses centered-projector trace variance to force large supports. A separate Hermitian-matrix construction establishes the exact complex endpoint m^2.

  • 2.1. MZ inequalities in terms of Gram matrices.: The discrete Gram matrix represents weighted point evaluations, and its rank immediately gives the universal lower bound n ≥ m for ε < 1.Nontrivial bounds require exploiting the geometry of rank-one evaluation matrices.
  • 2.2. Finite function spaces generated by tight frames.: A unit-norm tight frame generates an m-dimensional finite function space whose coefficient-to-function map is an isometry.The frame bound follows from taking the frame operator's trace.
  • 2.2. Finite function spaces generated by tight frames.: Weighted L2 MZ inequalities on the generated space are equivalent to weighted subframe inequalities, with tightness corresponding to basis orthonormality.The unit-norm condition becomes constancy of the Christoffel function.
  • 2.3. Centered projectors and trace variance.: Centered projectors form traceless self-adjoint operators whose Gram matrix has the all-ones vector in its kernel, with γΦ measuring the remaining spectral gap.The condition γΦ > 0 means the only linear dependence among centered projectors is their zero sum.
  • 2.3. Centered projectors and trace variance.: The trace-variance argument shows that a small support forces excess variance because centered projectors cannot cancel sufficiently well.The rank argument first gives |J| ≥ m, while the Kantorovich inequality controls the operator's eigenvalue spread.
  • 2.3. Centered projectors and trace variance.: The general UNTF lower bound combines γΦ with the distortion constraint to produce a nontrivial support lower bound for weighted subframes.Rescaling MZ weights by m/N preserves the support size, so the frame result transfers directly to point discretization.
  • 2.4. The exact complex endpoint.: The trace-variance method gives sharp order but not the exact complex value m^2 in every dimension.This limitation motivates the separate endpoint construction.

3. ETF-based construction

Equiangular tight frames maximize the spectral obstruction in the trace-variance method, yielding stronger discretization lower bounds as their cardinality grows. Singer and maximal ETFs provide near-extremal constructions under their respective existence conditions.

  • 3. ETF-based construction: An ETF is a unit-norm tight frame whose pairwise inner-product magnitudes are constant; its centered projectors form a regular simplex.This symmetry makes ETFs natural candidates for maximizing the trace-variance obstruction.
  • 3.2. ETF-based lower bounds.: Any weighted MZ discretization of the ETF-generated space obeys the lower bound supplied by the ETF theorem.The bound applies for distortion 0 ≤ ε < 1.
  • 3.1. General ETF lower bound.: For fixed m and N, ETFs maximize γΦ and therefore maximize the lower bound furnished by the general UNTF theorem.The resulting ETF lower bound increases with N.
  • 3.1. General ETF lower bound.: The complex ETF cardinality satisfies N ≤ m^2, with maximal ETFs attaining N = m^2 when they exist.Maximal ETFs correspond, after scaling, to SIC-POVMs; existence in every dimension remains conjectural.
  • 3.4. Maximal ETFs.: Maximal ETFs yield the strongest bound available from this method whenever such frames exist.Conditional on Zauner's conjecture, maximal ETFs and the resulting bound hold in every dimension.
  • 3.3. Singer ETFs.: Singer difference sets produce ETFs with N = m^2 − m + 1 whenever m − 1 is a prime power.The construction uses m = q + 1 and N = q^2 + q + 1.
  • 3.3. Singer ETFs.: The Singer ETF gives a corresponding explicit lower bound for every dimension satisfying the prime-power condition.This is stated as the Singer-ETF bound for the associated function space.
  • 3.3. Singer ETFs.: Singer and maximal ETFs cover the two largest possible ETF cardinalities, although this gap fact is not needed for the lower bounds.The Singer–Zauner gap theorem excludes ETF cardinalities strictly between m^2 − m + 1 and m^2.

4. Graph-based construction

The complete-graph edge frame supplies hard-to-discretize function spaces in every dimension and connects weighted L2 MZ inequalities to spectral sparsification. Its centered-projector spectrum yields sharp support lower bounds, including exact discretization.

  • Construction: The complete-graph edge frame provides a uniform construction because quadratically large ETFs are not known in every dimension.The construction works over the complex field as well as the real field.
  • Frame spectrum: The centered edge-projector Gram matrix has eigenvalue 0 on the uniform coefficient direction, while its remaining eigenvalues are unchanged after centering.The spectrum follows from the line-graph analysis and identifies the gap used in the lower bound.
  • Lower bounds: The complete-graph lower bound complements the O(|V |/ε^2)-edge spectral-sparsification upper bound, while the frame argument applies beyond graph-specific settings.A graph-specific minimal-degree obstruction is stronger, but the presented mechanism is more general.
  • Graph correspondence: Weighted L2 MZ inequalities on the edge-defined space FK hold if and only if the corresponding weighted graph is a spectral sparsifier of the complete graph.The equivalence follows by identifying the frame projectors with the weighted graph Laplacian on the vertex subspace.
  • Lower bounds: At ε = 0, all m(m + 1)/2 edges are necessary, and this exact-discretization lower bound is sharp.For positive distortion, the complete-graph construction supplies the lower bound used in the paper’s worst-case result.

5. Stability and arithmetic cost of least-squares approximation

The paper relates weighted least-squares stability to the conditioning of the weighted design matrix and studies how oversampling affects certified LSQR iteration counts and arithmetic cost. The resulting trade-off favors limited oversampling when evaluation and construction costs grow with the sample count.

  • Least-squares solver: LSQR is applied to W^1/2Lĝ ≈ W^1/2y, avoiding explicit formation of the normal matrix while matching conjugate-gradient coefficient iterates in exact arithmetic.The method is more stable than explicitly solving the normal equations.
  • Stability: Weighted least-squares stability depends on the conditioning of W^1/2L, equivalently the normal matrix M.For M = L*WL, the relevant conditioning can be expressed through extreme eigenvalues or singular values.
  • Iteration estimates: Actual LSQR convergence may be faster because it depends on the full spectrum and the initial error, so the lower bound concerns the standard a priori certificate.The sharper distortion estimate remains valid beyond n ≤ N/2 and tends to zero as n approaches N.
  • Iteration estimates: For hard ETF and complete-graph spaces, every m ≤ n ≤ N/2 sample design obeys a lower bound on the certified iteration count.The bound is derived by converting support lower bounds into a distortion estimate for the normal matrix.
  • Arithmetic cost: Certified iteration counts improve only inverse-logarithmically with oversampling, whereas one LSQR step costs Cmv(n, m) for multiplications by L and L*.Depending on structure, Cmv ranges from order mn for dense matrices through order n log n for Fourier-type transforms to order n for sparse matrices.
  • Arithmetic cost: When Cmv(n, m) is proportional to n^α, the qualitative oversampling factor is minimized at x = exp(1/α), favoring a small oversampling factor.Function evaluations, data acquisition, and point construction can shift the optimum toward fewer samples.
  • Implementation trade-offs: Well-conditioned design construction can itself dominate the solve, so the preferred sample size depends on evaluation-matrix structure and sample-acquisition costs.The paper contrasts cubic-in-m initial frame subsampling with random Christoffel sampling and structured trigonometric constructions.
Loading 2608.25886v1…