低秩分塊矩陣的核近似

王中元，劉驚雷

（煙臺大學 計算機與控制工程學院，山東 煙臺 264005）

近年來，隨著互聯網的快速發展，人們獲取數據以及存儲數據的能力都迅速提高。不論在科學技術還是在日常生活的各個領域都累積了大量數據。怎樣才能快速有效地對這些數據進行分析處理并發掘其中蘊含的有效信息引起人們的關注。大部分機器學習都能夠通過矩陣的形式表示，但是在現實生活中經常會使用到數以百萬記的樣本，通過對矩陣進行處理的機器學習技術的復雜度會隨著應用規模的增加呈二次方增長，這會使很多問題無法解決。

目前通常通過低秩矩陣分解、核方法和聚類等方法來解決矩陣分解的問題[1]。聚類是將輸入數據按照某種相似性規則劃分為若干類。低秩矩陣分解是將數據矩陣分解成噪聲和稀疏低秩兩部分。在眾多方法之中，通過核方法近似低秩分塊矩陣由于其模型合理直觀、實施簡單、效果顯著而受到關注。

本文考慮結構受限下的矩陣分解問題[2]，其中結構受限主要是低秩結構受限和分塊結構受限。本文通過消除噪聲并最小化塊外對角線來增強類與類之間數據表示的不相關性，從而實現分塊約束[3]；同時通過增強訓練樣本的自表達屬性并縮小樣本之間的差距來增強類內數據表示的相關性，從而實現低秩約束[4]，最后迭代優化求解一系列子問題來實現矩陣分解的目的。隨后設計了一個低秩分塊矩陣的核近似算法(low-rank block kernel approximation, LBKA)。LBKA 不僅能夠顯著提高算法速度，而且由于低秩分塊約束極大的消除了噪聲的影響，使得算法近似精度也有了提高。

相較于傳統的矩陣分解問題，本文設計了低秩分塊矩陣的核近似算法。本文的特點和貢獻如下：

1)引入了一種低秩分塊矩陣的框架，通過核方法將非線性問題轉化為高維空間中的線性問題來解決，這樣不僅可以提高算法的精度，還可以通過低秩約束來降低算法復雜度，提高了計算的收斂速度與計算精度。

2)設計了一種低秩分塊矩陣的核近似算法。該算法基于增廣拉格朗日乘子法和交替方向乘子法構造迭代公式，依次更新系數矩陣Z和輔助變量J、Q、S，直到收斂到穩定的特征矩陣。

3)在人臉識別數據集和字符識別數據集上進行了實驗驗證。實驗結果表明，相較于傳統的識別算法，LBKA 在收斂速度和近似精度上有所提高。同時通過核矩陣近似處理，極大地降低了噪聲對實驗的影響。

1 相關工作

本文主要在低秩、稀疏、對角矩陣的分解領域探討有關低秩分塊矩陣的近似問題。

隨著非負矩陣分解[4]等矩陣分解算法的提出，給數據處理領域帶來了新的思路。低秩可以看作稀疏的特殊形式，低秩就是特征值稀疏；塊對角也是，塊對角矩陣自身就具有低秩和稀疏的特性。

現階段，稀疏表示被廣泛應用于信號處理[3]、機器學習和計算機視覺[5]等方面。隨著基于稀疏表示的分類(SRC)[6]在人臉識別中的成功應用，已經提出了許多基于SRC 的優化算法。例如，Nie 等人通過對損失函數和正則化項進行l21范數約束，提出了一種有效的特征選擇方法[7]。

然而稀疏約束只能實現局部約束，而低秩約束卻能夠實現全局約束。魯棒主成分分析(robust principal component analysis, RPCA)是最典型的低秩方法，最初是用來將損壞的觀測數據恢復為具有低秩結構的數據。后來發現RPCA 可以將一個子空間的數據分解成低秩和稀疏噪聲兩部分。但RPCA 無法處理多個子空間的并集。為此提出了潛在的低秩表示(LatLRR)[8]，通過利用子空間分割的低秩表示的方法解決多個子空間問題。

