Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Daniel Potts, Manfread Tasche: Fast ESPRIT algorithms based on partial singular value decompositions

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

Presseartikel

  • MINT gewinnt

    Drei sächsische Hochschulen verfolgen unterschiedliche Konzepte, um Studieninteressenten Mathematik, Informatik, Naturwissenschaften und Technik schmackhaft zu machen …

  • Mathematik ganz alltagsnah

    „Videowoche der Mathematik“ zeigt das Fach von seiner spannenden, menschlichen und alltagstauglichen Seite …

  • Wahlzeit an der Universität

    Wahlvorschläge für Organe und Ämter an der TU Chemnitz können bis zum 23. Oktober 2017 eingereicht werden – Briefwahlanträge sind bis 27. Oktober 2017 zu stellen …