#
Greedy algorithms for sparse Fourier analysis

## Stefan Kunis (TU Chemnitz)

Recently, the surprising fact that it is possible to recover functions having only few non-zero
coefficients with respect to some basis from vastly incomplete information has gained much attention.
Such functions are commonly called sparse or compressible and they naturally appear in a wide range
of applications. We study *sparse trigonometric polynomials*

*u(x) = ∑*_{ k in IN} û_{k} exp(-2 π ikx), and *I*_{N} := {-N/2,...,N/2-1}

with non-zero complex Fourier coefficients *û*_{k} only on a subset *Ω* of *I*_{N}
with size |*Ω*| much less than *N*. However, a priori nothing is known about *Ω*
apart from a maximum
size. Our aim is to sample *u* at *M* randomly chosen nodes
*x*_{j} in [*-0.5,0.5*] and try to reconstruct *u* from these samples.

For an appropriate number of samples *M*, greedy methods like *(Orthogonal) Matching Pursuit*
or *Thresholding* succeed in this task with high probability. We focus on the computational
complexity of the proposed methods when using the nonequispaced FFT and particular updating techniques.
Illustration of our observations is given by numerical experiments.

This is joint work with H. Rauhut.