本節主要介紹一些基本符號并簡單說明了兩種典型的基于低秩表示的方法：魯棒主成分分析(RPCA)[9]和低秩表示(LRR)[10]。

1.1 基本符號

本文使用粗體大寫字母表示矩陣，例如A。用粗體小寫字母表示矢量，例如a。對于A，其第i行被表示為行向量[A]i，其第j列被表示為列向量[A]:,j。將aij或Aij表示為A的第 (i,j) 項。將Diag(A) 作為對角矩陣，其對角線上的第i項是ai。將單位矩陣表示為I。如果A中的所有項都是非負的，則表示為A≥0。文中將使用一些范數，包括l0范數 | |A||0，l1范數，Frobenius范數范數和核范數

1.2 低秩分塊矩陣相關定義

定義1假設矩陣A=[a1,a2,···,an]∈Rm×n是一個包含n個數據點的列矩陣。其核矩陣定義為：其中 ? :a|→ ?(a) 是內核誘導的特征圖。n個映射數據點的所有成對內積存儲在核矩陣K∈Rn×n中。

由于核矩陣的內存為O(n2)，所以在實際應用中是使用數據數量的二次方來計算和存儲的。例如核主成分分析算法需要計算特征值分解(SVD)，它的復雜度為O(n3)，并且要多次訪問核矩陣K。因此要想計算大規模的數據，必須考慮復雜度的影響。

圖1 是低秩矩陣分塊的一個示例，對于任意一個矩陣A∈Rm×n，有

圖1 低秩矩陣分塊示例Fig.1 An example of low-rank matrix partitioning

為了用低秩分塊矩陣逼近該相似度矩陣并同時得到聚類結構，可以分別近似這些對角塊，每個對角塊表示一個聚類。

通過求矩陣秩的最小化來求解低秩矩陣。然而這很難，可以用核近似方法將核范數最小化為

式中：X∈Rm×n， Γ ＞0 是正則化參數。

定義2(奇異值閾值(SVT)) 要想求解核范數最小化問題(NNM)，例如：

需要使用奇異值閾值處理算子SΓ(·) 給出的閉式解：

式中：SΓ(x)=sgn(x)·max(|x|-Γ,0) 是軟收縮算子；是A的SVD 分解[11]。

1.2.1 魯棒的主成分分析(RPCA)

假設X=[x1,x2,···,xn]∈Rd×n是由n個樣本組成的數據矩陣，RPCA 的目標是從損壞的矩陣X中確定低秩矩陣X0，同時消除稀疏噪聲E，即X=X0+E。因此，RPCA 的目標函數為

式中λ是平衡參數； | |·||0表示l0范數。由于低秩函數的離散性質和最小化l0范數十分困難，目前通常分別使用核范數和l1范數正則化代替低秩約束和l0范數正則化。因此，式(1)可以重新表述為

其 中 ||·||?和 | |·||1表 示 核 范 數 和l1范 數 。 式(2)可以使用增廣拉格朗日乘子法(ALM)[12]來計算。

1.2.2 低秩表示(LRR)

RPCA 是基于先驗假設，即數據大多是從低秩子空間中提取的，可以用單個子空間來描述。然而真實數據集很難用單個子空間來描述。為此，LRR 假設每個數據可以由多個線性低秩子空間的并集近似表示。由此可以得到LRR 的目標函數為

其中D和λ分別是字典和平衡參數。 ||·||1表示不同范數的約束。與RPCA 類似，式(3)可以重新表述為

1.3 塊對角矩陣的核近似

定義3(自表達屬性) 來自多個子空間的并集的每個數據實例可以通過其他數據實例的線性組合來表示，這種性質被稱為自表達屬性[13]。即

在存在自表達屬性的情況下，數據集中的每個數據點可以由來自其子空間的幾個點的線性組合來表示[14]。所以，自表達屬性應該是塊對角的。

本文令類與類之間塊對角線分量盡可能小，同時提高相關的類內表示，將其結構化形式表示為

