期刊
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
卷 8, 期 6, 页码 737-763出版社
SPRINGER
DOI: 10.1007/s10208-007-9005-x
关键词
Random sampling; Trigonometric polynomials; Orthogonal Matching Pursuit; Basis Pursuit; Thresholding; Sparse recovery; Random matrices; Fast Fourier transform; Nonequispaced fast Fourier transform; 94A20; 42A05; 15A52; 90C05; 90C25
资金
- German Academic Exchange Service (DAAD)
- Numerical Harmonic Analysis Group
- University of Vienna
- European Union [MEIF-CT-2006-022811]
- European Union's Human Potential Programme [HPRN-CT-2002-00285]
We investigate the problem of reconstructing sparse multivariate trigonometric polynomials from few randomly taken samples by Basis Pursuit and greedy algorithms such as Orthogonal Matching Pursuit (OMP) and Thresholding. While recovery by Basis Pursuit has recently been studied by several authors, we provide theoretical results on the success probability of reconstruction via Thresholding and OMP for both a continuous and a discrete probability model for the sampling points. We present numerical experiments, which indicate that usually Basis Pursuit is significantly slower than greedy algorithms, while the recovery rates are very similar.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据