Interpolation via weighted _1 minimization
From MaRDI portal
Publication:905907
Abstract: Functions of interest are often smooth and sparse in some sense, and both priors should be taken into account when interpolating sampled data. Classical linear interpolation methods are effective under strong regularity assumptions, but cannot incorporate nonlinear sparsity structure. At the same time, nonlinear methods such as minimization can reconstruct sparse functions from very few samples, but do not necessarily encourage smoothness. Here we show that weighted minimization effectively merges the two approaches, promoting both sparsity and smoothness in reconstruction. More precisely, we provide specific choices of weights in the objective to achieve rates for functions with coefficient sequences in weighted spaces, . We consider the implications of these results for spherical harmonic and polynomial interpolation, in the univariate and multivariate setting. Along the way, we extend concepts from compressive sensing such as the restricted isometry property and null space property to accommodate weighted sparse expansions; these developments should be of independent interest in the study of structured sparse approximations and continuous-time compressive sensing problems.
In practice, one has often to interpolate functions which are smooth as well as sparse in some sense. In this excellent paper, the authors merge classical smoothness-based interpolation methods with modern sparsity constraints and nonlinear reconstruction methods. For a bounded domain \(D\), let \(\psi_j:\, D \to {\mathbb C}\) \((j \in \Lambda)\) be orthonormal functions with finite index set \(\Lambda\), \(|\Lambda| = N\). For given sampling points \(t_{\ell}\in D\) \((\ell = 1,\ldots,m)\) and \(f=\sum_{j\in \Lambda} x_j\,\psi_j\), let \(y = (f(t_{\ell}))_{\ell =1}^m\) and let \(A\) be the sampling matrix with the entries \(A_{\ell,j} = \psi_j(t_{\ell})\) \((\ell =1,\ldots,m;\,j\in \Lambda)\). For interpolation, the authors consider the function \(f^{\sharp} = \sum_{j\in \Lambda} x_j^{\sharp}\,\psi_j\), whose coefficient vector \(x^{\sharp}\) is the solution of the \textit{weighted} \(\ell_1\) \textit{minimization problem} \[ \min \|z\|_{\omega,1}\quad {\mathrm{subject to}}\quad \|Az - y\|_2 \leq \eta \] with the weighted \(\ell_1\) norm \(\|z\|_{\omega,1} = \sum_{j\in \Lambda} \omega_j\,|z_j|\) and convenient weights \(\omega_j \geq 1\). Using the new concepts of weighted null space property and weighted restricted isometry property of the sampling matrix \(A\), the authors prove general interpolation theorems. Corresponding error estimates of \(f -f^{\sharp}\) in \(L_{\infty}\) resp. \(L_2\) norm are given. In several examples and numerical tests, this theory is applied to spherical harmonic interpolation and tensorized polynomial interpolation (with Chebyshev resp. Legendre polynomials).
Recommendations
- Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
- Infinite-dimensional compressed sensing and function interpolation
- Robust recovery of a kind of weighted l1-minimization without noise level
- Weighted splines as optimal interpolants
- New conditions on stable recovery of weighted sparse signals via weighted l₁ minimization
Cites work
- A Bennett concentration inequality and its application to suprema of empirical processes
- A mathematical introduction to compressive sensing
- A short note on compressed sensing with partially known signal support
- A simple proof of the restricted isometry property for random matrices
- A weighted _1-minimization approach for sparse polynomial chaos expansions
- An upper bound on Jacobi polynomials
- Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's
- Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
- Approximation in Sobolev spaces by kernel expansions
- Compressed sensing and best \(k\)-term approximation
- Compressive sensing and structured random matrices
- Convergence rates of best \(N\)-term Galerkin approximations for a class of elliptic SPDEs
- Decoding by Linear Programming
- scientific article; zbMATH DE number 432614 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
- Iterative hard thresholding for compressed sensing
- Lectures on Gaussian Processes
- Model-Based Compressive Sensing
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- On approximate recovery of functions with bounded mixed derivative
- On sparse reconstruction from Fourier and Gaussian measurements
- On the stability and accuracy of least squares approximations
- Recovering Compressively Sampled Signals Using Partial Support Information
- Restricted isometry of Fourier matrices and list decodability of random linear codes
- Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in H^
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- Sparse Legendre expansions via _1-minimization
- Spectral Methods for Uncertainty Quantification
- Stability Results for Scattered Data Interpolation by Trigonometric Polynomials
- Suprema of chaos processes and the restricted isometry property
- Weighted eigenfunction estimates with applications to compressed sensing
Cited in
(70)- Improved bounds for sparse recovery from subsampled random convolutions
- Infinite-dimensional compressed sensing and function interpolation
- Compressed sensing of data with a known distribution
- Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\)
- Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\)
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Sparse approximation of multivariate functions from small datasets via weighted orthogonal matching pursuit
- Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids
- Generalization bounds for sparse random feature expansions
- Recovery guarantees for polynomial coefficients from weakly dependent data with outliers
- A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations
- Worst-case recovery guarantees for least squares approximation using random samples
- Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements
- New conditions on stable recovery of weighted sparse signals via weighted l₁ minimization
- Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
- Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension
- On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
- Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property
- Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
- 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)
- Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
- Breaking the coherence barrier: a new theory for compressed sensing
- The Discrete Empirical Interpolation Method: Canonical Structure and Formulation in Weighted Inner Product Spaces
- Accelerating stochastic collocation methods for partial differential equations with random input data
- Reconstruction of sparse Legendre and Gegenbauer expansions
- Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation
- Compressive sensing with redundant dictionaries and structured measurements
- Extracting Sparse High-Dimensional Dynamics from Limited Data
- A theoretical study of compressed solving for advection-diffusion-reaction problems
- Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
- Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations
- Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification
- Optimal feedback law recovery by gradient-augmented sparse polynomial regression
- Generalization error of minimum weighted norm and kernel interpolation
- The gap between theory and practice in function approximation with deep neural networks
- Robust width: a characterization of uniformly stable and robust compressed sensing
- Convergence bounds for empirical nonlinear least-squares
- Sufficient conditions on stable reconstruction of weighted problem
- A general framework of rotational sparse approximation in uncertainty quantification
- The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials
- Robust recovery of a kind of weighted l1-minimization without noise level
- Extracting Structured Dynamical Systems Using Sparse Optimization With Very Few Samples
- A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
- A mixed ℓ1 regularization approach for sparse simultaneous approximation of parameterized PDEs
- Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property
- On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
- Minimum norm interpolation in the \(\ell_1(\mathbb{N})\) space
- Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method
- Randomized numerical linear algebra: Foundations and algorithms
- Sampling numbers of smoothness classes via \(\ell^1\)-minimization
- Analysis of sparse recovery for Legendre expansions using envelope bound
- Contractive symmetric matrix completion problems related to graphs
- Stable recovery of weighted sparse signals from phaseless measurements via weighted l1 minimization
- Towards optimal sampling for learning sparse approximation in high dimensions
- Tractability of sampling recovery on unweighted function classes
- Sample complexity bounds for the local convergence of least squares approximation
- Nonlinear frames and sparse reconstructions in Banach spaces
- An investigation of alternative methods for the inference of probabilistic-fuzzy systems
- Optimal sampling for least-squares approximation
- Weighted sparsity and sparse tensor networks for least squares approximation
- Sparse spectral methods for solving high-dimensional and multiscale elliptic PDEs
- The greedy side of the LASSO: new algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit
- Optimal approximation of infinite-dimensional holomorphic functions. II: Recovery from i.i.d. pointwise samples
- Recovery conditions in weighted sparse phase retrieval via weighted \(\ell_q\) (\(0<q\le 1\)) minimization
- Approximation of functions: optimal sampling and complexity
- Surrogate models for diffusion on graphs via sparse polynomials
- Enhancing sparsity of Hermite polynomial expansions by iterative rotations
- Sparse sampling recovery by greedy algorithms
This page was built for publication: Interpolation via weighted \(\ell_{1}\) minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905907)
