Random sampling of sparse trigonometric polynomials

DOI10.1016/J.ACHA.2006.05.002MaRDI QIDQ861807zbMATH OpenOpenAlexFDO

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

sparse recovery random matrices random sampling trigonometric polynomials set partitions basis pursuit $\ell ^{1}$-minimization

Mathematics Subject Classification ID

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

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

e l l^{1}

-minimization. Numerical experiments show that in many cases 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. 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.

Recommendations

Cites work

Cited in

(57)

Describes a project that uses

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)