High Rank Matrix Completion With Side Information
High Rank Matrix Completion With Side Information
复制标题
DOI：
10.1609/aaai.v32i1.11809
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Yugang Wang;Ehsan Elhamifar
中科院分区：
文献类型：
--
作者：
Yugang Wang;Ehsan Elhamifar
本文研究了带边信息的高秩矩阵完备化问题。与现有的工作处理边信息，假设数据矩阵是低秩的，我们考虑更一般的情况下，数据矩阵的列是从一个联盟的低维子空间，这可能会导致一个高秩矩阵。我们的目标是在利用边信息的同时完成矩阵。为此，我们使用数据的自我表达属性，将矩阵的每一列搜索为其他几列的组合的稀疏表示。更具体地说，我们提出了一个因式分解的数据矩阵作为产品的侧信息矩阵与未知的相互作用矩阵，根据该数据矩阵的每一列可以使用其他列的稀疏组合重建。由于我们提出的优化，寻找丢失的条目和稀疏系数，是非凸的和NP-困难的，我们提出了一个提升框架，在这里我们耦合稀疏系数和丢失值，并定义一个等价的优化，这是服从凸松弛。我们还提出了一个快速实现我们的凸框架使用线性交替方向方法。通过对合成数据和真实的数据的大量实验，特别是通过研究多标签学习问题，我们证明了我们的方法在低秩和高秩数据制度中优于现有技术。
We address the problem of high-rank matrix completion with side information. In contrast to existing work dealing with side information, which assume that the data matrix is low-rank, we consider the more general scenario where the columns of the data matrix are drawn from a union of low-dimensional subspaces, which can lead to a high rank matrix. Our goal is to complete the matrix while taking advantage of the side information. To do so, we use the self-expressive property of the data, searching for a sparse representation of each column of matrix as a combination of a few other columns. More specifically, we propose a factorization of the data matrix as the product of side information matrices with an unknown interaction matrix, under which each column of the data matrix can be reconstructed using a sparse combination of other columns. As our proposed optimization, searching for missing entries and sparse coefficients, is non-convex and NP-hard, we propose a lifting framework, where we couple sparse coefficients and missing values and define an equivalent optimization that is amenable to convex relaxation. We also propose a fast implementation of our convex framework using a Linearized Alternating Direction Method. By extensive experiments on both synthetic and real data, and, in particular, by studying the problem of multi-label learning, we demonstrate that our method outperforms existing techniques in both low-rank and high-rank data regimes.