SCIENCE@home

A deterministic sparse FFT algorithm for vectors with small support

G. Plonka-Hoch,Katrin Wannenwetsch

Published 2015 in Numerical Algorithms

ABSTRACT

In this paper we consider the special case where a signal x∈ℂN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\in }\,\mathbb {C}^{N}$\end{document} is known to vanish outside a support interval of length m < N. If the support length m of x or a good bound of it is a-priori known we derive a sublinear deterministic algorithm to compute x from its discrete Fourier transform x̂∈ℂN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\widehat {\mathbf x}\,{\in }\,\mathbb {C}^{N}$\end{document}. In case of exact Fourier measurements we require only O\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}$\end{document}(mlog\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\log $\end{document}m) arithmetical operations. For noisy measurements, we propose a stable O\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathcal O}$\end{document}(mlog\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\log $\end{document}N) algorithm.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-16 of 16 references · Page 1 of 1

CITED BY

Showing 1-20 of 20 citing papers · Page 1 of 1