期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 52, 期 12, 页码 5406-5425出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2006.885507
关键词
concentration of measure; convex optimization; duality in optimization; linear programming; random matrices; random projections; signal recovery; singular values of random matrices; sparsity; trigonometric expansions; uncertainty principle
Suppose we are given a vector f in a class F subset of R-N e.g., a class of digital signals or digital images. How many linear measurements do we need to make about f to be able to recover f to within precision is an element of in the Euclidean (l(2)) metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the,nth largest entry of the vector If I (or of its coefficients in a fixed basis) obeys vertical bar f vertical bar((n)) < R (.) n(-1/P), where R > 0 and p > 0. Suppose that we take measurements y(k) = < f, X-k >; k = 1..., K, where the X-k are N-dimensional Gaussian vectors with independent standard normal entries. Then for each f obeying the decay estimate above for some 0 < p < 1 and with overwhelming probability, our reconstruction f(#) defined as the solution to the constraints y(k) = < f(#), X-k > with minimal l(1) norm, obeys parallel to f - f(#)parallel to(l2) <= C-p (.) R (.) (K/log N)(-r), r = 1/p - 1/2 There is a sense in which this result is optimal; it is generally impossible to obtain a higher accuracy from any set of K measurements whatsoever. The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes a few randomly sampled Fourier coefficients of f. In fact, the results are quite general and require only two hypotheses on the measurement ensemble which are detailed.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据