Suppose I have an $n\times m$ real matrix $A$, $n\ll m$ with full row rank $(\mathrm{rank}(A) = n)$. I have an oracle that can compute $Ax$ or $A^T y$ for any $x\in \mathbb{R}^m, y\in \mathbb{R}^n$. How many oracle calls do I need (asymptotically) to calculate the "economy" SVD decomposition of $A$, namely $A=U_{n\times n}\Sigma_{n\times n} V^T_{n\times m}$?
Complexity of singular value decomposition using matrix multiplication oracles
AspiringMat
- 662
- 4
- 13