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.
There have been several works generalizing and building on the sFFT results mentioned above. One direction is to the multi-dimensional DFT (for example in @cite_27 @cite_9 ). Another direction is to apply the sFFT framework to orthogonal polynomials with similar structure. One example is Chebyshev polynomials and the Discrete Cosine Transform (DCT). It was observed in @cite_26 (also see Appendix ) that this can be reduced to sFFT in a black box manner, solving the sparse recovery problem for Chebyshev polynomials and the DCT. A second example of OP transforms which can essentially be reduced to the sFFT is Legendre polynomials. @cite_26 seek to recover an unknown @math -term Legendre polynomial (with highest magnitude degree limited to be @math ), defined on @math , from samples. They give a sublinear two-phase algorithm: in the first phase, they reduce @math -sparse-Legendre to sFFT to identify a set of candidate Legendre polynomials. The second phase uses the RIP result for BOS to produce a matrix that is used to estimate the coefficients of the candidate Legendre polynomials. We note that in this work the setting is naturally continuous, while ours is discrete.
@cite_9 @cite_27 @cite_26
2903067870 2082051116 2963520188
We give an algorithm for l2 l2 sparse recovery from Fourier measurements using O(klog N) samples, matching the lower bound of Do Ba-Indyk-Price-Woodruff'10 for non-adaptive algorithms up to constant factors for any k≤ N1-δ. The algorithm runs in tilde O(N) time. Our algorithm extends to higher dimensions, leading to sample complexity of Od(klog N), which is optimal up to constant factors for any d = O(1). These are the first sample optimal algorithms for these problems. A preliminary experimental evaluation indicates that our algorithm has empirical sampling complexity comparable to that of other recovery methods known in the literature, while providing strong provable guarantees on the recovery quality. In this paper, we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : [ź1, 1] ź ź with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just (slogN)O(1) @math -time. When s ź N, these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Ω(NlogN)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.