Constructive subsampling of finite frames with applications in optimal function recovery
Preprint
Abstract
In this paper we present new constructive methods, random and deterministic, for the efficient subsampling of finite frames in $\mathbb C^m$. Based on a suitable random subsampling strategy, we are able to extract from any given frame with bounds $0<A\le B<\infty$ (and condition $B/A$) a similarly conditioned reweighted subframe consisting of merely $\mathcal{O}(m\log m)$ elements. Further, utilizing a deterministic subsampling method based on principles developed by Batson, Spielman, and Srivastava to control the spectrum of sums of Hermitian rank-1 matrices, we are able to reduce the number of elements to $\mathcal{O}(m)$ (with a constant close to one). By controlling the weights via a preconditioning step, we can, in addition, preserve the lower frame bound in the unweighted case. This permits the derivation of new quasi-optimal unweighted (left) Marcinkiewicz-Zygmund inequalities for $L_2(D,\nu)$ with constructible node sets of size $\mathcal{O}(m)$ for $m$-dimensional subspaces of bounded functions. Those can be applied e.g. for (plain) least-squares sampling reconstruction of functions, where we obtain new quasi-optimal results avoiding the Kadison-Singer theorem. Numerical experiments indicate the applicability of our results.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- A sharp upper bound for sampling numbers in L2Applied and Computational Harmonic Analysis, 2022
- Towards Optimal Sampling for Learning Sparse Approximations in High Dimensions2022
- Approximation of functions with small mixed smoothness in the uniform normJournal of Approximation Theory, 2022
- Worst-case Recovery Guarantees for Least Squares Approximation Using Random SamplesConstructive Approximation, 2021
- A New Upper Bound for Sampling NumbersFoundations of Computational Mathematics, 2021
- Function Values Are Enough for $L_2$-ApproximationFoundations of Computational Mathematics, 2020
- Mercer’s Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSsConstructive Approximation, 2012
- Auto-tuning unit norm framesApplied and Computational Harmonic Analysis, 2012
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- On the stability of the hyperbolic cross discrete Fourier transformNumerische Mathematik, 2010