Command Palette
Search for a command to run...
REQUIRED NUMBER OF POINTS IN L_2 MARCINKIEWICZ–ZYGMUND INEQUALITIES
REQUIRED NUMBER OF POINTS IN L_2 MARCINKIEWICZ–ZYGMUND INEQUALITIES
Abstract
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 < ε < 1 is the relative distortion, this number is Θ(min{m^2, m/ε^2}), 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.
One-sentence Summary
The authors determine, up to absolute constants, the worst-case number of point evaluations required for a weighted L_2 Marcinkiewicz–Zygmund inequality on an m-dimensional complex function space, showing that this number is Θ(min{m^2, m/ε^2}) for relative distortion 0 < ε < 1 and exactly m^2 for exact discretization; they construct matching lower-bound function spaces via trace-variance inequalities for weighted subframes of unit-norm tight frames and derive consequences for weighted least-squares conditioning and LSQR.