其中λ1和λ2是用于衡量相應的項的正數， ⊙ 表示Hadamard 乘積，并且X∈Rd×n。具體地說，第1 項是為了最小化類與類之間塊對角線分量，并且第2 項是構造的子空間度量，以提高相關的類內表示。dij是度量xi和xj之間的距離。本文將兩個樣本之間的距離定義為歐幾里德距離的平方，即由于l0范數最小化問題是NP 難問題，所以第2 項可以被放寬表示為因此，式(5)可以重新表述為

通過整合公式(4)和(6),可以得到：

其中λ1、λ2和λ3為式(7)的相應項加權。

下面本文對式(7)進行核化。

設 ? :Rd→H是從輸入空間到Hilbert 空間的映射，K∈Rn×n為半正定核矩陣：

其中ker： Rd×Rd→R 是核函數。式(7)中的E可以表示為E=X-XZ,所以有

然后定義一個變量S=I-Z∈Rn×n，可以得到其中表示S的第i列。將其中的X替換為 ? (X)，可以得到

因為K=?(x)′?(x),所以可以通過將函數g(S)定義為將式(9)重寫為以下問題：

其中核矩陣K包含在g(S)中。

定義4(拉格朗日乘子法、增廣拉格朗日乘子法、交替方向乘子法)

1) 假定要求解f(X) 的最優化問題，滿足h(X)=0 ， 其中f(X):Rn→R，h(X):Rn→Rm。基于拉格朗日乘子法[13]可以得到以下目標函數：

2)在計算等式約束問題時，使用增廣拉格朗日乘子法(ALM)，ALM 增加了二次懲罰項，基于ALM 可以得到以下目標函數：

3)要求解f(X)+g(Z)的最優化問題，滿足約束條件AX+BZ=C。這類問題需要用到交替方向乘子法(ADMM)[13]，ADMM 是ALM 的進一步推廣，它將對偶上升法的可分解性與ALM 的收斂性相結合，基于ADMM 方法可以得到以下目標函數：

2 低秩分塊矩陣的核近似算法

算法1低秩分塊矩陣的核近似算法

輸入特征矩陣X；參數λ1，λ2，λ3；距離測量矩陣D；

輸出系數矩陣Z。

初始化：J=0,Z=0,Q=0,S=0,λ1，λ2，λ3>0,

do

1) 通過式(14)更新系數矩陣Z；

2) 通過式(15)更新輔助變量J；

3) 通過式(17)更新輔助變量Q；

4) 通過式(18)更新輔助變量S；

5) 更新拉格朗日乘子C1，C2和C3；

6) 更新μ

end

為了優化式(10)，首先引入兩個輔助變量J和Q來使問題可分離，將式(10)重寫為

然后，可以通過ALM 得到式(11)的增廣拉格朗日函數

其中 〈J,Q〉=tr(JTQ)。C1、C2和C3是拉格朗日乘子， μ＞0 是懲罰參數。下面介紹詳細迭代步驟：

更新Z固定其他變量并通過下述步驟更新Z

這相當于

更新J當固定其他變量時，式(12)的目標函數可以表示為J的函數，即

通過使用奇異值閾值算子(見定義3)，可以得到一個封閉形式的解決方案，即

式中：UΣVT是的奇異值分解；S1/μt(·) 是軟閾值算子[7]，定義為

更新Q當固定其他變量時，式(12)的目標函數可以表示為Q的函數，即

可以通過逐元素的方法進行更新。顯然，式(16)可以等效為解決n×N個子問題。對于第i行第j列元素Kij，式(16)的最優解是

更新S當固定其他變量時，式(12)的目標函數可以表示為S的函數，即

其中 Γi是矩陣Γ的第i行。

在優化變量J、Z、Q和S之后，ADMM 算法還需要更新拉格朗日乘子C1、C2、C3以及參數 μ，以便更快地收斂。

最后，本文通過譜聚類算法進行聚類，即先通過構造親和矩陣來找到數據的低維嵌入，然后使用k均值聚類來實現最后的聚類。

3 算法的性質分析

3.1 算法的收斂性分析

