Praneeth Netrapalli Provable Matrix Completion using Alternating Minimization AltMin Sensing Completion Proof References

To minimize f (X) over rank-k matrices X, repeat the following: fix U and minimize f (UV †)over V fix V and minimize f (UV †)over U X U V' A popular Empirical approach to solve low rank matrix problems eg. matrix completion, clustering etc. Challenge: few theoretical guarantee