Interpolation via weighted \(\ell_{1}\) minimization

DOI10.1016/J.ACHA.2015.02.003zbMath1333.41003arXiv1308.0759OpenAlexW2963862882MaRDI QIDQ905907

Rachel Ward, Holger Rauhut

Publication date: 28 January 2016

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

interpolationerror estimatescompressive sensingweighted \(\ell_1\)-minimizationbounded orthonormal systemsampling matrixsmooth and sparse functionsweighted null space propertyweighted restricted isometry property

Mathematics Subject Classification ID

Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Sampling theory in information and communication theory (94A20)

Related Items (55)

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method ⋮ Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data ⋮ Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension ⋮ Convergence bounds for empirical nonlinear least-squares ⋮ Sufficient conditions on stable reconstruction of weighted problem ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Improved bounds for sparse recovery from subsampled random convolutions ⋮ On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization ⋮ A General Framework of Rotational Sparse Approximation in Uncertainty Quantification ⋮ Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ Accelerating Stochastic Collocation Methods for Partial Differential Equations with Random Input Data ⋮ Reconstruction of sparse Legendre and Gegenbauer expansions ⋮ Stable and robust $\ell_p$-constrained compressive sensing recovery via robust width property ⋮ Infinite-dimensional compressed sensing and function interpolation ⋮ Extracting Sparse High-Dimensional Dynamics from Limited Data ⋮ Recovery analysis for weighted \(\ell_{1}\)-minimization using the null space property ⋮ Compressed sensing of data with a known distribution ⋮ The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials ⋮ Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class ⋮ A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems ⋮ Robust recovery of a kind of weighted l1-minimization without noise level ⋮ Sampling numbers of smoothness classes via \(\ell^1\)-minimization ⋮ Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations ⋮ Analysis of sparse recovery for Legendre expansions using envelope bound ⋮ Contractive symmetric matrix completion problems related to graphs ⋮ A gradient enhanced \(\ell_{1}\)-minimization for sparse approximation of polynomial chaos expansions ⋮ Unnamed Item ⋮ Correcting for unknown errors in sparse high-dimensional function approximation ⋮ Basis adaptive sample efficient polynomial chaos (BASE-PC) ⋮ Stable recovery of weighted sparse signals from phaseless measurements via weighted l₁ minimization ⋮ Polynomial approximation via compressed sensing of high-dimensional functions on lower sets ⋮ BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING ⋮ Compressed Sensing with Sparse Corruptions: Fault-Tolerant Sparse Collocation Approximations ⋮ Sliced-Inverse-Regression--Aided Rotated Compressive Sensing Method for Uncertainty Quantification ⋮ 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 ⋮ Extracting Structured Dynamical Systems Using Sparse Optimization With Very Few Samples ⋮ Towards optimal sampling for learning sparse approximation in high dimensions ⋮ Recovery analysis for weighted mixed \(\ell_2 / \ell_p\) minimization with \(0 < p \leq 1\) ⋮ Worst-case recovery guarantees for least squares approximation using random samples ⋮ Nonlinear frames and sparse reconstructions in Banach spaces ⋮ A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials ⋮ Solving structured nonsmooth convex optimization with complexity \(\mathcal {O}(\varepsilon ^{-1/2})\) ⋮ Enhancing sparsity of Hermite polynomial expansions by iterative rotations ⋮ Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs ⋮ A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs ⋮ Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation ⋮ 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 ⋮ New conditions on stable recovery of weighted sparse signals via weighted \(l_1\) minimization ⋮ Generalization Error of Minimum Weighted Norm and Kernel Interpolation ⋮ The Gap between Theory and Practice in Function Approximation with Deep Neural Networks ⋮ Generalization bounds for sparse random feature expansions ⋮ Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing ⋮ On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \(H^\gamma\)
• A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions
• A mathematical introduction to compressive sensing
• On the stability and accuracy of least squares approximations
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Convergence rates of best \(N\)-term Galerkin approximations for a class of elliptic SPDEs
• Iterative hard thresholding for compressed sensing
• A simple proof of the restricted isometry property for random matrices
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• A Bennett concentration inequality and its application to suprema of empirical processes
• Approximation in Sobolev spaces by kernel expansions
• A short note on compressed sensing with partially known signal support
• On approximate recovery of functions with bounded mixed derivative
• An upper bound on Jacobi polynomials
• Suprema of Chaos Processes and the Restricted Isometry Property
• ANALYTIC REGULARITY AND POLYNOMIAL APPROXIMATION OF PARAMETRIC AND STOCHASTIC ELLIPTIC PDE'S
• Compressed sensing and best 𝑘-term approximation
• Lectures on Gaussian Processes
• On sparse reconstruction from Fourier and Gaussian measurements
• Stability Results for Scattered Data Interpolation by Trigonometric Polynomials
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Spectral Methods for Uncertainty Quantification
• Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
• Weighted Eigenfunction Estimates with Applications to Compressed Sensing
• Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
• Recovering Compressively Sampled Signals Using Partial Support Information
• Model-Based Compressive Sensing
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

This page was built for publication: Interpolation via weighted \(\ell_{1}\) minimization