Kunis, Stefan ; Rauhut, Holger : Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit

Author(s):

Kunis, Stefan
Rauhut, Holger

Title:

Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 6, 2006

Mathematics Subject Classification:

94A20			[ Sampling theory ]
42A05			[ Trigonometric polynomials, inequalities, extremal problems ]
15A52			[ Random matrices ]
05A18			[ Partitions of sets ]
90C05			[ Linear programming ]
90C25			[ Convex programming ]

Abstract:

We continue investigating the problem of reconstructing a multivariate trigonometric polynomial having only few non-zero coefficients from few random samples. Both for a continuous and a discrete probability model for the sampling points we prove theoretical results on the success probability of reconstruction when using Orthogonal Matching Pursuit (OMP) or Basis Pursuit (BP). Although our theoretical estimates are the same for both methods, our numerical experiments indicate that OMP outperforms BP slightly. Moreover, OMP is significantly faster than BP in practice.

Keywords:

random sampling, trigonometric polynomials, Orthogonal Matching Pursuit, Basis Pursuit, sparse recovery, set partitions, random matrices, fast Fourier transform, nonequispaced fast Fourier transform

Language:

English

Publication time:

4 / 2006