#eth/cil/theory

SVD and Matrix Completion

We generalize the simple rank 1 model to a rank k approximation.
We do this by additive superposition of k rank 1 matrices.
If all matrix entries are completely obeserved, the solution is constructively given by the SVD.

k principal left singular vectors, paired with the respective right singular vector form outer products:

A≈∑i=1kσiuiviT
Low-rank matrix approximation is non-convex, even for the completely observed case

$

SVD

Computation Complexity

SVD is computable in O(min{nm2,mn2}