為了解決目標函數，即式(10)，本文使用了迭代更新ADMM 算法，如第2 章所示。下面證明LBKA 的收斂性。

定理1LBKA 是收斂的。

證明經典的ADMM 算法主要解決下述問題：

R∈Rp×n,T∈Rp×m,μ ∈Rp

其中 ，f和h是凸函數。

可以看出，式(11) 是式(19) 的一種特殊情況。經變換，式(12)可以被轉換為式(19)。然后，就可以使用ADMM 算法以交替方式更新兩個原始變量，并迭代地解決式(19)：

它與第2 章中的算法1 有相同的更新步驟。因此，式(11)是經典ADMM 問題的一個特殊情況。算法1 中所提出的優化算法相當于兩塊ADMM，它的收斂性在理論上得以證明。

3.2 算法的復雜度分析

定理2根據第2 章可以看出LBKA 的總時間復雜度為Ok(2n2N+n2d+nN)，其中n為訓練樣本數，N為樣本總數，d為樣本維數，k為迭代次數。

證明算法1 的主要過程在第二節算法迭代的前3 步給出，因為需要進行奇異值分解(SVD)和矩陣運算。因此，當訓練樣本數n和樣本總數N非常大時，LBKA 的時間復雜度會很高。特別是計算矩陣J∈Rn×N的SVD 分解需要O(n2N)(N＞n)的復雜度。在這里需要注意的是，由于要計算矩陣的逆，迭代更新Z時需要O(n2N+n2d) 時間，其中d是樣本維數。步驟3 的時間復雜度是O(nN)。因此，LBKA 的總時間復雜度為Ok(2n2N+n2d+nN)，其中k是迭代次數。

相比之下，基于稀疏表示的分類方法(如SRC 和LatLRR)的時間復雜度是O(n2(N-n)d)，這要比LBKA 慢很多。LRLR[15]和LRRR[16]等回歸方法的計算復雜度為O(nd+n2d)，比LBKA 快一點，但計算精度比LBKA 低。基于低秩和稀疏表示的方法(如RPCA) 需要同時計算特征矩陣的SVD 并求解軟閾值問題。LBKA 的總體時間復雜度與低秩稀疏表示方法的總時間大致相同。

4 實驗結果與分析

4.1 實驗環境

本文在兩個數據集上分別測試了人臉識別和字符識別兩個識別任務，然后與一些最先進的識別方法進行比較，包括基于稀疏表示的方法，如LRC[17]，基于低秩標準的方法，如RPCA，和傳統的分類方法，如支持向量機(SVM)[18]，以及塊對角低秩表示方法(block-diagonal low-rank representation, BDLRR)[5]。

為了保證LBKA 和對比算法在實驗中的參數相同，本文使用交叉驗證方法重新實現了所有算法。因此，本文使用的所有算法都是在相同條件下進行測試的，所以實驗結果是真實可靠的。

4.2 評估標準

本文使用2 個常用的度量指標對實驗結果進行評估，分別是準確度(Accuracy) 和蘭德指數(Rand index)：

1)Accuracy(Acc):

其中 π 是n個組的排列，Xt和X分別是分類準確的樣本和所有測試樣本，如果點j屬于簇i則它們的第i個條目等于1，否則為0。

2)Rand index(RI):

其中，TN 表示不同類樣本的被分到不同個集合，FN 表示同一類樣本的被分到不同個集合。

4.3 人臉識別

在本節中，本文使用擴展YaleB[5]面部圖像數據集進行實驗。

擴展的YaleB 數據庫：由38 個人的2 414 個人臉圖像組成，每個人有59～64 個亮度不同的圖像。在實驗過程中，隨機選擇其中的20、25、30、35個圖像作為訓練集，其余的作為測試集進行實驗。

圖2 為LBKA 獲得的擴展YaleB 數據庫的數據表示，從中可以看出獲得的矩陣為對角分塊結構。表1 和表2 分別是擴展的YaleB 數據庫中不同算法的識別精度和蘭德指數。從中可以看出，在使用不同數量的訓練集進行實驗時，LBKA 都能得到最好的識別結果。而且隨著樣本數量的增加，LBKA 的識別精度也隨之逐漸提高。

