标题： 一种组合代数方法用于低秩矩阵完成的可识别性研究 显示英文标题

标题： A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion

摘要： 本文中，我们回顾了矩阵完成问题，并揭示了它与代数几何、组合学和图论之间的密切关系。 我们提出了对于任意秩的矩阵从一组矩阵条目中可识别的第一个充分必要组合条件，从而为矩阵完成问题提供了理论约束和新算法。 最后，我们通过算法评估所给条件和算法在实际相关矩阵大小下的紧密性，表明代数-组合方法可以带来优于现有矩阵完成方法的改进。 显示英文摘要

摘要： In this paper, we review the problem of matrix completion and expose its intimate relations with algebraic geometry, combinatorics and graph theory. We present the first necessary and sufficient combinatorial conditions for matrices of arbitrary rank to be identifiable from a set of matrix entries, yielding theoretical constraints and new algorithms for the problem of matrix completion. We conclude by algorithmically evaluating the tightness of the given conditions and algorithms for practically relevant matrix sizes, showing that the algebraic-combinatoric approach can lead to improvements over state-of-the-art matrix completion methods.