An interesting observation here is that the nuclear norm minimization is able to successfully to solve this problem.
[1]} have shown that the following convex optimization program returns the exactly recovered low-rank matrix:
