Deterministic sampling of sparse trigonometric polynomials

doi:10.1016/j.jco.2011.01.007

	Deterministic sampling of sparse trigonometric polynomials
	Xu, Zhiqiang
	2011-04-01
发表期刊	JOURNAL OF COMPLEXITY
ISSN	0885-064X
卷号	27 期号:2 页码:133-140
摘要	One can recover sparse multivariate trigonometric polynomials from a few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling of multivariate trigonometric polynomials inspired by Weil's exponential sum. Our sampling can produce a deterministic matrix satisfying the statistical restricted isometry property, and also nearly optimal Grassmannian frames. We show that one can exactly reconstruct every M-sparse multivariate trigonometric polynomial with fixed degree and of length D from the determinant sampling X, using the orthogonal matching pursuit, and with vertical bar X vertical bar a prime number greater than (M log D)(2). This result is optimal within the (log D)(2) factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling. (C) 2011 Elsevier Inc. All rights reserved.
关键词	Compressed sensing Deterministic sampling Weil sum Sparse trigonometric polynomials
DOI	10.1016/j.jco.2011.01.007
语种	英语
资助项目	Funds for Creative Research Groups of China[11021101] ; NSFC[10871196] ; National Basic Research Program of China (973 Program)[2010CB832702]
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000289135400002
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13090
专题	计算数学与科学工程计算研究所
通讯作者	Xu, Zhiqiang
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, Inst Comp Math, LSEC, Beijing 100091, Peoples R China
推荐引用方式 GB/T 7714	Xu, Zhiqiang. Deterministic sampling of sparse trigonometric polynomials[J]. JOURNAL OF COMPLEXITY,2011,27(2):133-140.
APA	Xu, Zhiqiang.(2011).Deterministic sampling of sparse trigonometric polynomials.JOURNAL OF COMPLEXITY,27(2),133-140.
MLA	Xu, Zhiqiang."Deterministic sampling of sparse trigonometric polynomials".JOURNAL OF COMPLEXITY 27.2(2011):133-140.