Random sampling of sparse trigonometric polynomials

DOI10.1016/J.ACHA.2006.05.002zbMath1123.94004arXivmath/0512642OpenAlexW2067161429MaRDI QIDQ861807

Holger Rauhut

Publication date: 2 February 2007

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

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

zbMATH Keywords

random matricestrigonometric polynomialsset partitionsrandom samplingsparse recoverybasis pursuit\(\ell ^{1}\)-minimization

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Sampling theory in information and communication theory (94A20) Trigonometric polynomials, inequalities, extremal problems (42A05)

Related Items (50)

Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method ⋮ A Novel Compressed Sensing Scheme for Photoacoustic Tomography ⋮ A Survey of Compressed Sensing ⋮ Compressive Sensing in Acoustic Imaging ⋮ Cosparsity in Compressed Sensing ⋮ Sparse high-dimensional FFT based on rank-1 lattice sampling ⋮ Reconstruction of sparse Legendre and Gegenbauer expansions ⋮ A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing ⋮ Sparse approximate solution of fitting surface to scattered points by MLASSO model ⋮ Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces ⋮ The Recovery Guarantee for Orthogonal Matching Pursuit Method to Reconstruct Sparse Polynomials ⋮ Parameter estimation for nonincreasing exponential sums by Prony-like methods ⋮ Remote sensing via \(\ell_1\)-minimization ⋮ A multivariate generalization of Prony's method ⋮ Random sampling and reconstruction in reproducing kernel subspace of mixed Lebesgue spaces ⋮ Sampling and reconstruction of concentrated reproducing kernel signals in mixed Lebesgue spaces ⋮ Sparse Legendre expansions via \(\ell_1\)-minimization ⋮ Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms ⋮ Deterministic sampling of sparse trigonometric polynomials ⋮ Random sampling in multi-window quasi shift-invariant spaces ⋮ Compressive Sensing ⋮ Compressed Sensing with Nonlinear Fourier Atoms ⋮ Iterative thresholding algorithms ⋮ Uncertainty in time-frequency representations on finite Abelian groups and applications ⋮ Spark-level sparsity and the \(\ell_1\) tail minimization ⋮ A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials ⋮ Sparse approximation of fitting surface by elastic net ⋮ Sparse signal recovery using a new class of random matrices ⋮ Compressed sensing for quaternionic signals ⋮ On the properties of reachability, observability, controllability, and constructibility of discrete-time positive time-invariant linear systems with aperiodic choice of the sampling instants ⋮ Spectral compressive sensing ⋮ Spectral dynamics and regularization of incompletely and irregularly measured data ⋮ Meshless Hermite-HDMR finite difference method for high-dimensional Dirichlet problems ⋮ The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems ⋮ Sparsity in time-frequency representations ⋮ Sparse approximate solution of partial differential equations ⋮ Investigations of the effects of random sampling schemes on the stability of generalized sampling ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Greedy Algorithms for Optimal Measurements Selection in State Estimation Using Reduced Models ⋮ Robust group lasso: model and recoverability ⋮ How many Fourier samples are needed for real function reconstruction? ⋮ Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs ⋮ Random sampling and reconstruction of concentrated signals in a reproducing kernel space ⋮ Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time ⋮ Accelerated projected gradient method for linear inverse problems with sparsity constraints ⋮ On the linear independence of spikes and sines ⋮ Structured random measurements in signal processing ⋮ Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit ⋮ Sparse reconstruction with multiple Walsh matrices ⋮ Sparse recovery of sound fields using measurements from moving microphones

Uses Software

• PDCO
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extensions of compressed sensing
• Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
• Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Atomic Decomposition by Basis Pursuit
• A sharp concentration inequality with applications
• Random Sampling of Multivariate Trigonometric Polynomials
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Neighborliness of randomly projected simplices in high dimensions
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing

This page was built for publication: Random sampling of sparse trigonometric polynomials