In this paper we consider the following sparse recovery problem. We have query access to a vector @math such that @math is @math -sparse (or nearly @math -sparse) for some orthogonal transform @math . The goal is to output an approximation (in an @math sense) to @math in sublinear time. This problem has been well-studied in the special case that @math is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time @math . However, for transforms @math other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms---running in time @math ---for solving the sparse recovery problem for orthogonal transforms @math that arise from orthogonal polynomials. More precisely, our algorithm works for any @math that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the @math -sparse sparse recovery problem to the @math -sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials.
The sample complexity of OP transforms @math has been largely pinned down by the compressed sensing literature. For example, suppose that @math is any orthogonal and sufficiently flat matrix, in the sense that none of the entries of @math are too large. Then a result of Rudelson and Vershynin (and a sharpening of their result by Bourgain) shows that @math samples suffice to establish that the matrix @math (which is made up of @math sampled rows from @math ) has the Restricted Isometry Property (RIP) @cite_0 @cite_4 . Finding @math from samples of @math of corresponds to the problem of finding an (approximately) @math -sparse vector @math from the linear measurements @math , which is precisely the compressed sensing problem. It is known that if @math satisfies the RIP, then this can be solved (for example with @math minimization) in time @math . We note that very recently a result due to B show that this is essentially tight, in that @math queries (for a certain range of @math ) to @math are not enough to compute a @math -sparse approximation of @math @cite_16 . Bounds specific to the DFT over finite fields can be found in @cite_30 .
@cite_0 @cite_16 @cite_4 @cite_30
641843003 2923536738 2055064119 2924908021
It is shown that for the n × n-Hadamard matrix (or, more generally, a bounded orthogonal matrix) the RIP-property for r-space vectors holds, with row restriction to a set S of size @math This bound represents a slight improvement over (Rudelson and Vershynin, Commun Pure Appl Math 61:1025–1045, 2008) in that the power of the logarithm is decreased by one unit. We give a short argument that yields a new lower bound on the number of subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that for a @math Hadamard matrix, one cannot recover all @math -sparse vectors unless the number of subsampled rows is @math . This paper improves upon best-known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly nonconvex problem to a convex problem and then solve it as a linear program. We show that there exists a set of frequencies Ω such that one can exactly reconstruct every r-sparse signal f of length n from its frequencies in Ω, using the convex relaxation, and Ω has size k(r, n) = O(r log(n)·log 2 (r) log(r logn)) = O(r log 4 n ). A random set Ω satisfies this with high probability. This estimate is optimal within the log log n and log 3 r factors. We also give a relatively short argument for a similar problem with k(r, n) ≈ r[12 + 8 log(n r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short. Let @math be an @math Fourier matrix over @math for some prime @math . We improve upon known lower bounds for the number of rows of @math that must be sampled so that the resulting matrix @math satisfies the restricted isometry property for @math -sparse vectors. This property states that @math is approximately @math for all @math -sparse vectors @math . In particular, if @math , we show that @math rows must be sampled to satisfy the restricted isometry property with constant probability.