Fast ESPRIT algorithms based on partial singular value decompositions

作者：Potts Daniel^*; Tasche Manfred

来源：Applied Numerical Mathematics, 2015, 88: 31-45.

DOI：10.1016/j.apnum.2014.10.003

• ESPRIT algorithm
• Exponential sum
• Rectangular Hankel matrix
• Partial singular value decomposition
• Partial Lanczos bidiagonalization
• Computational cost

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,..., N-1) with 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(l+m))(l,m=0)(L-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 approximate to N/2, the ESPRIT algorithm based on complete SVD costs about 21/8N(3) + M-2 (21N + 91/3M) 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 approximate to N/2, the ESPRIT algorithm based on partial Lanczos bidiagonalization with S steps requires only about 18SN log(2) N + S-2(20N + 30S) + M-2(N + 1/3M) 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.

• 出版日期2015-2