Combinatorial Compressive Sampling with Applications.

Abstract

We simplify and improve the deterministic Compressed Sensing (CS) results of Cormode and Muthukrishnan (CM). A simple relaxation of our deterministic CS technique then generates a new randomized CS result similar to those derived by CM. Finally, our CS techniques are applied to two computational problems of wide interest: The calculation of a periodic function's Fourier transform, and matrix multiplication. Short descriptions of our results follow.

(i) Sublinear-Time Sparse Fourier Transforms: Suppose $f: [0, 2pi] rightarrow mathbbm{C}$ is $k$-sparse in frequency (e.g., $f$ is an exact superposition of $k$ sinusoids with frequencies in $[1-frac{N}{2},frac{N}{2}]$). Then we may recover $f$ in $O(k^2 cdot log^4(N))$ time by deterministically sampling it at $O(k^2 cdot log^3(N))$ points. If succeeding with high probability is sufficient, we may sample $f$ at $O(k cdot log^4(N))$ points and then reconstruct it in $O(k cdot log^5(N))$ time via a randomized version of our deterministic Fourier algorithm. If $N$ is much larger than $k$, both algorithms run in sublinear-time in the sense that they will outrun any procedure which samples $f$ at least $N$ times (e.g., both algorithms are faster than a fast Fourier transform).

In addition to developing new sublinear-time Fourier methods we have implemented previously existing sublinear-time Fourier algorithms. The resulting implementations, called AAFFT 0.5/0.9, are empirically evaluated. The results are promising: AAFFT 0.9 outperforms standard FFTs (e.g., FFTW 3.1) on signals containing about $10^2$ energetic frequencies spread over a bandwidth of $10^6$ or more. Furthermore, AAFFT utilizes significantly less memory than a standard FFT on large signals since it only needs to sample a fraction of the input signal's entries.

(ii) Fast matrix multiplication: Suppose both $A$ and $B$ are dense $N times N$ matrices. It is conjectured that $A cdot B$ can be computed in $O(N^{2+epsilon})$-time. If $A cdot B$ is known to be $O(N^{2.9462})$-sparse/compressible in each column (e.g., each column of $A cdot B$ contains only a few non-zero entries) we show that $A cdot B$ may be calculated in $O(N^{2+epsilon})$-time. Thus, we generalize previous rapid rectangular matrix multiplication results due to D. Coppersmith.