Facial Reduction (FR) for Semidefinite Programming (SDP) with
applications to Low-Rank Matrix Completion (LRMC).

SDP relaxations are extremely successful for many numerically hard
problems. Of interest is that many of these SDP relaxations are
degenerate in that strict feasibility fails. We look at FR for
regularizing the SDP relaxations. In addition, we show that the
degeneracy can be turned to an advantage.

In particular, we look at LRMC.
Minimization of the NN is often used as a surrogate, convex
relaxation, for solving LRMC problems.
The minimum NN problem can be solved as a trace minimization
semidefinite program (SDP). The SDP and its dual are regular
in the sense that they both satisfy strict feasibility.
Here we take advantage of the structure at optimality for the NN
minimization and show that even though strict
feasibility holds, the FR framework can be successfully applied 
to obtain a proper face that contains the optimal set. This can
dramatically reduce the size of the final NN problem while
guaranteeing a low-rank solution. We include numerical tests for 
both exact and noisy cases.

(work with Shimeng Huang)