MMDec, 2010

带权重或缺失数据的低秩矩阵逼近是 NP 难的

TL;DR本文研究了带权低秩逼近算法的计算复杂度,并证明了即使在寻求秩为一的逼近解时,找到近似解也是 NP 难的,该证明基于最大边双团问题的约化并适用于严格正权重和二进制权重。