|
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. |
