非負(fù)矩陣分解

AlgorithmsforNon-negativeMatrixFactorization精讀報(bào)告

在科學(xué)研究中，矩陣是最常被使用到的一種處理海量數(shù)據(jù)的數(shù)學(xué)表達(dá)方式。然而，數(shù)據(jù)直接對(duì)應(yīng)的矩陣信息分布往往不均勻且維度極大，計(jì)算時(shí)效率不高。為了解決這個(gè)問(wèn)題，科學(xué)家們提出了矩陣分解這一概念。背景DanielD.Lee和H.SebastianSeung于1999年提出了非負(fù)矩陣分解算法〔Al-gorithmsforNon-negativeMatrixFact-orization,NMF〕，它是矩陣分解最根本的方法之一。

根本思想

？Yes以乘法規(guī)那么更新W〔或H〕No得到分解因子使用某些測(cè)度方法來(lái)量化相似結(jié)果的質(zhì)量代價(jià)函數(shù)1.最小化歐氏距離

2.最小化K-L離散度更新規(guī)那么定理1歐氏距離||V-WH||在如下的更新規(guī)那么下非增定理2K-L散度D(V||WH)在如下的更新規(guī)那么下非增首先，引入輔函數(shù)的概念：收斂性證明定義1：當(dāng)，時(shí)，是的輔函數(shù)。推理1假設(shè)G是F的輔函數(shù)，那么F在如下的更新規(guī)那么下非增證明：當(dāng)且僅當(dāng)是的極小值時(shí)成立。每次迭代更新h后的F(h)(1)均比前一次小。h推理2令為對(duì)角矩陣：那么是如下函數(shù)的輔函數(shù)(2)(3)(4)為半正定矩陣，因此同半正定證明：顯見(jiàn)G(h,h)=F(h)，只需證將F(h)使用泰勒級(jí)數(shù)展開(kāi)假設(shè)假設(shè)成立，必然有，將(3)(5)代入(5)當(dāng)半正定時(shí)，不等式成立經(jīng)過(guò)證明，形如得證定理1證明：對(duì)(3)求導(dǎo)，將結(jié)果代入(1)化簡(jiǎn)，得轉(zhuǎn)換W和H的角色，同理可得W的更新規(guī)那么。推理3(5)是如下函數(shù)的輔函數(shù)：(6)證明：顯見(jiàn)，G(h,h)=F(h)，只需證根據(jù)對(duì)數(shù)函數(shù)單調(diào)遞增的性質(zhì)，可得如下不等式令得此不等式亦為將(5)(6)代入的結(jié)果，為真，故得證。定理2證明：對(duì)(5)求導(dǎo)化簡(jiǎn)，得轉(zhuǎn)換W和H的角色，同理可得W的更新規(guī)那么。相關(guān)工作NMF經(jīng)過(guò)十多年的開(kāi)展，已經(jīng)成為了一個(gè)相對(duì)成熟的數(shù)據(jù)分析手段。其之所以得到研究人員的青睞，主要?dú)w功于其分解結(jié)果有較為明確的物理意義。AlgorithmsforNon