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
2568623927 2598205349 2973707709 2949898670
Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary @math . This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the @math -restricted isometry property ( @math -RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in @math . While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the @math -RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary $ ... As a paradigm for reconstructing sparse signals using a set of under sampled measurements, compressed sensing has received much attention in recent years. In identifying the sufficient condition under which the perfect recovery of sparse signals is ensured, a property of the sensing matrix referred to as the restricted isometry property (RIP) is popularly employed. In this article, we propose the RIP based bound of the orthogonal matching pursuit (OMP) algorithm guaranteeing the exact reconstruction of sparse signals. Our proof is built on an observation that the general step of the OMP process is in essence the same as the initial step in the sense that the residual is considered as a new measurement preserving the sparsity level of an input vector. Our main conclusion is that if the restricted isometry constant δ K of the sensing matrix satisfies δ K < K - 1 K - 1 + K then the OMP algorithm can perfectly recover K(> 1)-sparse signals from measurements. We show that our bound is sharp and indeed close to the limit conjectured by Dai and Milenkovic. In sparse approximation theory, the fundamental problem is to reconstruct a signal A∈ℝn from linear measurements 〈Aψi〉 with respect to a dictionary of ψi's. Recently, there is focus on the novel direction of Compressed Sensing [9] where the reconstruction can be done with very few—O(k logn)—linear measurements over a modified dictionary if the signal is compressible, that is, its information is concentrated in k coefficients with the original dictionary. In particular, these results [9, 4, 23] prove that there exists a single O(k logn) ×n measurement matrix such that any such signal can be reconstructed from these measurements, with error at most O(1) times the worst case error for the class of such signals. Compressed sensing has generated tremendous excitement both because of the sophisticated underlying Mathematics and because of its potential applications In this paper, we address outstanding open problems in Compressed Sensing. Our main result is an explicit construction of a non-adaptive measurement matrix and the corresponding reconstruction algorithm so that with a number of measurements polynomial in k, logn, 1 e, we can reconstruct compressible signals. This is the first known polynomial time explicit construction of any such measurement matrix. In addition, our result improves the error guarantee from O(1) to 1 + e and improves the reconstruction time from poly(n) to poly(k logn) Our second result is a randomized construction of O(kpolylog (n)) measurements that work for each signal with high probability and gives per-instance approximation guarantees rather than over the class of all signals. Previous work on Compressed Sensing does not provide such per-instance approximation guarantees; our result improves the best known number of measurements known from prior work in other areas including Learning Theory [20, 21], Streaming algorithms [11, 12, 6] and Complexity Theory [1] for this case Our approach is combinatorial. In particular, we use two parallel sets of group tests, one to filter and the other to certify and estimate; the resulting algorithms are quite simple to implement Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important both for theory and practice. We present a formula that characterizes the allowed undersampling of generalized sparse objects. The formula applies to Approximate Message Passing (AMP) algorithms for compressed sensing, which are here generalized to employ denoising operators besides the traditional scalar soft thresholding denoiser. This paper gives several examples including scalar denoisers not derived from convex penalization -- the firm shrinkage nonlinearity and the minimax nonlinearity -- and also nonscalar denoisers -- block thresholding, monotone regression, and total variation minimization. Let the variables eps = k N and delta = n N denote the generalized sparsity and undersampling fractions for sampling the k-generalized-sparse N-vector x_0 according to y=Ax_0. Here A is an n N measurement matrix whose entries are iid standard Gaussian. The formula states that the phase transition curve delta = delta(eps) separating successful from unsuccessful reconstruction of x_0 by AMP is given by: delta = M(eps| Denoiser), where M(eps| Denoiser) denotes the per-coordinate minimax mean squared error (MSE) of the specified, optimally-tuned denoiser in the directly observed problem y = x + z. In short, the phase transition of a noiseless undersampling problem is identical to the minimax MSE in a denoising problem.