Sparse Legendre expansions via \(\ell_1\)-minimization

DOI10.1016/j.jat.2012.01.008zbMath1239.65018arXiv1003.0251OpenAlexW2141454789MaRDI QIDQ420755

Holger Rauhut, Rachel Ward

Publication date: 23 May 2012

Published in: Journal of Approximation Theory (Search for Journal in Brave)

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

zbMATH Keywords

random samplesLegendre polynomialsparse approximationorthogonal polynomialJacobi polynomialcompressive sensingsparse recoveryrestricted isometry propertyChebyshev measure\(\ell_1\)-minimizationLegendre matrixsparse Legendre expansion

Mathematics Subject Classification ID

Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.) (33C45) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Numerical interpolation (65D05) Computation of special functions and constants, construction of tables (65D20) Sampling theory in information and communication theory (94A20)

Related Items

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method, Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data, Randomized numerical linear algebra: Foundations and algorithms, A sparse grid stochastic collocation method for elliptic interface problems with random input, On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization, A General Framework of Rotational Sparse Approximation in Uncertainty Quantification, Compressive Sensing with Cross-Validation and Stop-Sampling for Sparse Polynomial Chaos Expansions, Compressive Sensing with Redundant Dictionaries and Structured Measurements, Sensor Placement Sensitivity and Robust Reconstruction of Wave Dynamics from Multiple Sensors, Constructing Surrogate Models of Complex Systems with Enhanced Sparsity: Quantifying the Influence of Conformational Uncertainty in Biomolecular Solvation, A Survey of Compressed Sensing, Reconstruction of sparse Legendre and Gegenbauer expansions, Infinite-dimensional compressed sensing and function interpolation, Extracting Sparse High-Dimensional Dynamics from Limited Data, Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations, A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions, Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies, The restricted isometry property for time-frequency structured random matrices, Polynomial chaos expansions for dependent random variables, Adaptive weighted least-squares polynomial chaos expansion with basis adaptivity and sequential adaptive sampling, Stable Image Reconstruction Using Transformed Total Variation Minimization, The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials, On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals, A survey of unsupervised learning methods for high-dimensional uncertainty quantification in black-box-type problems, A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems, Nonlinear approximation in bounded orthonormal product bases, Adaptive group Lasso neural network models for functions of few variables and time-dependent data, Sampling numbers of smoothness classes via \(\ell^1\)-minimization, Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations, Error guarantees for least squares approximation with noisy samples in domain adaptation, A novel sparse polynomial chaos expansion technique with high adaptiveness for surrogate modelling, Analysis of sparse recovery for Legendre expansions using envelope bound, A massively parallel implementation of multilevel Monte Carlo for finite element models, Restricted isometries for partial random circulant matrices, A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions, Basis adaptive sample efficient polynomial chaos (BASE-PC), A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions, Importance sampling in signal processing applications, Least Squares Approximation of Polynomial Chaos Expansions With Optimized Grid Points, Enhanced total variation minimization for stable image reconstruction, Comparison of the performance and reliability between improved sampling strategies for polynomial chaos expansion, Sparse Approximation using $\ell_1-\ell_2$ Minimization and Its Application to Stochastic Collocation, Interpolation via weighted \(\ell_{1}\) minimization, Polynomial approximation via compressed sensing of high-dimensional functions on lower sets, Stochastic Collocation Methods via $\ell_1$ Minimization Using Randomized Quadratures, A Christoffel function weighted least squares algorithm for collocation approximations, Sparse polynomial interpolation in Chebyshev bases, Stochastic Collocation vial₁-Minimisation on Low Discrepancy Point Sets with Application to Uncertainty Quantification, Compressed Sensing with Sparse Corruptions: Fault-Tolerant Sparse Collocation Approximations, Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification, Compressive isogeometric analysis, Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials, Compressed sensing with preconditioning for sparse recovery with subsampled matrices of Slepian prolate functions, Adaptive sparse polynomial dimensional decomposition for derivative-based sensitivity, Data assimilation for models with parametric uncertainty, Extracting Structured Dynamical Systems Using Sparse Optimization With Very Few Samples, Towards optimal sampling for learning sparse approximation in high dimensions, Sparse sums with bases of Chebyshev polynomials of the third and fourth kind, Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression, Sequential Design of Experiment for Sparse Polynomial Chaos Expansions, Sparse polynomial chaos expansions via compressed sensing and D-optimal design, A preconditioning approach for improved estimation of sparse polynomial chaos expansions, A data-driven framework for sparsity-enhanced surrogates with arbitrary mutually dependent randomness, An efficient adaptive forward-backward selection method for sparse polynomial chaos expansion, Worst-case recovery guarantees for least squares approximation using random samples, Generalized sampling and infinite-dimensional compressed sensing, Sparse signal recovery using a new class of random matrices, Rapidly computing sparse Legendre expansions via sparse Fourier transforms, How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings, Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization, Sparse identification of nonlinear dynamical systems via reweighted \(\ell_1\)-regularized least squares, Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables, A generalized multi-fidelity simulation method using sparse polynomial chaos expansion, Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection, Enhancing sparsity of Hermite polynomial expansions by iterative rotations, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs, The stochastic properties of \(\ell^1\)-regularized spherical Gaussian fields, Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time, A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs, Accelerating the Bayesian inference of inverse problems by using data-driven compressive sensing method based on proper orthogonal decomposition, Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids, Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements, Sparse reconstruction with multiple Walsh matrices, Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark, Stochastic Collocation Algorithms Using $l_1$-Minimization for Bayesian Solution of Inverse Problems, GenMod: a generative modeling approach for spectral representation of PDEs with random inputs, Generalization bounds for sparse random feature expansions, Orthogonal one step greedy procedure for heteroscedastic linear models, A Generalized Sampling and Preconditioning Scheme for Sparse Approximation of Polynomial Chaos Expansions

Uses Software

• PDCO
• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A non-adapted sparse approximation of PDEs with stochastic inputs
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• New bounds on the restricted isometry constant \(\delta _{2k}\)
• CMB data analysis and sparsity
• Iterative hard thresholding for compressed sensing
• Random sampling of sparse trigonometric polynomials
• The restricted isometry property and its implications for compressed sensing
• A note on guaranteed sparse recovery via \(\ell_1\)-minimization
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• A simple proof of the restricted isometry property for random matrices
• FFTs for the 2-sphere-improvements and variations
• Fast algorithms for discrete polynomial transforms on arbitrary grids
• Fast algorithms for spherical harmonic expansions. II.
• ANALYTIC REGULARITY AND POLYNOMIAL APPROXIMATION OF PARAMETRIC AND STOCHASTIC ELLIPTIC PDE'S
• Compressed sensing and best 𝑘-term approximation
• On sparse reconstruction from Fourier and Gaussian measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Compressed Sensing and Redundant Dictionaries
• Atomic Decomposition by Basis Pursuit
• Fast algorithms for discrete polynomial transforms
• Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
• Dictionary Preconditioning for Greedy Algorithms
• Compressive Sensing
• New Bounds for Restricted Isometry Constants
• Sparsity and incoherence in compressive sampling
• On the Complexity of Mumford–Shah-Type Regularization, Viewed as a Relaxed Sparsity Constraint
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Adaptive greedy approximations