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.

核范数最小化（NNM）通常被用作寻找部分矩阵的最小秩填充（恢复）的替代（凸松弛）方法。最小核范数问题可作为一个迹最小化半定规划问题（SDP）来求解。内点算法是这类问题当前的首选方法。这意味着在以下方面存在困难：解决大规模问题；利用稀疏性；以及获得高精度的解。SDP及其对偶在它们都满足严格可行性的意义上是正则的。在本文中，我们利用了SDP嵌入中低秩解的结构。我们表明，即使满足严格可行性，用于严格可行性不成立的问题的面约简框架也可成功应用，以一般性地获得一个包含原始填充问题所有最小低秩解的恰当面。这可以极大地减小最终NNM问题的规模，同时保证一个低秩解。这可与在一般非线性规划问题中识别活动集的一部分相类比。在采样矩阵的图具有足够的二部图的情况下，我们得到一个与任何核范数最小化无关的低秩解。我们包含了精确情况和含噪情况的数值测试。我们说明我们的方法比仅从NNM方法获得的秩更低且精度更高。