Skip to main content
3 of 3
formatting, added tag
YCor
  • 63.9k
  • 5
  • 187
  • 286

Complexity of singular value decomposition using matrix multiplication oracles

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}$?

AspiringMat
  • 662
  • 4
  • 13