Wissen, was gut ist. Studieren in Chemnitz.
Kunis, Stefan; Rauhut, Holger : Random Sampling of Sparse Trigonometric Polynomials II - Orthogonal Matching Pursuit versus Basis Pursuit

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