A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods

ABSTRACT

We study the problem of estimating the best B term Fourier representation for a given frequency-sparse signal (i.e., vector) A of length N ≫ B. More precisely, we investigate how to deterministically identify B of the largest magnitude frequencies of Â, and estimate their coefficients, in polynomial (B, log N) time. Randomized sub-linear time algorithms, which have a small (controllable) probability of failure for each processed signal, exist for solving this problem. However, for failure intolerant applications such as those involving mission-critical hardware designed to process many signals over a long lifetime, deterministic algorithms with no probability of failure are highly desirable. In this paper we build on the deterministic Compressed Sensing results of Cormode and Muthukrishnan (CM) [26, 6, 7] in order to develop the first known deterministic sub-linear time sparse Fourier Transform algorithm suitable for failure intolerant applications. Furthermore, in the process of developing our new Fourier algorithm, we present a simplified deterministic Compressed Sensing algorithm which improves on CM's algebraic compressibility results while simultaneously maintaining their results concerning exponential decay.

REFERENCES

• 1: Chris Anderson , Marie Dillon Dahleh, Rapid computation of the discrete Fourier transform, SIAM Journal on Scientific Computing, v.17 n.4, p.913-919, July 1996 [doi>10.1137/0917059]
• 2: L. I. Bluestein. A Linear Filtering Approach to the Computation of Discrete Fourier Transform, IEEE Transactions on Audio and Electroacoustics, 18:451--455, 1970.
• 3: J. P. Boyd, Chebyshev and Fourier Spectral Methods, Dover Publications, Inc., 2001.
• 4: E. Candes, J. Romberg, and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52:489--509, 2006.
• 5: J. Cooley and J. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comput., 19:297--301, 1965.
• 6: G. Cormode and S. Muthukrishnan, Combinatorial Algorithms for Compressed Sensing, Technical Report DIMACS TR 2005--40, 2005.
• 7: G. Cormode and S. Muthukrishnan, Combinatorial Algorithms for Compressed Sensing, Conference on Information Sciences and Systems, March 2006.
• 8: I. Daubechies, O. Runborg, and J. Zou, A sparse spectral method for homogenization multiscale problems, Multiscale Model. Sim., 2007.
• 9: Ronald A. DeVore, Deterministic constructions of compressed sensing matrices, Journal of Complexity, v.23 n.4-6, p.918-925, August, 2007 [doi>10.1016/j.jco.2007.04.002]
• 10: A. Dutt , V. Rokhlin, Fast Fourier transforms for nonequispaced data, SIAM Journal on Scientific Computing, v.14 n.6, p.1368-1393, Nov. 1993 [doi>10.1137/0914081]
• 11: J. A. Fessler and B. P. Sutton, Nonuniform Fast fourier transforms using min-max interpolation, IEEE Trans. Signal Proc., 51:560--574, 2003.
• 12: G. B. Folland, Fourier Analysis and Its Applications, Brooks/Cole Publishing Company, 1992.
• 13: S. Ganguly and A. Majumder, CR-precis: A deterministic summary structure for update data streams, ArXiv Computer Science e-prints, Sept. 2006.
• 14: C. F. Gerald and P. O. Wheatley, Applied Numerical Analysis, Addison-Wesley Publishing Company, 1994.
• 15: A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509933]
• 16: A. Gilbert, S. Muthukrishnan, and M. Strauss, Improved time bounds for near-optimal sparse Fourier representations, SPIE, 2005.
• 17: Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
• 18: M. A. Iwen, Unpublished Results, http://www-personal.umich.edu/ markiwen/.
• 19: M. A. Iwen, A. C. Gilbert, and M. J. Strauss, Empirical evaluation of a sub-linear time sparse DFT algorithm, Submitted for Publication, 2007.
• 20: S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. Baraniuk, Analog-to-information conversion via random demodulation. in Proc. IEEE Dallas Circuits and Systems Conference, 2006.
• 21: J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, and M. Strauss, Random sampling for analog-to-information conversion of wideband signals, Proc. IEEE Dallas Circuits and Systems Conference, 2006.
• 22: June-Yub Lee , Leslie Greengard, The type 3 nonuniform FFT and its applications, Journal of Computational Physics, v.206 n.1, p.1-5, 10 June 2005 [doi>10.1016/j.jcp.2004.12.004]
• 23: M. Lustig, D. Donoho, and J. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Submitted for publication, 2007.
• 24: R. Maleh, A. C. Gilbert, and M. J. Strauss, Signal recovery from partial information via orthogonal matching pursuit, IEEE Int. Conf. on Image Processing, 2007.
• 25: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 26: S. Muthukrishnan, Some Algorithmic Problems and Results in Compressed Sensing, Allerton Conference, 2006.
• 27: L. Rabiner, R. Schafer, and C. Rader, The Chirp z-Transform Algorithm, IEEE Transactions on Audio and Electroacoustics, AU-17(2):86--92, June 1969.
• 28: J. Tropp and A. Gilbert, Signal recovery from partial information via orthogonal matching pursuit, Submitted for Publication, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Fast Fourier transforms (FFT)
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory