On sparse reconstruction from Fourier and Gaussian measurements

摘要: This paper improves upon best-known guarantees for exact reconstruction of a sparse signal f from small universal sample Fourier measurements. The method that has recently gained momentum in the approximation theory is to relax this highly nonconvex problem convex and then solve it as linear program. We show there exists set frequencies Ω such one can exactly reconstruct every r-sparse length n its Ω, using relaxation, size k(r, n) = O(r log(n)·log 2 (r) log(r logn)) log 4 ). A random satisfies with high probability. estimate optimal within 3 r factors. also give relatively short argument similar ≈ r[12 + 8 log(n/r)] Gaussian use methods geometric functional analysis probability Banach spaces, which makes our arguments quite short.