January 25 - 27, 2007

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 IN := {-N/2,...,N/2-1}

with non-zero complex Fourier coefficients ûk only on a subset Ω of IN 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 xj 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.

Impressum       Valid HTML 4.0 Transitional