Fast ESPRIT algorithms based on partial singular value decompositions

Let h(x) be a nonincreasing exponential sum of order M. For N given noisy sampled values hn=h(n)+en (n=0,…,N−1) with error terms en, 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ℓ+m)ℓ,m=0L−1,N−L, where the window length L fulfills M≤L≤N−M+1. The computational cost of the ESPRIT algorithm is dominated by the cost of SVD. In the case L≈N2, the ESPRIT algorithm based on complete SVD costs about 218N3+M2(21N+913M) 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≈N2, the ESPRIT algorithm based on partial Lanczos bidiagonalization with S steps requires only about 18SNlog2⁡N+S2(20N+30S)+M2(N+13M) operations, where M≤S≤N−L+1. Numerical experiments demonstrate the high performance of these fast ESPRIT algorithms for noisy sampled data with relatively large error terms.