二值分解压缩和Consensus算法

奇异值分解(SVD)是一种流行的用于高维数据压缩的方法,二值分解是奇异值分解的一种简化形式。实现二值分解的主要算法有两种:迭代启发式算法和贪婪算法。但这两种算法都不是很理想的算法:迭代启发式算法在很多情况下不能保证收敛性,贪婪算法不满足大型数值矩阵分解的需要。采用了一种新的算法来实现二值分解:Consensus的算法。Consensus算法可在渐进多项式时间内找到一般图中的极大二分团。对于某些二分图,该算法的复杂度是多项式时间的。实验结果表明,当迭代启发式算法不起作用时,Consensus算法是一种很好的求解二值分解的方法。该算法远比贪婪算法的效率高,且具有稳定收敛性。