Rapidly computing sparse Legendre expansions via sparse Fourier transforms

DOI10.1007/s11075-016-0184-xzbMath1365.65034arXiv1508.04758OpenAlexW2963520188MaRDI QIDQ521921

Hyejin Kim, Xianfeng Hu, Mark A. Iwen

Publication date: 12 April 2017

Published in: Numerical Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.04758

zbMATH Keywords

interpolationalgorithmChebyshev polynomialsfast Fourier transformsparse approximationLegendre polynomialscompressive sensingreal functionbest-basis approximationIserles transformsparse Fourier transforms

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Approximation by polynomials (41A10) Algorithms for approximation of functions (65D15) Approximation to limiting values (summation of series, etc.) (40A25)

Related Items (6)

Nonlinear approximation in bounded orthonormal product bases ⋮ A new class of fully discrete sparse Fourier transforms: faster stable implementations with guarantees ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity ⋮ Sparse fast DCT for vectors with one-block support ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time

Uses Software

• FFTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A multiscale sub-linear time Fourier algorithm for noisy data
• Reconstruction of sparse Legendre and Gegenbauer expansions
• A mathematical introduction to compressive sensing
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Convergence rates of best \(N\)-term Galerkin approximations for a class of elliptic SPDEs
• A fast and simple algorithm for the computation of Legendre coefficients
• Combinatorial sublinear-time Fourier algorithms
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Representation of sparse Legendre expansions
• Improved sparse Fourier approximation results: Faster implementations and stronger guarantees
• Sparse polynomial interpolation in Chebyshev bases
• Empirical evaluation of a sub-linear time sparse DFT algorithm
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• $\mathcal{O}(1)$ Computation of Legendre Polynomials and Gauss--Legendre Nodes and Weights for Parallel Computing
• ANALYTIC REGULARITY AND POLYNOMIAL APPROXIMATION OF PARAMETRIC AND STOCHASTIC ELLIPTIC PDE'S
• A Remark on Stirling's Formula
• Near-optimal sparse fourier representations via sampling
• Spectral Methods for Uncertainty Quantification
• Learning Decision Trees Using the Fourier Spectrum
• Randomized Interpolation and Approximation of Sparse Polynomials
• A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators
• On the convergence rates of Legendre approximation
• Nearly optimal sparse fourier transform
• AN EXAMPLE IN THE THEORY OF THE SPECTRUM OF A FUNCTION

This page was built for publication: Rapidly computing sparse Legendre expansions via sparse Fourier transforms