Polynomial EVD and Algorithms

Polynomial matrices arise, for example, in many broadband array or multichannel signal processing problems, where explicit lags between channels need to be considered, and the phase difference captured by a (narrowband) instantaneous covariance matrix would be insufficient. The resulting space-time covariance matrix therefore contains auto- and cross-correlation sequences as entries; its z-transform, the cross power spectral density (CSD) matrix, is a polynomial matrix. The symmetry structure of this matrix is an extension of the Hermitian property to a parahermitian matrix: the polynomial matrix identical to its Hermitian transposed, time reversed version.

This toolbox provides algorithms to extend the utility of the eigenvalue decomposition (EVD) to the polynomial case via a polynomial EVD (PEVD). The PEVD provides a factorisation of a parahermitian matrix $$ \small{\boldsymbol{R}(z) \approx \boldsymbol{H}(z) \boldsymbol{D}(z) \tilde{\boldsymbol{H}}(z)} $$ where \(\small{\boldsymbol{H}(z)}\) is a paraunitary matrix such that the product with its parahermitian, \(\small{\tilde{\boldsymbol{H}}(z)}\), yields \(\small{\boldsymbol{H}(z)\tilde{\boldsymbol{H}}(z)=\mathbf{I}}\). The parahermitian \(\small{\boldsymbol{D}(z)}\) is diagonalised $$ \small{\boldsymbol{D}(z) = \left[ \begin{array}{cccc} D_1(z) & & & \\ & D_2(z) & & \\ & & \ddots & \\ & & & D_M(z) \end{array} \right]} $$ and spectrally majorised such that the power spectral densities \(\small{D_m(e^{j\Omega}) =D_m(z)|_{z=e^{j\Omega}}}\) are ordered at all frequencies: $$ \small{D_m(e^{j\Omega}) \geq D_{m+1}(e^{j\Omega}) \qquad \forall m=1 \dots (M-1) \quad \forall \Omega} \quad. $$ The approximation sign in the PEVD factorisation can generally be achieved well with FIR paraunitary matrices of sufficiently high order.

The iterative PEVD algorithms within this toolbox fall into two families of algorithms: 2nd order sequential best rotation (SBR2) and sequential matrix diagonalisation (SMD) algorithms. Iterative by nature, these algorithms will aim to diagonalise a parahermitian matrix by means of paraunitary (i.e. lossless) matrices. All algorithms have been proven to convergence towards a diagonal matrix. Additionally, both SBR2 and SMD algorithms enforce (but cannot guarantee) spectral majorisation, i.e. the power spectral densities along the main diagonal of the CSD matrix will be strictly order at all frequencies.

Please note that the SBR2 algorithm is subject of a patent owned by QinetiQ. QinetiQ has given permission for its free use in university research, but at present its use in a commercial application without license from QinetiQ would be an infringement of the patent.

Details of the above PEVD algorithms are covered in the following publications:

  1. J.G. McWhirter, P.D. Baxter, T. Cooper, S. Redif, and J. Foster, "An EVD Algorithm for Para-Hermitian Polynomial Matrices," IEEE Transactions on Signal Processing, vol. 55, no. 5, pp. 2158-2169, May 2007.
  2. S. Redif, J.G. McWhirter, and S. Weiss, "Design of FIR Paraunitary Filter Banks for Subband Coding Using a Polynomial Eigenvalue Decomposition," IEEE Transactions on Signal Processing, vol. 59, no. 11, pp. 5253-5264, Nov 2011.
  3. S. Redif, S. Weiss, and J.G. McWhirter, "Sequential Matrix Diagonalisation Algorithms for Polynomial EVD of Parahermitian Matrices," to appear in IEEE Transactions on Signal Processing.