Random Sampling of Sparse Trigonometric Polynomials

By Holger Rauhut. 2005

177 citations recorded by the source corpus.

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 l 1 -minimization. In contrast to their work, where the sampling points are restricted to a grid, we model the random sampling points by a continuous uniform distribution on the cube, i.e., we allow them to have arbitrary position. Numerical experiments show that with high probability the trigonometric polynomial can be recovered exactly provided the number N of samples is high enough compared to the “sparsity”—the number of non-vanishing coefficients. However, N can be chosen small compared to the assumed maximal degree of the trigonometric polynomial. We present two theorems that explain this observation. One of them provides the analogue of the result of Candes, Romberg and Tao. The other one is a result toward an average case analysis and, unexpectedly connects to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before. Although our proofs follow ideas of Candes et al. they are simpler.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/f717fae559b9f0b244e0c86735177c82df79ec60

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Parameter estimation for nonincreasing exponential sums by Prony-like methods (2013, unknown): “j=1 cj e iωjt (t ≥ 0) with distinct integer frequencies ωj := −1000 fj i, see [27, 19, 9, 17].”
Compressed Sensing Off the Grid (2012, background): “While this simple strategy yields state-of-the-art performance for problems where the true parameters lie on the grid, discretization has several signi ﬁ cant drawbacks—1) In cases where the true parameters do not fall onto the ﬁ nite grid, the G. Tang and B. N. Bhaskar are with the Department of…”
Spectral compressive sensing (2013, unknown): “selection technique results in a random sampling acquisition scheme [39, 40, 41, 42, 43, 44].”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “Finally and to be complete, we would like to mention that earlier works have considered the recovery of perfectly sparse signals from subsampled orthogonal transforms [11], and of sparse trigonometric polynomials from random time samples [38].”
Compressive Sensing with structured random matrices (2012, methodology): “The techniques of the proof of this theorem [19, 102] heavily use the algebraic structure of the Fourier system and do not easily extend to general bounded orthonormal systems.”
Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization (2011, background): “There are many important applications in which the observations of interest can be modeled as a linear projection of a sparse signal plus sparse error.”
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation (2009, unknown): “The basis pursuit (BP), or -minimization approach, is the most extensively studied recovery method [8], [12], [15], [34].”