Daniel Potts, Manfread Tasche: Fast ESPRIT algorithms based on partial singular value decompositions

Author(s):

Daniel Potts
Manfread Tasche

Title:

Daniel Potts, Manfread Tasche: Fast ESPRIT algorithms based on partial singular value decompositions

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 09, 2014

Mathematics Subject Classification:

    65F15 []
    65F20 []
    94A12 []

Abstract:

Let $h(x)$ be a nonincreasing exponential sum of order $M$. For $N$ given noisy sampled values $h_n = h(n) + e_n$ $(n=0,\ldots, N-1)$ with small error terms $e_n$, all parameters of $h(x)$ can be estimated by the known ESPRIT (Estimation of Signal Parameters via Rotational Invariance Techniques) method. The ESPRIT method is based on singular value decomposition (SVD) of the $L$-trajectory matrix $(h_{\ell +m})_{\ell,m=0}^{L-1,N-L}$, where the window length $L$ fulfils $M\le L \le N-M+1$. The computational cost of the ESPRIT algorithm is dominated by the cost of SVD. In the case $L \approx \frac{N}{2}$, the ESPRIT algorithm based on complete SVD costs about $\frac{21}{8}\,N^3 + M^2 (21\, N + \frac{91}{3}\,M)$ operations. Here we show that the ESPRIT algorithm based on partial SVD and fast Hankel matrix-vector multiplications has much lower cost. Especially for $L \approx \frac{N}{2}$, the ESPRIT algorithm based on partial Lanczos bidiagonalization with $S$ steps requires only about $18\,SN\, \log_2 N + S^2(20 N + 30 S) + M^2 (N + \frac{1}{3}M)$ operations, where $M \le S \le N-L+1$. Numerical experiments demonstrate the high performance of these fast ESPRIT algorithms for noisy sampled data with relatively large error terms, for data with large number of samples, and for data of an exponential sum with large order.

Keywords:

ESPRIT algorithm, exponential sum, rectangular Hankel matrix, partial singular value decomposition, partial Lanczos bidiagonalization, computational cost

Language:

English

Publication time:

10/2014