11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.? $\endgroup$ – Mike Pomp Aug 31 '18 at 8:45
  • $\begingroup$ 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. $\endgroup$ – David Richerby Aug 31 '18 at 12:35
  • $\begingroup$ Since this is an easy question, I've answered it here. However, if you have any further questions, please ask them as a page on their own using the "ask question" button at the top of the page. You can link back to this page to give context. This site is only set up for one question per page: there's no threading and posts move around according to the votes they get, so things get awfully messy with more than one question on a page. There's more information at our short tour and in our help center. $\endgroup$ – David Richerby Aug 31 '18 at 12:37
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Chao Xu Apr 24 '14 at 19:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 24 '14 at 22:14
  • $\begingroup$ So $O(n^ω)$ holds in general? Can you give me a hint what the "Matrix multiplication constant" $w$ is? $\endgroup$ – ben Apr 27 '15 at 20:18
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Apr 27 '15 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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