What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid

详细信息    查看全文

• 作者：Petros Boufounos ; Volkan Cevher ; Anna C. Gilbert ; Yi Li ; Martin J. Strauss
• 关键词：Sparse signal recovery ; Fourier sampling ; Sublinear algorithms ; 94A20 ; 68W20
• 刊名：Algorithmica
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：73
• 期：2
• 页码：261-288
• 全文大小：690 KB
• 参考文献：1.Baraniuk, R., Cevher, V., Wakin, M.: Low-dimensional models for dimensionality reduction and signal recovery: a geometric perspective. Proc. IEEE 98(6), 959-71 (2010)CrossRef
  2.Chahine, K., Baltazart, V., Wang, Y.: Interpolation-based matrix pencil method for parameter estimation of dispersive media in civil engineering. Signal Process. 90(8), 2567-580 (2010)CrossRef MATH
  3.Chui, D.: Personal communication (2013).
  4.Gilbert, A., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937-47 (2010)CrossRef
  5.Gilbert, A., Li, Y., Porat, E., Strauss, M.: Approximate sparse recovery: optimizing time and measurements. SIAM J. Comput. 41(2), 436-53 (2012)MathSciNet CrossRef MATH
  6.Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing. STOC -2, pp. 152-61. ACM, New York (2002)
  7.Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-optimal sparse Fourier representations. In: Proceedings of Wavelets XI conference, pp. 398-12 (2005).
  8.Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Nearly optimal sparse Fourier transform. In: Proceedings of the 44th Symposium on Theory of Computing, STOC -2, pp. 563-78. ACM, New York (2012)
  9.Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse Fourier transform. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA -2, pp. 1183-194. SIAM (2012).
  10.Heider, S., Kunis, S., Potts, D., Veit, M.: A sparse Prony FFT. In: Proceedings of Tenth International Conference on Sampling Theory and Applications, SampTA 2013, pp. 572-75 (2013)
  11.Helson, H.: Harmonic Analysis (2nd edn.). Hindustan Book Agency, New Delhi (1995).
  12.Hua, Y., Sarkar, T.: On SVD for estimating generalized eigenvalues of singular matrix pencil in noise. In: Proceedings of the IEEE Transactions on Signal Processing, vol. 39(4), pp. 892-00 (1991)
  13.Iwen, M.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10(3), 303-38 (2009)MathSciNet CrossRef
  14.Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6), 1331-348 (1993)MathSciNet CrossRef MATH
  15.Peter, T., Potts, D., Tasche, M.: Nonlinear approximation by sums of exponentials and translates. SIAM J. Sci. Comput. 33(4), 1920-947 (2011)MathSciNet CrossRef MATH
  16.Potts, D., Tasche, M.: Parameter estimation for exponential sums by approximate Prony method. Signal Process. 90(5), 1631-642 (2010)CrossRef MATH
  17.Vetterli, M., Marziliano, P., Blu, T.: Sampling signals with finite rate of innovation. In: Proceedings of the IEEE Transactions on Signal Processing, vol. 50(6), pp. 1417-428 (2002)
  
• 作者单位：Petros Boufounos (1)
  Volkan Cevher (2)
  Anna C. Gilbert (3)
  Yi Li (4)
  Martin J. Strauss (5) (6)
  
  1. Mitsubishi Electric Research Labs, 201 Broadway, Cambridge, MA, 02139, USA
  2. Laboratory for Information and Inference Systems, EPFL, Lausanne, Switzerland
  3. Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109, USA
  4. Department 1, Max-Planck-Institut für Informatik, Campus E1 4, 66123?, Saarbrücken, Germany
  5. Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109, USA
  6. Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI, 48109, USA
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form \(f(t) = \sum _{j=1}^k a_j \mathrm{e}^{i\omega _j t} + \int \nu (\omega )\mathrm{e}^{i\omega t}d\mu (\omega )\); i.e., exponential polynomials with a noise term. The frequencies \(\{\omega _j\}\) satisfy \(\omega _j\in [\eta ,2\pi -\eta ]\) and \(\min _{i\ne j} |\omega _i-\omega _j|\ge \eta \) for some \(\eta > 0\). We design a sublinear time randomized algorithm which, for any \(\epsilon \in (0,\eta /k]\), which takes \(O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))\) samples of \(f(t)\) and runs in time proportional to number of samples, recovering \(\omega _j'\approx \omega _j\) and \(a_j'\approx a_j\) such that, with probability \(\varOmega (1)\), the approximation error satisfies \(|\omega _j'-\omega _j|\le \epsilon \) and \(|a_j-a_j'|\le \Vert \nu \Vert _1/k\) for all \(j\) with \(|a_j|\ge \Vert \nu \Vert _1/k\). We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing. Keywords Sparse signal recovery Fourier sampling Sublinear algorithms