Deterministic sparse FFT for \(M\)-sparse vectors. (English) Zbl 1478.65146
In this interesting paper, the authors present a new deterministic sparse (inverse) fast Fourier transform (FFT), where the resulting vector \(\mathbf x \in {\mathbb C}^N\) with \(N = 2^J\) is \(M\)-sparse, i.e., \(\mathbf x\) contains only \(M\) nonzero components. This new algorithm which generalizes the sparse FFT of G. Plonka and K. Wannenwetsch [Numer. Algorithms 71, No. 4, 889–905 (2016; Zbl 1341.65056)] is based on a multi-scale reconstruction of \(\mathbf x\) and uses the solutions of well-conditioned Vandermonde-like systems in each iteration step. The unknown sparsity \(M\) is determined during the algorithm. The computational costs of this method is at most \({\mathcal O}(M^2\,\log N)\) if \(M^2 < N\) and falls back to \(\mathcal{O}(N\,\log N)\) if \(M^2 \geq N\). Numerical tests illustrate the performance of this method.
Reviewer: Manfred Tasche (Rostock)
MSC:
| 65T50 | Numerical methods for discrete and fast Fourier transforms |
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
Keywords:
sparse fast Fourier transform; sparse FFT; deterministic algorithm; reconstruction of sparse vectors; Vandermonde systems; sparse signalsCitations:
Zbl 1341.65056Software:
Sparse FFT small supportReferences:
| [1] | Akavia, A.: Deterministic sparse fourier approximation via approximating arithmetic progressions. IEEE Trans. Inform. Theory 60(3), 1733-1741 (2014) · Zbl 1360.94051 · doi:10.1109/TIT.2013.2290027 |
| [2] | Bittens, S.: Sparse FFT for functions with short frequency support. Dolomites Res. Notes Approx. 10, 43-55 (2017) · Zbl 1372.65359 · doi:10.1186/s13104-016-2361-3 |
| [3] | Berman, L., Feuer, A.: On perfect conditioning of Vandermonde matrices on the unit circle. Electron. J. Linear Algebra 16, 157-161 (2007) · Zbl 1146.15003 · doi:10.13001/1081-3810.1190 |
| [4] | Demeure, C.J.: Fast QR factorization of Vandermonde matrices. Linear Algebra Appl. 122-124, 165-194 (1989) · Zbl 0687.65025 · doi:10.1016/0024-3795(89)90652-6 |
| [5] | Giesbrecht, M., Labahn, G., Lee, W. -S.: Symbolic-numeric sparse interpolation of multivariate polynomials. J. Symbolic Comput. 44(8), 943-959 (2009) · Zbl 1167.65003 · doi:10.1016/j.jsc.2008.11.003 |
| [6] | Giesbrecht, M., Roche, D.S.: Diversification improves interpolation. In: Leykin, A. (ed.) Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation ISSAC 2011, pp 123-130. ACM · Zbl 1323.65010 |
| [7] | Gilbert, A., Indyk, P., Iwen, M.A., Schmidt, L.: Recent developments in the sparse fourier transform. IEEE Signal Process. Mag. 31(5), 91-100 (2014) · doi:10.1109/MSP.2014.2329131 |
| [8] | Hassanieh, H., Indyk, P., Katabi, D., Price, E.: Simple and practical algorithm for sparse fourier transform. In: Proc. 23th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’12), pp. 1183-1194 (2012) · Zbl 1286.94046 |
| [9] | Hassanieh, H., Adib, F., Katabi, D., Indyk, P.: Faster GPS via the sparse fourier transform. In: Proceeding Mobicom 2012, Proceedings of the 18th Annual International Conference on Mobile Computing and networking, pp. 353-364 (2012) |
| [10] | Iwen, M.A.: Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10, 303-338 (2010) · Zbl 1230.65145 · doi:10.1007/s10208-009-9057-1 |
| [11] | Iwen, M.A.: Improved approximation guarantees for sublinear-time Fourier algorithms. Appl. Comput. Harmon. Anal. 34, 57-82 (2013) · Zbl 1260.65115 · doi:10.1016/j.acha.2012.03.007 |
| [12] | Janakiraman, N.T., Vem, A., Narayanan, K.R., Chamberland, J.-F.: Sub-string/pattern matching in sub-linear time using a sparse Fourier transform approach, preprint, arXiv:1704.07852v1 |
| [13] | Moitra, A.: Super-resolution, extremal functions and the condition number of Vandermonde matrices. In: STOC ’15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 821-830 (2015) · Zbl 1321.68421 |
| [14] | Montgomery, H.L., Vaughan, R.C.: Hilbert’s inequality. J. London Math. Soc. (2) 8, 73-82 (1974) · Zbl 0281.10021 · doi:10.1112/jlms/s2-8.1.73 |
| [15] | Lawlor, D., Wang, Y., Christlieb, A.: Adaptive sub-linear time Fourier algorithms. Adv. Adapt. Data Anal. 5(1), 1350003 (2013) · doi:10.1142/S1793536913500039 |
| [16] | Pawar, S., Ramchandran, K.: Computing a k-sparse n-length discrete Fourier transform using at most 4k samples and O(kk)\( \mathcal{O}(k k)\) complexity. IEEE Int. Symp. Inf. Theory, 464-468 (2013) · Zbl 1366.65118 |
| [17] | Potts, D., Tasche, M., Volkmer, T.: Efficient spectral estimation by MUSIC and ESPRIT with application to sparse FFT. Frontiers Appl. Math. Stat. (2016) |
| [18] | Plonka, G., Wannenwetsch, K.: A deterministic sparse FFT algorithm for vectors with small support. Numer. Algorithms 71(4), 889-905 (2016) · Zbl 1341.65056 · doi:10.1007/s11075-015-0028-0 |
| [19] | Plonka, G., Wannenwetsch, K.: A sparse fast Fourier algorithm for real non-negative vectors. J. Comput. Appl. Math. 321, 532-539 (2017) · Zbl 1366.65118 · doi:10.1016/j.cam.2017.03.019 |
| [20] | Segal, B., Iwen, M.A.: Improved sparse Fourier approximation results: faster implementations and stronger guarantees. Numer. Algor. 63(2), 239-263 (2013) · Zbl 1276.65097 · doi:10.1007/s11075-012-9621-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
