Abstract
In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is ksparse (or nearly ksparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been wellstudied in the special case that 𝐅 is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k ⋅ polylog N). However, for transforms 𝐅 other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled.
In this paper we give sublineartime algorithms  running in time poly(k log(N))  for solving the sparse recovery problem for orthogonal transforms 𝐅 that arise from orthogonal polynomials. More precisely, our algorithm works for any 𝐅 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 ksparse sparse recovery problem to the 1sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this onesparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1sparse recovery algorithm as a black box.
BibTeX  Entry
@InProceedings{gilbert_et_al:LIPIcs:2020:12465,
author = {Anna Gilbert and Albert Gu and Christopher R{\'e} and Atri Rudra and Mary Wootters},
title = {{Sparse Recovery for Orthogonal Polynomial Transforms}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {58:158:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12465},
URN = {urn:nbn:de:0030drops124653},
doi = {10.4230/LIPIcs.ICALP.2020.58},
annote = {Keywords: Orthogonal polynomials, Jacobi polynomials, sublinear algorithms, sparse recovery}
}
Keywords: 

Orthogonal polynomials, Jacobi polynomials, sublinear algorithms, sparse recovery 
Collection: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) 
Issue Date: 

2020 
Date of publication: 

29.06.2020 