加速的乘法迭代算法（A-MU）

D.D.Lee和H.S.Seung在2001年的NIPS上发表得乘法迭代更新（MU）算法用矩阵形式表示MU算法1，如下(考虑W的更新，对于H类似)：

其中 $\circ$ 表示矩阵元素分别相乘。

对于它存在着收敛慢的问题，尤其是处理密集矩阵，一些人提出了新的算法来解决（如ANLS和HALS），Nicolas Gillis1an和Francois Glineur（2011）提出了一种加速MU的算法，并取得了很好的效果。

为了确定内部迭代的次数，NicolasGillis1an和Francois Glineur（2011）给出了3种停止准则。

（1） 固定次数的内部迭代

（2）动态的停止准则

（3）层次的停止准则（两种方法的结合）

从上面的实验可以看出固定次数的内部迭代效果要好于动态的内部迭代，但是它可能有迭代次数过多，无用或者效率不高迭代的问题。如：若 $\rho _W$ 特别大，那么W的更新次数还会很多，若未达到最大迭代次数过程已经满足动态停止的条件，就会造成极大的计算浪费。所以我们有时需要在两个停止准则之间转换。因此NicolasGillis1an和Francois Glineur（2011）提出了层次的停止准则（两种方法的结合）。算法如下：

Nicolas Gillis1an和Francois Glineur（2011）提出这种加速方法不仅可以用于MU算法，也可以将这种思想用于HALS，PG等算法中。并且他们通过实验（通过比较MU，A-MU，HALS，A-HALS，PG，A-PG和ANLS）也证明了这种加速思想的可行性和高效性。

转载本文请联系原作者获取授权，同时请注明本文来自赵龙科学网博客。
链接地址： https://blog.sciencenet.cn/blog-795427-679899.html

上一篇： NMF概要
下一篇： NMF概要