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
