Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
DOI10.1007/s00211-021-01200-zzbMath1483.65030arXiv1909.09564OpenAlexW3167230891MaRDI QIDQ2038427
Bosu Choi, Toni Volkmer, Mark A. Iwen
Publication date: 6 July 2021
Published in: Numerische Mathematik (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.09564
sparse approximationcompressive sensingfunction learninghigh-dimensional function approximationsparse Fourier transformssublinear-time algorithms
Algorithms for approximation of functions (65D15) Numerical methods for trigonometric approximation and interpolation (65T40) Approximation algorithms (68W25) Randomized algorithms (68W20) Numerical approximation of high-dimensional functions; sparse grids (65D40)
Related Items (4)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- A mathematical introduction to compressive sensing
- Sparse Legendre expansions via \(\ell_1\)-minimization
- Rapidly computing sparse Legendre expansions via sparse Fourier transforms
- Sparse grid quadrature in high dimensions with applications in finance and insurance
- Approximation of functions of few variables in high dimensions
- The smoothing effect of the ANOVA decomposition
- Random sampling of sparse trigonometric polynomials
- Tractability of multivariate problems. Volume I: Linear information
- Combinatorial sublinear-time Fourier algorithms
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- The jackknife estimate of variance
- Improved approximation guarantees for sublinear-time Fourier algorithms
- Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
- A deterministic sparse FFT for functions with structured Fourier sparsity
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Sparse fast DCT for vectors with one-block support
- Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
- Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
- Explicit universal sampling sets in finite vector spaces
- A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees
- Empirical evaluation of a sub-linear time sparse DFT algorithm
- Karhunen-Loève approximation of random fields by generalized fast multipole methods
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
- Compressed sensing and best 𝑘-term approximation
- Numerical Methods in Scientific Computing, Volume I
- On decompositions of multivariate functions
- Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
- Randomized interpolation and approximation of sparse polynomials stPreliminary version
- Dimension-independent Sparse Fourier Transform
- Sparse grids
- Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time
- Kronecker Compressive Sensing
- Sparse Spectral Approximations of High-Dimensional Problems Based on Hyperbolic Cross
This page was built for publication: Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
