Null space conditions and thresholds for rank minimization
Null space conditions and thresholds for rank minimization
复制标题
DOI：
10.1007/s10107-010-0422-2
复制
发表时间：
2011-03-01
影响因子：
2.7
通讯作者：
Hassibi, Babak
中科院分区：
文献类型：
--
作者：
Recht, Benjamin;Xu, Weiyu;Hassibi, Babak
在机器学习、控制理论和离散几何的许多应用中，最小化受约束的矩阵的秩是一个具有挑战性的问题。这类优化问题，称为秩最小化，是NP难的，对于大多数实际问题，没有有效的算法产生精确的解决方案。一个流行的启发式取代的秩函数与核范数等于奇异值的总和的决策变量，并已被证明提供最佳的低秩解决方案在各种情况下。在本文中，我们评估的实际表现，这种启发式寻找最低秩矩阵的线性等式约束。我们的零空间的线性算子定义的约束集，是必要的和充分的启发式成功的特性。然后，我们分析线性约束随机均匀采样，并获得无量纲的界限下，我们的零空间属性几乎肯定持有的矩阵维数趋于无穷大。最后，我们提供的经验证据表明，这些概率界提供了准确的预测的启发式的性能在非渐近的情况下。
Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in machine learning, control theory, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-hard, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic replaces the rank function with the nuclear norm-equal to the sum of the singular values-of the decision variable and has been shown to provide the optimal low rank solution in a variety of scenarios. In this paper, we assess the practical performance of this heuristic for finding the minimum rank matrix subject to linear equality constraints. We characterize properties of the null space of the linear operator defining the constraint set that are necessary and sufficient for the heuristic to succeed. We then analyze linear constraints sampled uniformly at random, and obtain dimension-free bounds under which our null space properties hold almost surely as the matrix dimensions tend to infinity. Finally, we provide empirical evidence that these probabilistic bounds provide accurate predictions of the heuristic's performance in non-asymptotic scenarios.