The reviewers were split on this paper. On the positive side the authors have given an algorithm that takes advantage of side information in a provable way that can lead to perfect recovery with a novel algorithm. On the negative side their were concerns about the synthetic nature of experiments as well as brittleness of theoretical set-up. Overall, I suggest that this paper should be accepted for its provable advance in its utilization of side-information for matrix recovery.