Combinatorial Compressive Sampling with Applications.

[摘要] 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.

[发布机构] University of Michigan

[效力级别] Compressed Sensing

[关键词] Fast Fourier Transforms;Compressed Sensing;Sparsity;Rapid Matrix Multiplication;Mathematics;Science;Applied and Interdisciplinary Mathematics