  Minimization of the nuclear norm is often used as a surrogate, convex
relaxation, for finding the minimum rank completion (recovery) of a partial
matrix. The minimum nuclear norm problem can be solved as a trace minimization
semidefinite programming problem, (SDP). The SDP and its dual are regular in
the sense that they both satisfy strict feasibility. Interior point algorithms
are the current methods of choice for these problems. This means that it is
difficult to solve large scale problems and difficult to get high accuracy
solutions.
  In this paper we take advantage of the structure at optimality for the
minimum nuclear norm problem. We show that even though strict feasibility
holds, the facial reduction framework can be successfully applied to obtain a
proper face that contains the optimal set, and thus can dramatically reduce the
size of the final nuclear norm problem while guaranteeing a low-rank solution.
We include numerical tests for both exact and noisy cases. In all cases we
assume that knowledge of a target rank is available.
