# 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.? Commented Aug 31, 2018 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. Commented Aug 31, 2018 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 at most $$C_\gamma n^\gamma$$, where $$C_\gamma$$ is a constant depending on $$\gamma$$ (possibly $$C_\gamma \to \infty$$ as $$\gamma \to \omega$$).
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?
• 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$. Commented Apr 27, 2015 at 21:35