1. Advanced algorithms for polynomial matrix eigenvalue decomposition
- Author
-
Corr, Jamie
- Subjects
621.3 - Abstract
Matrix factorisations such as the eigen- (EVD) or singular value decomposition (SVD) offer optimality in often various senses to many narrowband signal processing algorithms. For broadband problems, where quantities such as MIMO transfer functions or cross spectral density matrices are conveniently described by polynomial matrices,such narrowband factorisations are suboptimal at best. To extend the utility of EVD and SVD to the broadband case, polynomial matrix factorisations have gained momentum over the past decade, and a number of iterative algorithms for particularly the polynomial matrix EVD (PEVD) have emerged. Existing iterative PEVD algorithms produce factorisations that are computationally costly (i) to calculate and (ii) to apply. For the former, iterative algorithms at every step eliminate off-diagonal energy, but this can be a slow process. For the latter,the polynomial order of the resulting factors, directly impacting on the implementation complexity, typically grows with every iteration of a PEVD algorithm. The work presented in this thesis helps to reduce both computational complexities. To address algorithmic complexity and convergence speed, this thesis firstly proposes a multiple shift approach, which can eliminate more off-diagonal energy at every iteration compared to existing methods. Equally applicable to the second order sequential best rotation (SBR2) algorithm, the idea here is applied to the family of sequential matrix diagonalisation (SMD) algorithms, for which a convergence proof is presented. Maximum energy transfer requires a very laborious parameter search; it is demonstrated that a very significant reduction of this search space can be gained while retaining almost all of the transfered energy. In addition a number of techniques have been developed which improve the efficiency of these PEVD algorithms. With each PEVD algorithm iteration the lengths of the polynomial eigenvectors and eigenvalues increase. To lower the order of the polynomial eigenvectors a novel truncation technique was developed which takes advantage of an ambiguity in the eigenvalues. A drawback of the multiple shift algorithms is the faster growth of the polynomial eigenvectors and eigenvalues; to mitigate this the search step has been analysed and modified to reduce the growth. The SMD algorithm suffers from a performance bottleneck in its EVD step. Here a cyclic-by-row Jacobi approximation is developed that significantly reduces the computational cost of the SMD algorithm with almost no impact on numerical performance. The impact of these algorithmic advances is studied in a number of applications. Firstly, based on a source model, it is investigated how the conditioning of the input data affects algorithm performance. Secondly, to highlight the benefit of the better converging multiple shift SMD algorithm it is compared to the SBR2 algorithm for broadband angle of arrival estimation, where the proposed multiple shift versions can achieve a more accurate subspace decomposition and hence a more accurate AoA estimation. Lastly, its demonstrated how PEVD algorithms can be utilised to extend other linear algebraic techniques to polynomial matrices. The example used here is the extension of the generalised eigenvalue decomposition (GEVD) to a polynomial matrix GEVD.
- Published
- 2017
- Full Text
- View/download PDF