A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods

Details A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods

2007-08-09

arxiv.org/abs/0708.1211v1

Computer Science

Discrete Mathematics

16 pages total, 10 in paper, 6 in appended

Scientific paper

We study the problem of estimating the best B term Fourier representation for a given frequency-sparse signal (i.e., vector) $\textbf{A}$ of length $N \gg B$. More explicitly, we investigate how to deterministically identify B of the largest magnitude frequencies of $\hat{\textbf{A}}$, 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) \cite{CMDetCS3,CMDetCS1,CMDetCS2} 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.

Affiliated with

Also associated with

No associations

Rating

A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-417074