T:A:L:K:S

close this window
title:
Stable Sparse FFT for Nonnegative Vectors
name:
Plonka-Hoch
first name:
Gerlind
location/conference:
SPP-JT14
PRESENTATION-link:
http://www.dfg-spp1324.de/nuhagtools/event_NEW/dateien/SPP-JT14/slides/plonka_fc14.pdf
abstract:
We propose a deterministic stable FFT algorithm to compute a sparse vector x from its Fourier transformed vector.
In case of nonnegative vectors being M-sparse, we need at most min {M log(N), N } Fourier values in order to recover x and at most O(M^{2} log N) arithmetical operations.
The algorithm works iteratively and does not incorporate any a priori knowledge on the sparsity M of x.
Each iteration step only involves the solution of a linear system of size at most $M$.
We develop an adaptive
strategy to ensure that the coefficient matrix in the linear system is well-conditioned.
For this purpose, we have to study Vandermonde matrices with knots on the unit circle. The talk is based on joint work with Katrin Wannenwetsch.