Generalised matrix inversion and rank computation by successive matrix powering (Q1319512): Difference between revisions

The authors derive an iterative scheme to compute the generalised inverse \(A^ +\) of an arbitrary matrix \(A \in\mathbb{C}^{m \times n}\). If \(m \cong n\), they show that \(A^ +\), and its rank, can be computed in parallel time ranging from \(O(\log n)\) to \(O(\log^ 2n)\). It is first shown that the unique generalised inverse of \(A\) is the solution of a simple matrix equation \(X=PX+Q\), where \(P=I - \beta A^ HA\), \(Q=\beta A^ H\), \(\beta\) being a relaxation parameter. The iterative scheme for \(X\) is \(X_{K+1} = PX_ K + Q\), with \(X_ 1=Q\), and this can be computed in parallel by considering \[ T={P\;Q \brack 0\;I},\quad \text{ so that } \quad T^ K = \left[ \begin{matrix} P^ K & \sum^{K-1}_{i=0} P^ iQ \\ 0 & I \end{matrix} \right]. \] The top right block of \(T^ K\) is \(X_ K\), the \(K^{\text{th}}\) approximant to \(A^ +\). \(T^ K\) can be computed by repeated squaring, namely \(T_{i+1} = T^ 2_ i\), with \(T_ 0=T\). If suitable assumptions about the number of available processors are made, \(T_ K\) can be computed in \(O(K \log (m+n))\) time. The number of iterations required to guarantee required accuracy is determined in terms of this accuracy and the condition number of \(A^ +\). It is pointed out that the algorithm may be modified to find least squares solutions of the linear system \(Ax=b\). The paper concludes with a discussion of an implementation of the algorithm on a CM-5 general purpose parallel machine.