I have a large matrix $\mathbf{A}\in \mathbb{C}^{m\times n}$ with very low rank $r$, I find that the general complexity of finding its pseudoinverse is $\mathcal{O}(\max(m,n)^3)$, this is too high. Is there any method to reduce the complexity?
2
-
$\begingroup$ arxiv.org/abs/2011.04235 $\endgroup$– Steve HuntsmanCommented Dec 29, 2020 at 14:51
-
$\begingroup$ I am not sure how you got that complexity, but it seems way off. Using thin SVD without any particular optimization it would cost $O(\max \min^2)$. $\endgroup$– Federico PoloniCommented Dec 29, 2020 at 16:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can use the trick from my answer here to compute an economy-sized SVD of $A$ in cost $O(mnr)$:
You can run rank-revealing QR on your matrix $A$, which will stop at step $k$ (hence effectively terminating in $O(mnk)$) and produce $A = QRP$, where $R$ has nonzeros only in its first $k$ rows, and $Q,P$ are orthogonal. You can now compute and SVD of $R$, and use it to piece back the factors with a few matrix products with cost $O(\max(m,n)k^2)$.
From this SVD, you have a closed-form expression for the pseudoinverse, $A^+ =VS^+U^T$. Note that it is often cheaper to work with the three factors individually rather than forming the product.
answered Dec 29, 2020 at 16:21