Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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)$.

share|cite|improve this answer
Thank you for the answer! I got the paper and found it seems I lack the background. Are there some good introductions/survey on this kind of result? I know the Algebraic Complexity Theory book is a good one but currently it's checked out of the library... – Chao Xu Apr 24 '14 at 19:41
There might be relevant lecture notes, though it's probably best to take a look at the book. CLRS (Introduction to Algorithms) also contains some relevant material, such as the equivalence between matrix multiplication and matrix inverse. – Yuval Filmus Apr 24 '14 at 22:14
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.