Fast realization of root MUSIC using multi-taper real polynomial rooting

The computational complexity of root MUSIC, which is on the order of (2N−2)3, turns out to be computationally expensive when N is large, where N is the number of array elements. To reduce the computational complexity, an efficient implementation of root MUSIC using the multi-taper rooting technique is developed. It decomposes the (2N−2)-order complex polynomial as 2N−1 groups of low order real polynomials by the multi-taper fast Fourier transform (FFT). Then, all roots can be simultaneously solved with low complexity. Numerical examples are given to demonstrate the effectiveness of the presented method.