An adaptive sublinear-time block sparse fourier transform

DOI10.1145/3055399.3055462zbMATH Open1372.65360arXiv1702.01286OpenAlexW2586885375MaRDI QIDQ4978017

Michael Kapralov, Jonathan Scarlett, Amir Zandieh, Volkan Cevher

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: The problem of approximately computing the $k$ dominant Fourier coefficients of a vector $X$ quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in algorithms with $O(klognlog(n/k))$ runtime [Hassanieh et al., STOC'12] and $O(klogn)$ sample complexity [Indyk et al., FOCS'14]. These results are proved using non-adaptive algorithms, and the latter $O(klogn)$ sample complexity result is essentially the best possible under the sparsity assumption alone. This paper revisits the sparse FFT problem with the added twist that the sparse coefficients approximately obey a $(k_0,k_1)$-block sparse model. In this model, signal frequencies are clustered in $k_0$ intervals with width $k_1$ in Fourier space, where $k=k_0{k}_1$ is the total sparsity. Signals arising in applications are often well approximated by this model with $k_{0}llk$. Our main result is the first sparse FFT algorithm for $(k_0,k_1)$-block sparse signals with the sample complexity of $O^{*}(k_0{k}_1+k_{0}log(1+k_0)logn)$ at constant signal-to-noise ratios, and sublinear runtime. A similar sample complexity was previously achieved in the works on model-based compressive sensing using random Gaussian measurements, but used $Omega(n)$ runtime. To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the $O(klogn)$ sample complexity bound. Our algorithm crucially uses {em adaptivity} to achieve the improved sample complexity bound, and we prove that adaptivity is in fact necessary if Fourier measurements are used: Any non-adaptive algorithm must use $Omega(k_0{k}_{1}logfracn{k}_0{k}_1)$ samples for the $(k_0,k_1$)-block sparse model, ruling out improvements over the vanilla sparsity assumption.

Full work available at URL: https://arxiv.org/abs/1702.01286

zbMATH Keywords

lower boundsadaptive samplingsublinear-time algorithmssparse Fourier transformenergy-based importance sampling

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)

Related Items (2)

Fast multidelay block transform-domain adaptive filters based on a two-dimensional optimum block algorithm ⋮ A deterministic sparse FFT for functions with structured Fourier sparsity

This page was built for publication: An adaptive sublinear-time block sparse fourier transform