A sublinear algorithm for the recovery of signals with sparse Fourier transform when many samples are missing.

*(English)*Zbl 1278.94024Summary: We present a sublinear randomized algorithm to compute a sparse Fourier transform for nonequispaced data of a special type. More precisely, we address the situation where a signal \(S\) is known to consist of \(N\) equispaced time samples, of which only \(L<N\) samples are available. If the ratio \(p=L/N\) is much smaller than 1, the available data typically look like nonequispaced samples, with little or no visible trace of the equispacing of the full set of \(N\) samples. We extend an approach for equispaced data that was presented in [the author et al., J. Comput. Phys. 211, No. 2, 572–595 (2006; Zbl 1085.65128)]; the extended algorithm reconstructs, from the incomplete data, a near-optimal \(B\)-term representation \(R\) with high probability \(1-\delta\), in time and space \(\text{poly}(B,\log(N),\log(1/\delta), \varepsilon^{-1})\), such that
\[
\| S-R\|_2^2\leq (1+\varepsilon)\| S-R_{\text{opt}}^B\|_2^2,
\]
where \(R_{\text{opt}}^B\) is the optimal \(B\)-term Fourier representation of signal \(S\). The sublinear \(\text{poly}(\log N)\) time is compared to the superlinear \(O(L1+(d-1)/\beta\log L)\) time requirement of the present best known inverse nonequispaced fast Fourier transform (INFFT) algorithms, in the sense of weighted norm with the number of dimensions \(d\) and smoothness parameter \(\beta\). Numerical experiments support the advantage of our algorithm in speed over other methods for sparse signals: it already outperforms the INFFT for large but realistic size \(N\) and works well even in the situation of a large percentage of missing data and in the presence of large noise.

##### MSC:

94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |

42A16 | Fourier coefficients, Fourier series of functions with special properties, special Fourier series |

68W20 | Randomized algorithms |

65T50 | Numerical methods for discrete and fast Fourier transforms |

##### Keywords:

sublinear randomized algorithm; sparse Fourier transform for nonequispaced data; optimal B-term Fourier representation of signal
PDF
BibTeX
XML
Cite

\textit{J. Zou}, Appl. Comput. Harmon. Anal. 22, No. 1, 61--77 (2007; Zbl 1278.94024)

Full Text:
DOI

##### References:

[1] | Bass, R.; Gröchenig, K., Random sampling of multivariate trigonometric polynomials, SIAM J. math. anal., 36, 773-795, (2004) · Zbl 1096.94008 |

[2] | Boyd, J.P., A fast algorithm for Chebyshev, Fourier and sinc interpolation onto an irregular grid, J. comput. phys., 103, 243-257, (1992) · Zbl 0768.65001 |

[3] | E. Candes, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, preprint, December 2004 · Zbl 1231.94017 |

[4] | E. Candes, J. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements, preprint, March 2005 · Zbl 1098.94009 |

[5] | E. Candes, T. Tao, Decoding by linear programming, preprint, February 2005 · Zbl 1264.94121 |

[6] | E. Candes, T. Tao, M. Rudelson, R. Vershynin, Error correction via linear programming, FOCS, 2005 |

[7] | Canny, J., Lecture 10, Chernoff bounds |

[8] | D. Donoho, M. Elad, V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, preprint, 2004 · Zbl 1288.94017 |

[9] | D. Donoho, J. Tanner, Sparse nonnegative solutions of underdetermined linear equations by linear programming, preprint, 2005 |

[10] | Fassbender, H., On numerical methods for discrete least-squares approximation by trigonometric polynomials, Math. comput., 66, 719-741, (1997) · Zbl 0864.65096 |

[11] | Feichtinger, H.; Gröchenig, K.; Strohmer, T., Efficient numerical methods in non-uniform sampling theory, Numer. math., 69, 423-440, (1995) · Zbl 0837.65148 |

[12] | A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-optimal sparse Fourier representations via sampling, STOC, 2002 · Zbl 1192.94078 |

[13] | Greengard, L.; Lee, J., Accelerating the nonuniform fast Fourier transform, SIAM rev., 46, 443-454, (2004) · Zbl 1064.65156 |

[14] | S. Kunis, D. Potts, Stability results for scattered data interpolation by trigonometric polynomials, preprint · Zbl 1146.65016 |

[15] | S. Kunis, D. Potts, G. Steidl, Fast Fourier transform at nonequispaced knots: A user’s guide to a C-library, Manual of NFFT 2.0 software |

[16] | Press, W.; Teukolsky, S.; Vetterling, W.; Flannery, B., Numerical recipes in C: the art of scientific computing, (1992), Cambridge Univ. Press Cambridge, UK · Zbl 0845.65001 |

[17] | H. Rauhut, Random sampling of sparse trigonometric polynomials, submitted for publication · Zbl 1123.94004 |

[18] | T.L. Veldhuizen, Grid filters for local nonlinear image restoration, Ph.D. dissertation, University of Waterloo, 1998 |

[19] | M. Rudelson, R. Vershynin, Geometric approach to error correcting codes and reconstruction of signals, in preparation · Zbl 1103.94014 |

[20] | Ware, A.F., Fast approximate Fourier transforms for irregularly spaced data, SIAM rev., 40, 838-856, (1998) · Zbl 0917.65122 |

[21] | Zou, J.; Gilbert, A.C.; Strauss, M.; Daubechies, I., Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis, J. comput. phys., 211, 572-595, (2006) · Zbl 1085.65128 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.