圖2 LBKA 獲得的擴展YaleB 數據庫的數據表示Fig.2 Data representation of the Extended YaleB databaseobtained by LBKA

表1 擴展YaleB 數據庫中不同數量訓練集中不同方法的準確度(Acc±std)Table 1 Recognition accuracies of different methods of different numbers of training samples on the Extended YaleB database (Acc±std) %

4.4 字符識別

本文選取Char74K 場景人物圖像數據集[5]來進行實驗。在以往的模式識別任務中，由于場景圖像十分復雜，很難將想要識別的文本分離出來，而LBKA 中對類內類外的處理有助于對場景中字符進行提取。本文將LBKA 與其他先進的字符識別算法進行對比，包括CoHOG[19]、RTPD[20]，PHOG[21]、MLFP[22]和BDLRR[5]。

Char74K 數據庫：該數據庫總共包含7 萬4 千幅圖像，所以叫Chars74K。本文主要關注其中英語字符和數字的識別。本文在實驗中只使用了原數據庫的一個小子集Char74K-15，其中包含15 個訓練樣本和15 個測試樣本。

表2 擴展YaleB 數據庫中不同數量訓練集中不同方法的蘭德指數(RI)Table 2 Rand index of different methods of different numbers of training samples on the Extended YaleB database(RI) %

表3 和表4 列出了LBKA 和其他字符識別方法的識別準確度和蘭德指數，從中可以看出，LBKA 識別的準確度和蘭德指數都是最高的。

表3 場景角色數據庫上不同方法的準確度Table 3 Recognition accuracies of different methods onthe scene character database. %

表4 場景角色數據庫上不同方法的蘭德指數Table 4 Rand index of different methods on the scenecharacter database. %

4.5 實驗分析

首先，與兩種數據集上的對比算法相比，LBKA 進行模式識別時更加準確。

其次，LBKA 比現有的識別算法更準確，這說明擴大了對角塊和非對角塊之間的差異的同時增強了相關數據表示，能夠獲得更好的識別效果。

第三，LBKA 在識別數量有限的樣本時比其它對比算法都好。主要原因是LBKA 具有稀疏，低秩和分塊三大特性。低秩可以有效地挖掘數據相關的基礎結構，并且揭示數據矩陣的全局潛在結構；稀疏能夠尋找最近的數據子空間；塊對角表示能夠發掘數據內在結構并闡明數據點的最近子空間。

隨著迭代次數的增加LBKA 的相對誤差在減小，并且總值在圖3 所示的60 次迭代后基本沒有變化，這驗證了LBKA 具有收斂性。圖4 表示LBKA 關于參數和的性能變化。可以看出，LBKA 對和的變化值不敏感。更具體的說，當參數處于一個合理范圍內時，LBKA 準確度較高，這說明增加類內類外約束是十分有必要的。

圖3 LBKA 在不同數據庫上的收斂曲線Fig.3 Convergence curves of LBKA on different databases

5 結束語

本文給出了低秩分塊矩陣的相關定義，說明了矩陣分解的應用。分析了核近似的優點，并提出了低秩分塊矩陣核近似的方法。最后將該方法在人臉識別和字符識別中進行比較。結果表明，所提出的低秩分塊矩陣分解算法在收斂速度和近似精度上都具有一定的優勢。未來工作包括：

1)從矩陣的核近似出發，對原有的子空間聚類算法進行改進，提高分塊的速度和準確性，從而提升算法找到全局最優解的能力。

2)通過與多種矩陣分解算法的比較，觀察提出的低秩分塊矩陣的核近似算法的表現，進一步分析算法的可行性。

圖4 λ1、 λ1 對兩種數據集的影響Fig.4 The impact of λ1 and λ2 on the two data sets

3)本文通過實驗證明了LBKA 在人臉識別和字符識別等領域的效果比傳統識別算法更好，接下來可以研究其在回歸、聚類、排序等方面的應用。