Performance of polynomial rooting algorithms

Performance of polynomial rooting algorithms

Dejan Markovic
DEI PhD Student

DEI - 2A Room
November 17th, 2011
4.30 pm


A number of applications in engineering require finding roots of a polynomial. Usually the coefficients of these polynomials are obtained through measurements or after processing of input data. As a consequence they are affected by random perturbation due to noise or estimation error. Depending on the context, the root positions are used to determine frequency, directions of arrival (DOA's), time of arrival (TOA), etc. In this work we collect some results and make a few remarks on the performance of polynomial rooting algorithms for perturbations with arbitrary correlation. In particular we review a few well known applications in signal processing , ARMA models and subspace methods for line spectral analysis such as root-MUSIC, and we derive the first and second order moments of root estimates for a generic, complex, Nth order polynomial. The results presented here are derived independently from a particular application and will turn useful in all problems that require finding roots of a noisy polynomial. They can be used to determine statistical properties and give insight into the behavior of the algorithm for different statistics of the input perturbation.

Research area: