Constructive subsampling of finite frames with applications in optimal function recovery
Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Multidimensional problems (41A63) Trigonometric approximation (42A10) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Sampling theory in information and communication theory (94A20)
The authors deal with the question of how to choose a well-conditioned subframe out of a given frame. Namely, they present new constructive methods, random and deterministic, for the efficient subsampling of finite frames in \(\mathbb{C}^m\), i.e., extracting a similarly conditioned reweighted subframe consisting of merely \(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, they reduce the number of elements to \(O(m)\) (with a constant close to one). By controlling the weights via a preconditioning step, they, 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, ν)\) with constructible node sets of size \(O(m)\) for \(m\)-dimensional subspaces of bounded functions. Those are applied for (plain) least-squares sampling reconstruction of functions, where the authors obtain new quasi-optimal results avoiding the Kadison-Singer theorem. Several numerical experiments indicate the applicability of the results.
- Sampling and recovery of multidimensional bandlimited functions via frames
- Sampling and reconstruction of signals in a reproducing kernel subspace of \(L^p(\mathbb R^d)\)
- Sampling-related frames in finite \(U\)-invariant subspaces
- scientific article; zbMATH DE number 640550
- On the reconstruction of signals by a finite number of samples
- Frames and sampling theorems in multiwavelet subspaces
- Sampling and Reconstructing Signals From a Union of Linear Subspaces
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- scientific article; zbMATH DE number 18186
- Optimal recovery of linear functionals on sets of finite dimension
- \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace
- A Class of Nonharmonic Fourier Series
- A note on sampling recovery of multivariate functions in the uniform norm
- A Singular Value Decomposition Updating Algorithm for Subspace Tracking
- Approximation of functions with small mixed smoothness in the uniform norm
- Auto-tuning unit norm frames
- Boosted optimal weighted least-squares
- Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
- Entropy numbers and Marcinkiewicz-type discretization
- Equal-norm tight frames with erasures
- Exponential frames on unbounded sets
- Finite frames. Theory and applications.
- Function values are enough for \(L_2\)-approximation
- Function values are enough for \(L_2\)-approximation. II
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 1077338 (Why is no real title available?)
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs
- Numerical Fourier analysis
- On optimal recovery in L₂
- On sampling discretization in \(L_2\)
- On the stability of the hyperbolic cross discrete Fourier transform
- Optimal weighted least-squares methods
- Pipage rounding, pessimistic estimators and matrix concentration
- Sampling from large matrices
- The Kadison-Singer problem in discrepancy theory.
- Twice-Ramanujan sparsifiers
- Updating the singular value decomposition
- User-friendly tail bounds for sums of random matrices
- Worst-case recovery guarantees for least squares approximation using random samples
- Sampling numbers of smoothness classes via \(\ell^1\)-minimization
- Error guarantees for least squares approximation with noisy samples in domain adaptation
- On the reconstruction of functions from values at subsampled quadrature points
- Randomized least-squares with minimal oversampling and interpolation in general spaces
- One-sided discretization inequalities and sampling recovery
- Exact discretization, tight frames and recovery via D-optimal designs
- Optimal sampling for least-squares approximation
- Sampling projections in the uniform norm
- Bounds for the sampling discretization error and their applications to the universal sampling discretization
- Weighted least-squares approximation with determinantal point processes and generalized volume sampling
- Measure transport via polynomial density surrogates
- Optimal approximation of infinite-dimensional holomorphic functions. II: Recovery from i.i.d. pointwise samples
- Optimal algorithms for numerical integration: recent results and open problems
- Kernel interpolation on generalized sparse grids
- Required Number of Points in L₂ Marcinkiewicz-Zygmund Inequalities
- Approximation of functions: optimal sampling and complexity
- Sparse grids vs. random points for high-dimensional polynomial approximation
- Simultaneous spatial-parametric collocation approximation for parametric PDEs with log-normal random inputs
- A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
- A higher order lattice-based method for high-dimensional numerical integration using periodization
This page was built for publication: Constructive subsampling of finite frames with applications in optimal function recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038824)
