Infinite-dimensional ^1 minimization and function approximation from pointwise data
From MaRDI portal
Publication:2359680
Abstract: We consider the problem of approximating a smooth function from finitely-many pointwise samples using minimization techniques. In the first part of this paper, we introduce an infinite-dimensional approach to this problem. Three advantages of this approach are as follows. First, it provides interpolatory approximations in the absence of noise. Second, it does not require extit{a priori} bounds on the expansion tail in order to be implemented. In particular, the truncation strategy we introduce as part of this framework is independent of the function being approximated, provided the function has sufficient regularity. Third, it allows one to explain the key role weights play in the minimization; namely, that of regularizing the problem and removing aliasing phenomena. In the second part of this paper we present a worst-case error analysis for this approach. We provide a general recipe for analyzing this technique for arbitrary deterministic sets of points. Finally, we use this tool to show that weighted minimization with Jacobi polynomials leads to an optimal method for approximating smooth, one-dimensional functions from scattered data.
It is known that as dimension increases, smooth multivariate functions are increasingly well represented by their best k-term approximation in certain orthogonal expansions. Therefore, in this paper, an infinite dimensional approach has been introduced to discuss the problem of approximating a smooth function from finitely many pointwise samples using \(\ell^{1}\)-minimization techniques. This approach provides interpolatory approximation in the absence of noise and does not require a priori bounds on the expansion tail for implementation. Also, it does not depend on the approximated function, if the function has sufficient regularity. A worst-case error analysis has been discussed. Moreover, it has been shown that weighted \(\ell^{1}\)-minimization with Jacobi polynomials leads to an optimal method for approximating smooth, one-dimensional functions from scattered data.
Recommendations
- Interpolation via weighted \(\ell_{1}\) minimization
- An adaptive algorithm for weighted approximation of singular functions over \(\mathbb{R}\)
- Infinite-dimensional compressed sensing and function interpolation
- A weighted _1-minimization approach for sparse polynomial chaos expansions
- Smolyak's algorithm for weighted \(L_1\)-approximation of multivariate functions with bounded \(r\)th mixed derivatives over \(\mathbb R^d\)
Cites work
- A compressed sensing approach for partial differential equations with random input data
- A generalized sampling theorem for stable reconstructions in arbitrary bases
- A mapped polynomial method for high-accuracy approximations on arbitrary grids
- A mathematical introduction to compressive sensing
- A minimum Sobolev norm technique for the numerical discretization of PDEs
- A non-adapted sparse approximation of PDEs with stochastic inputs
- A weighted _1-minimization approach for sparse polynomial chaos expansions
- Analysis of discrete L^2 projection on polynomial spaces with random evaluations
- Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
- Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's
- Beyond consistent reconstructions: optimality and sharp bounds for generalized sampling, and application to the uniform resampling problem
- Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies
- Convergence rates of best \(N\)-term Galerkin approximations for a class of elliptic SPDEs
- Exponentially-convergent strategies for defeating the Runge phenomenon for the approximation of non-periodic functions. I: Single-interval schemes
- Generalized sampling and infinite-dimensional compressed sensing
- scientific article; zbMATH DE number 3477793 (Why is no real title available?)
- Impossibility of fast stable approximation of analytic functions from equispaced samples
- Infinite-dimensional compressed sensing and function interpolation
- Interpolation via weighted \(\ell_{1}\) minimization
- Minimum Sobolev norm interpolation with trigonometric polynomials on the torus
- On the numerical stability of Fourier extensions
- On the stability and accuracy of least squares approximations
- Optimal sampling rates for approximating analytic functions from pointwise samples
- Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
- Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations
- Scattered Data Approximation
- Sparse Legendre expansions via _1-minimization
- Spectral Methods
- Spectral Methods for Uncertainty Quantification
- Stable extrapolation of analytic functions
- Stochastic collocation algorithms using _1-minimization
- The Wiener--Askey Polynomial Chaos for Stochastic Differential Equations
Cited in
(18)- Infinite-dimensional compressed sensing and function interpolation
- Sparse polynomial chaos expansions via compressed sensing and D-optimal design
- 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
- Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
- Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
- On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
- A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions
- Correcting for unknown errors in sparse high-dimensional function approximation
- Basis adaptive sample efficient polynomial chaos (BASE-PC)
- Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations
- Robust recovery of a kind of weighted l1-minimization without noise level
- Generalized sampling and infinite-dimensional compressed sensing
- A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
- A mixed ℓ1 regularization approach for sparse simultaneous approximation of parameterized PDEs
- Towards optimal sampling for learning sparse approximation in high dimensions
- Surrogate models for diffusion on graphs via sparse polynomials
- Interpolation via weighted \(\ell_{1}\) minimization
This page was built for publication: Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359680)
