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.
Finally, there are sparse OP transforms based on Prony's method. The work @cite_20 extends Prony's method to a very general setting, including Jacobi polynomials, and gives an algorithm that requires only @math queries to recover exactly @math -sparse polynomials. However, these general results work only for exact sparsity and are in general not robust to noise. There has been work extending and modifying these techniques to settings with noise (for example, @cite_11 @cite_31 ), but to the best of our knowledge the only provable results for noise are for either the sFFT or closely related polynomial families. We note that @cite_32 presents a Prony-like algorithm for Legendre and Gegenbauer polynomials and demonstrates empirically that this algorithm is robust to noise, although they do not address the question theoretically.
@cite_31 @cite_32 @cite_20 @cite_11
2211482116 1559478034 2141454789 1977375620
We present a new deterministic approximate algorithm for the reconstruction of sparse Legendre expansions from a small number of given samples. Using asymptotic properties of Legendre polynomials, this reconstruction is based on Prony-like methods. The method proposed is robust with respect to noisy sampled data. Furthermore we show that the suggested method can be extended to the reconstruction of sparse Gegenbauer expansions of low positive order. In this survey, we describe the classical Prony method and whose relatives. We sketch a frequently used Prony–like method for equispaced sampled data, namely the ESPRIT method. The case of nonequispaced sampled data is discussed too. For the reconstruction of a sparse eigenfunction expansion, a generalized Prony method is presented. The Prony methods are applied to the recovery of structured functions (such as exponential sums and extended exponential sums) and of sparse vectors. The recovery of spline functions with arbitrary knots from Fourier data is also based on Prony methods. Finally, some numerical examples are given. (© 2014 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) We consider the problem of recovering polynomials that are sparse with respect to the basis of Legendre polynomials from a small number of random samples. In particular, we show that a Legendre s-sparse polynomial of maximal degree N can be recovered from [email protected]?slog^4(N) random samples that are chosen independently according to the Chebyshev probability measure [email protected](x)[email protected]^-^1(1-x^2)^-^1^ ^2dx. As an efficient recovery method, @?"1-minimization can be used. We establish these results by verifying the restricted isometry property of a preconditioned random Legendre matrix. We then extend these results to a large class of orthogonal polynomial systems, including the Jacobi polynomials, of which the Legendre polynomials are a special case. Finally, we transpose these results into the setting of approximate recovery for functions in certain infinite-dimensional function spaces. We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or Tiwari sparse interpolation algorithm and the classical Prony's method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony's method. We analyse the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.