# Complexity of finding the pseudoinverse matrix

How many arithmetic operations are required to find a Moore–Penrose pseudoinverse matrix of a arbitrary field?

If the matrix is invertible and complex valued, then it's just the inverse. Finding the inverse takes $O(n^\omega)$ time, where $\omega$ is the matrix multiplication constant. It is Theorem 28.2 in Introduction to Algorithms 3rd Edition.

If the matrix $A$ has linearly independent rows or columns and complex valued, then the pseudoinverse matrix can be computed with $A^*(A A^*)^{-1}$ or $(A A^*)^{-1}A^*$ respectively, where $A^*$ is the conjugate transpose of $A$. In particular, this implies an $O(n^\omega)$ time for finding the pseudoinverse of $A$.

For general matrix, the algorithms I have seen uses QR decomposition or SVD, which seems to take $O(n^3)$ arithmetic operations in the worst case. Is there algorithms that uses fewer operations?

• I have a follow up, It might be too basic but can you please confirm what is n here in the complexity equation . Is it the dimension of a matrix and what if the matrix is not a square.? – Mike Pomp Aug 31 '18 at 8:45
• In the claim that the inverse can be found in $O(n^\omega)$ time, $n$ is indeed the dimension of the square matrix; if the matrix isn't square, you can probably take $n$ to be the larger dimension. – David Richerby Aug 31 '18 at 12:35
First of all, people tend to forget that $\omega$ is an infimum. Whenever we write $O(n^\omega)$, we actually mean for all $\gamma > \omega$, there is an algorithm running in time $O_\gamma(n^\gamma)$.
Keller-Gehrig showed (among else) how to present a matrix $A$ in rank normal form in time $O(n^\omega)$. If $A$ has rank $r$, then a rank normal form of $A$ is $$S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T$$ for some invertible $S,T$ of the appropriate dimensions; see also Algebraic Complexity Theory, Proposition 16.13 on page 435.
Rank normal form is similar to the rank decomposition mentioned in the Wikipedia article, $A = XY$ where $X$ has $r$ columns and $Y$ has $r$ rows. Indeed, we can take $X$ to be the first $r$ columns of $S$, and $Y$ to be the first $r$ rows of $T$. Given this decomposition, Wikipedia gives a formula for the pseudoinverse using only Hermitian adjoint, matrix multiplication and matrix inverse. Therefore the pseudoinverse can be computed in time $O(n^\omega)$.
• So $O(n^ω)$ holds in general? Can you give me a hint what the "Matrix multiplication constant" $w$ is? – ben Apr 27 '15 at 20:18
• We don't know the value of $\omega$. The best upper bound, due to Le Gall, is $\omega < 2.3728639$. It is conjectured that $\omega = 2$. – Yuval Filmus Apr 27 '15 at 21:35