Low-rank matrix completion using nuclear norm minimization and facial reduction

Minimization of the nuclear norm, NNM, 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. Interior point algorithms are the current methods of choice for this class of problems. This means that it is difficult to: solve large scale problems; exploit sparsity; and get high accuracy solutions. The SDP and its dual are regular in the sense that they both satisfy strict feasibility. In this paper we take advantage of the structure of low rank solutions in the SDP embedding. We show that even though strict feasibility holds, the facial reduction framework used for problems where strict feasibility fails can be successfully applied to generically obtain a proper face that contains all minimum low rank solutions for the original completion problem. This can dramatically reduce the size of the final NNM problem, while simultaneously guaranteeing a low-rank solution. This can be compared to identifying part of the active set in general nonlinear programming problems. In the case that the graph of the sampled matrix has sufficient bicliques, we get a low rank solution independent of any nuclear norm minimization. We include numerical tests for both exact and noisy cases. We illustrate that our approach yields lower ranks and higher accuracy than obtained from just the NNM approach.