Random sampling of sparse trigonometric polynomials
From MaRDI portal
Publication:861807
DOI10.1016/J.ACHA.2006.05.002zbMATH Open1123.94004arXivmath/0512642OpenAlexW2067161429MaRDI QIDQ861807FDOQ861807
Authors: Holger Rauhut 
Publication date: 2 February 2007
Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)
Abstract: We study the problem of reconstructing a multivariate trigonometric polynomial having only few non-zero coefficients from few random samples. Inspired by recent work of Candes, Romberg and Tao we propose to recover the polynomial by Basis Pursuit, i.e., by -minimization. Numerical experiments show that in many cases the trigonometric polynomial can be recovered exactly provided the number of samples is high enough compared to the ``sparsity -- the number of non-vanishing coefficients. However, can be chosen small compared to the assumed maximal degree of the trigonometric polynomial. Hence, the proposed scheme may overcome the Nyquist rate. We present two theorems that explain this observation. Unexpectly, they establish a connection to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before.
Full work available at URL: https://arxiv.org/abs/math/0512642
Recommendations
- Stability Results for Random Sampling of Sparse Trigonometric Polynomials
- Deterministic sampling of sparse trigonometric polynomials
- Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
- Random Sampling of Multivariate Trigonometric Polynomials
- Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces
sparse recoveryrandom matricesrandom samplingtrigonometric polynomialsset partitionsbasis pursuit\(\ell ^{1}\)-minimization
Random matrices (algebraic aspects) (15B52) Trigonometric polynomials, inequalities, extremal problems (42A05) Sampling theory in information and communication theory (94A20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Atomic Decomposition by Basis Pursuit
- Title not available (Why is that?)
- Stable signal recovery from incomplete and inaccurate measurements
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Compressed sensing
- Sparse nonnegative solution of underdetermined linear equations by linear programming
- Neighborliness of randomly projected simplices in high dimensions
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Geometric approach to error-correcting codes and reconstruction of signals
- A sharp concentration inequality with applications
- Random Sampling of Multivariate Trigonometric Polynomials
Cited In (57)
- Compressive Sensing
- Structured random measurements in signal processing
- Remote sensing via \(\ell_1\)-minimization
- Spectral dynamics and regularization of incompletely and irregularly measured data
- Sparse recovery of sound fields using measurements from moving microphones
- Sparse Legendre expansions via \(\ell_1\)-minimization
- Sparse approximation of fitting surface by elastic net
- Sparse approximate solution of partial differential equations
- On the linear independence of spikes and sines
- A multivariate generalization of Prony's method
- Meshless Hermite-HDMR finite difference method for high-dimensional Dirichlet problems
- Stability Results for Random Sampling of Sparse Trigonometric Polynomials
- Parameter estimation for nonincreasing exponential sums by Prony-like methods
- Random sampling and reconstruction of concentrated signals in a reproducing kernel space
- Spark-level sparsity and the \(\ell_1\) tail minimization
- Spectral compressive sensing
- Investigations of the effects of random sampling schemes on the stability of generalized sampling
- Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces
- A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Variations on a theorem of Candès, Romberg and Tao
- Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
- Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
- A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing
- Reconstruction of Sparse Polynomials via Quasi-Orthogonal Matching Pursuit Method
- Sparse high-dimensional FFT based on rank-1 lattice sampling
- Reconstruction of sparse Legendre and Gegenbauer expansions
- How many Fourier samples are needed for real function reconstruction?
- Sparse approximate solution of fitting surface to scattered points by MLASSO model
- Sparse reconstruction with multiple Walsh matrices
- Cosparsity in Compressed Sensing
- Robust group lasso: model and recoverability
- Accelerated projected gradient method for linear inverse problems with sparsity constraints
- Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit
- The alternating descent conditional gradient method for sparse inverse problems
- Random sampling in multi-window quasi shift-invariant spaces
- Probability against condition number and sampling of multivariate trigonometric random polynomials
- A survey of compressed sensing
- Iterative thresholding algorithms
- Idempotents and compressive sampling
- Greedy Algorithms for Optimal Measurements Selection in State Estimation Using Reduced Models
- The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials
- Compressive sensing in acoustic imaging
- Random Sampling of Multivariate Trigonometric Polynomials
- On the impossibility of uniform sparse reconstruction using greedy methods
- Uncertainty in time-frequency representations on finite Abelian groups and applications
- On the properties of reachability, observability, controllability, and constructibility of discrete-time positive time-invariant linear systems with aperiodic choice of the sampling instants
- Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
- Deterministic sampling of sparse trigonometric polynomials
- A novel compressed sensing scheme for photoacoustic tomography
- Sparse signal recovery using a new class of random matrices
- Compressed Sensing with Nonlinear Fourier Atoms
- Sparsity in time-frequency representations
- Compressed sensing for quaternionic signals
- Sampling and reconstruction of concentrated reproducing kernel signals in mixed Lebesgue spaces
- Inversion of Band-Limited Discrete Fourier Transforms of Binary Images: Uniqueness and Algorithms
- Random sampling and reconstruction in reproducing kernel subspace of mixed Lebesgue spaces
Uses Software
This page was built for publication: Random sampling of sparse trigonometric polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q861807)
