基于快速凸無窮范數(shù)極小化的大量子空間的子空間分割

唐科威，穆夢嬌，李縉紅，張 杰，姜 偉，彭興璇

基于快速凸無窮范數(shù)極小化的大量子空間的子空間分割

唐科威，穆夢嬌，李縉紅，張 杰，姜 偉，彭興璇

(遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧 大連 116029)

子空間分割是計算機(jī)視覺和機(jī)器學(xué)習(xí)中的一個基本問題。由于實(shí)際問題中的數(shù)據(jù)往往類數(shù)較多，使得大量子空間的子空間分割問題顯得尤為重要。近年來基于譜聚類的方法在子空間分割領(lǐng)域得到了越來越多的關(guān)注，但是在相關(guān)工作的實(shí)驗(yàn)中，子空間的個數(shù)卻往往不超過10個。無窮范數(shù)極小化是近年來提出的一個專門針對大量子空間的子空間分割問題的方法，其通過降低表示系數(shù)矩陣的差異性能有效地處理該問題，但是仍有一定的局限，例如計算速度仍不夠快，缺乏針對獨(dú)立子空間問題的理論保證。為此，提出快速凸無窮范數(shù)極小化，該個方法不僅能夠降低表示系數(shù)矩陣的差異性，而且能夠?qū)Κ?dú)立子空間情況提供理論保障且計算速度更快，大量的實(shí)驗(yàn)證明了該方法的有效性。

子空間分割；基于譜聚類的方法；大量子空間；無窮范數(shù)；快速算法

在大數(shù)據(jù)時代，數(shù)據(jù)的低維結(jié)構(gòu)分析在許多實(shí)際應(yīng)用中發(fā)揮著關(guān)鍵作用[1-6]。眾所周知，在不同的光照條件下拍攝一個受試者的正面臉部圖像，可以用一個低維子空間很好地刻畫。事實(shí)上，該結(jié)構(gòu)在許多其他應(yīng)用中也存在，例如視頻中剛體運(yùn)動的軌跡特征點(diǎn)、不同形態(tài)的手寫數(shù)字。不幸的是，一個單一的低維子空間通常不足以準(zhǔn)確地刻畫數(shù)據(jù)的幾何結(jié)構(gòu)，而多個子空間可以更好地刻畫，因此需要面對子空間分割問題。給定一組采樣于多個子空間并集的數(shù)據(jù)點(diǎn)，子空間分割的目的是將數(shù)據(jù)點(diǎn)劃分為組，每個組對應(yīng)一個子空間。子空間分割廣泛應(yīng)用于計算機(jī)視覺和機(jī)器學(xué)習(xí)領(lǐng)域，如圖像分割[7-9]、運(yùn)動分割[10]和人臉聚類[11]?，F(xiàn)有的子空間分割方法大致可分為[12]迭代方法、統(tǒng)計方法、代數(shù)方法、基于譜聚類方法?；谧V聚類的方法是近年來的研究熱點(diǎn)，該類方法首先尋找一個包含所有數(shù)據(jù)點(diǎn)之間相似度的親和矩陣，然后對其應(yīng)用歸一化切割(normalized cut，NC)[13]來獲得分割結(jié)果，而基于譜聚類方法的主要差別在于構(gòu)造親和矩陣的方式不同。

根據(jù)NC的原理，如果將親和圖構(gòu)造為同一子空間獲取數(shù)據(jù)點(diǎn)之間的權(quán)值大于不同子空間獲得的數(shù)據(jù)點(diǎn)之間權(quán)值的形式，則分割效果較好。為了便于討論，本文假設(shè)數(shù)據(jù)點(diǎn)的順序與真實(shí)結(jié)果一致，此假設(shè)是不失一般性的，因?yàn)榇蠖鄶?shù)基于譜聚類的方法都是全局最優(yōu)的。在這種假設(shè)下，親和矩陣的塊對角結(jié)構(gòu)引起廣泛討論。當(dāng)子空間是獨(dú)立的時候，很多方法都能得到塊對角結(jié)構(gòu)，例如低秩表示(low-rank representation，LRR)[14-15]，最小二乘回歸(least square regression，LSR)[16]和稀疏子空間聚類(sparse subspace clustering，SSC)[17-18]。為此，文獻(xiàn)[16]和文獻(xiàn)[19]還專門研究了目標(biāo)函數(shù)滿足一定的條件，就可以得到一個基于獨(dú)立子空間假設(shè)的塊對角結(jié)構(gòu)，并且稱這個條件為強(qiáng)制塊對角結(jié)構(gòu)(enforced block diagonal，EBD)條件。在子空間獨(dú)立的情況下，滿足EBD條件的前2條即可保證得到塊對角結(jié)構(gòu)。

實(shí)際應(yīng)用中的數(shù)據(jù)集通常存在噪聲和異常值，即使許多方法被設(shè)計成追求塊對角的親和矩陣，也不可避免非對角區(qū)域的元素是非零的。當(dāng)子空間數(shù)量較多時，非對角噪聲會嚴(yán)重影響分割性能。而在實(shí)際問題中，數(shù)據(jù)集往往包含很多類，因此面對大量子空間的子空間分割問題時，僅僅追求親和矩陣的塊對角結(jié)構(gòu)是遠(yuǎn)遠(yuǎn)不夠的。文獻(xiàn)[20]表明，親和矩陣中同類點(diǎn)對應(yīng)的元素相互接近能在一定程度上克服上述非對角噪聲帶來的影響，本文稱此性質(zhì)為親和矩陣的低差異性。其實(shí)，以往工作中探討的很多性質(zhì)都與親和矩陣的低差異性有一定關(guān)系，例如聚組效應(yīng)(grouping effect，GE)。

文獻(xiàn)[21]表明，最小二乘回歸(least square regression，LSR)[16]、光滑表示聚類(smooth representation clustering，SMR)[21]等方法具有GE。對于一組給定的高維數(shù)據(jù)點(diǎn)以及一個自表示矩陣，如果不同數(shù)據(jù)點(diǎn)間差異比較小，那么自表示矩陣中對應(yīng)的列也趨于零，則該自表示矩陣具有GE[21]。因此，如果同一個子空間中的數(shù)據(jù)點(diǎn)相鄰，則具有GE的塊對角圖在對角塊上的差異較小。然而，這樣的結(jié)果依賴于數(shù)據(jù)點(diǎn)的分布。對于任何數(shù)據(jù)集，都可以很容易地在相同的子空間中找到一些彼此之間距離很遠(yuǎn)的數(shù)據(jù)點(diǎn)，所以不能利用GE這個性質(zhì)來準(zhǔn)確地度量親和矩陣的差異性。稠密塊稀疏表示(dense block and sparse representation，DBSR)[22]的提出也考慮了親和矩陣的低差異性。DBSR最小化自表示矩陣的1,1-范數(shù)和2-范數(shù)的組合，獲得了稀疏性和稠密塊性質(zhì)的組合。由于最大奇異值可以是對角塊差的一個界，因此可以誘導(dǎo)等密度塊來實(shí)現(xiàn)親和矩陣的低差異性。但是，該方法的計算速度對于大量子空間的子空間分割問題來說還不夠快。無窮范數(shù)極小化(infinity norm minimization，INM)[20]是一個考慮了親和矩陣低差異性的快速方法。該方法通過引入無窮范數(shù)控制對角塊的差，對角塊的差是指對角塊的最大值減去最小值。因?yàn)榫仃嚨臒o窮范數(shù)不超過最大奇異值，所以相對于以往方法，該方法往往能夠使親和矩陣的差異性更低，從而對于大量子空間的子空間分割問題能獲得更好的分割效果。但是INM不能滿足EBD條件，因此無法在理論上保證親和矩陣的塊對角結(jié)構(gòu)，同時在速度上也有上升的空間。

本文在INM的基礎(chǔ)上提出了快速凸無窮范數(shù)極小化(fast convex infinity norm minimization，F(xiàn)C-INM)的方法來處理大量子空間的子空間分割問題，通過最小化無窮范數(shù)和1,1-范數(shù)的組合可以保證親和矩陣的低差異性。在子空間獨(dú)立的情況下，F(xiàn)C-INM能夠滿足EBD條件，從而在理論上保證了親和矩陣的塊對角結(jié)構(gòu)。此外，受到文獻(xiàn)[20]和文獻(xiàn)[23]的啟發(fā)，在求解FC-INM模型的過程中運(yùn)用了一些加速技巧。實(shí)驗(yàn)結(jié)果表明，本文方法不僅計算速度高于INM，而且取得了較好的效果：

(1) 可以降低親和矩陣的差異性，在大量子空間的子空間分割問題中取得了很好的效果；

(2) 在子空間獨(dú)立的情況下，理論上可以保證獲得的親和矩陣具有塊對角結(jié)構(gòu)；

(3) 通過借鑒線性時間投影算法和Woodbury矩陣反演公式，本文方法的計算速度明顯高于INM方法。實(shí)際上，本文方法的ADM算法比大多數(shù)基于譜聚類方法的ADM算法都快。

1 相關(guān)工作

1.1 符號說明

1.2 無窮范數(shù)極小化的回顧

為了便于理解，本文首先回顧INM子空間分割方法。記=[1,···,]為數(shù)據(jù)集，其中x(=1,···,)代表一個數(shù)據(jù)點(diǎn)，INM的模型為

根據(jù)先前工作的結(jié)果，INM的交替方向迭代(alternating direction method，ADM)[24]算法相對穩(wěn)定。

算法1. INM的ADM算法。

輸入：矩陣，參數(shù)。

輸出：。

初始化：====0,=10-6,=1.1,=10-4。

2 本文模型

INM雖然在子空間分割中取得了很好的效果，但是，在子空間獨(dú)立的情況下，無法在理論上保證親和矩陣的塊對角結(jié)構(gòu)，即不滿足EBD條件的前2條。

已知函數(shù)(,)是定義在(,)上的，其中是由一些方陣組成的集合，是由非零列的方陣組成的集合。

假設(shè)所有矩陣都是兼容維數(shù)的，那么EBD的條件[16]為：

(2)(,)≥(,)，當(dāng)且僅當(dāng)=或者3=4=0時，等號成立。

(3)(,)=(1,1)+(2,2)。

EBD條件(1)是子空間分割的基本要求，保證了分割結(jié)果對輸入數(shù)據(jù)矩陣的列的任何排列都是恒定不變的。條件(2)是最小化函數(shù)后，在一定子空間假設(shè)下成為對角塊的關(guān)鍵。條件(3)實(shí)際上沒有要求函數(shù)的解是塊對角的，但是通過此條件可以了解每個塊的結(jié)構(gòu)與所使用的函數(shù)之間的聯(lián)系。

其中參數(shù)>0，用于控制親和矩陣低差異性和稀疏性的平衡。

由此可見，本文模型滿足EBD條件的前2點(diǎn)。

由命題2可知，當(dāng)子空間獨(dú)立時，本文方法計算的具備塊對角結(jié)構(gòu)。

考慮到實(shí)際應(yīng)用中數(shù)據(jù)通常含有噪聲，本文將式(2)中的模型改寫為

此外，通過對無窮范數(shù)相關(guān)問題采用了全新的求解方案，本文模型的數(shù)值算法還在計算速度上有所提高。在大量子空間的子空間分割問題中，數(shù)據(jù)量往往很大，所以此改進(jìn)是尤為重要的?；谝陨蟽?nèi)容，本文方法稱之為快速凸無窮范數(shù)極小化(fast convex infinity norm minimization，F(xiàn)C-INM)。

3 數(shù)值算法

為了便于無窮范數(shù)和1,1范數(shù)的求解，需要引入輔助變量和，則有

上述模型的增廣拉格朗日函數(shù)為

算法2. FC-INM的ADM算法。

輸入：矩陣，參數(shù)和。

輸出：。

初始化：=====0,=10-4,=1.5,=10-4。

算法2中的步驟2和步驟3，可以分別由文獻(xiàn)[25]中的奇異值閾值算子和文獻(xiàn)[14]中的引理3.2求解。根據(jù)經(jīng)驗(yàn)，該算法的收斂性和穩(wěn)定性都很好，但是算法2的主要計算量是步驟1和步驟4。

算法3.線性時間投影算法。

輸入：，標(biāo)量。

輸出：。

步驟1.當(dāng)非空時，隨機(jī)從集合中選取一個索引。

步驟4.設(shè)置，如果(+)-(+)(),=+,=+那么，為；否則，為{}。

若集合不為空，重復(fù)步驟1~4，直到為空集時，過程結(jié)束。

根據(jù)文獻(xiàn)[23]，該算法的算法復(fù)雜度為(2)，低于INM算法中相關(guān)問題的算法復(fù)雜度。

因此，算法2中的步驟4可以轉(zhuǎn)化為

由于在迭代過程中不更新，和可以在循環(huán)外提前計算。

4 實(shí) 驗(yàn)

本文測試了FC-INM對于大量子空間的子空間分割問題的有效性。在2個基準(zhǔn)數(shù)據(jù)庫上與相關(guān)工作INM[20]，LRR[14-15]，SSC[17-18]，LSR[16]，SMR[21]，DBSR[22]以及結(jié)構(gòu)限制的低秩表示(structure constrained low-rank representation，SCLRR)[26]進(jìn)行了比較，通過準(zhǔn)確率(accuracy，ACC)、標(biāo)準(zhǔn)化互信息(normalized mutual information，NMI)和調(diào)整蘭德指數(shù)(adjusted rand index，ARI)3個評價指標(biāo)的百分比來評估性能，其中準(zhǔn)確率為主要的評價指標(biāo)。同時本文也對計算速度進(jìn)行了比較。對于每種方法，都使用了原始作者提供的源代碼，并對其重要參數(shù)進(jìn)行了經(jīng)驗(yàn)調(diào)優(yōu)，從而獲得最佳結(jié)果。

4.1 人臉聚類實(shí)驗(yàn)

表1 每種方法在CMU PIE上的ACC (%)

表2 每種方法在CMU PIE上的NMI (%)

表3 每種方法在CMU PIE上的ARI (%)

圖1 FC-INM隨參數(shù)變化的準(zhǔn)確率

4.2 紋理聚類實(shí)驗(yàn)

表4 每種方法在USC SIPI上的結(jié)果(%)

4.3 計算速度

大量子空間的子空間分割問題往往包含大量數(shù)據(jù)，所以計算速度在該問題中十分重要，在使用ADM迭代的方法中，INM已經(jīng)是一個速度較快的方法。本文重點(diǎn)比較FC-INM與INM在上述實(shí)驗(yàn)數(shù)據(jù)上的計算速度。實(shí)驗(yàn)在一臺I7-9700K處理器和16 G內(nèi)存的計算機(jī)上進(jìn)行，所有的時間都是以s為單位的。實(shí)驗(yàn)結(jié)果見表5，F(xiàn)C-INM較INM進(jìn)一步提升了的計算速度，能夠快速處理大量子空間的子空間分割問題，在實(shí)際問題中具有重要意義。

表5 兩種方法的計算速度

5 結(jié)束語

本文提出了快速凸無窮范數(shù)極小化的子空間分割方法，該方法的一個重要優(yōu)點(diǎn)是能夠處理大量子空間的子空間分割問題，在實(shí)際問題中具有重要意義。各種基準(zhǔn)數(shù)據(jù)庫上的大量實(shí)驗(yàn)結(jié)果表明，本文方法可以保證親和矩陣的低差異性，并且能夠很好的進(jìn)行大量子空間的子空間分割。然而，本文運(yùn)用無窮范數(shù)控制對角塊的差，只考慮了表示矩陣的全局性質(zhì)，該策略也會在一定程度上縮小對角塊處的元素與非對角塊處元素的差異性。未來的工作，可以考慮表示矩陣的局部性質(zhì)來克服上述局限性。

[1] ZHANG W, ZHANG Y M, MA L, et al. Multimodal learning for facial expression recognition[J]. Pattern Recognition, 2015, 48(10): 3191-3202.

[2] ZHANG W, QU C F, MA L, et al. Learning structure of stereoscopic image for no-reference quality assessment with convolutional neural network[J]. Pattern Recognition, 2016, 59: 176-187.

[3] ZHANG W, HU S N, LIU K. Patch-Based correlation for deghosting in exposure fusion[J]. Information Sciences, 2017, 415: 19-27.

[4] 唐科威, 由月, 蘇志勛, 等. 核結(jié)構(gòu)限制的低秩表示及其在流行聚類上的應(yīng)用[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2019, 31(4): 589-595. TANG K W, YOU Y, SU Z X, et al. Kernel structure constrained low rank representation for manifold clustering[J]. Journal of Computer-Aided Design & Computer Graphics, 2019, 31(4): 589-595 (in Chinese).

[5] 章榮, 陳誼, 張夢錄, 等. 高維數(shù)據(jù)聚類可視分析方法綜述[J]. 圖學(xué)學(xué)報, 2020, 41(1): 44-56. ZHANG R, CHEN Y, ZHANG M L, et al. Overviewing of visual analysis approaches for clustering high- dimensional data[J]. Journal of Graphics, 2020, 41(1): 44-56 (in Chinese).

[6] 潘恒, 何進(jìn)榮, 凌宇, 等. 基于多視圖邊界判別投影的高光譜圖像分類[J]. 圖學(xué)學(xué)報, 2018, 39(6): 1063-1068. PAN H, HE J R, LING Y, et al. Hyperspectral images classification based on multiview marginal discriminant projection[J]. Journal of Graphics, 2018, 39(6): 1063-106 (in Chinese).

[7] CHENG B, LIU G C, WANG J D, et al. Multi-task low-rank affinity pursuit for image segmentation[C]// 2011 IEEE International Conference on Computer Vision. Los Alamitos: IEEE Computer Society Press, 2011: 2439-2446.

[8] LANG C Y, LIU G C, YU J, et al. Saliency detection by multitask sparsity pursuit[J]. IEEE Transactions on Image Processing, 2012, 21(3): 1327-1338.

[9] YANG A Y, WRIGHT J, MA Y, et al. Unsupervised segmentation of natural images via lossy data compression[J]. Computer Vision and Image Understanding, 2008, 110(2): 212-225.

[10] RAO S, TRON R, VIDAL R, et al. Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1832-1845.

[11] HO J, YANG M H, LIM J, et al. Clustering appearances of objects under varying illumination conditions[C]//2013 IEEE Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2003: 11-18.

[12] VIDAL R. Subspace clustering[J]. IEEE Signal Processing Magazine, 2011, 28(2): 52-68.

[13] SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 22(8): 888-905.

[14] LIU G C, LIN Z C, YU Y. Robust subspace segmentation by low-rank representation[C]// Proceedings of the 27th International Conference on Machine Learning. Madison: Omnipress, 2010: 663-670.

[15] LIU G C, LIN Z C, YAN S C, et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 171-184.

[16] LU C Y, MIN H, ZHAO Z Q, et al. Robust and efficient subspace segmentation via least squares regression[C]// Proceedings of the European Conference on Computer Vision. Heidelberg: Springer, 2012: 347-360.

[17] ELHAMIFAR E, VIDAL R. Sparse subspace clustering[C]//Proceedings of the 12thComputer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2009: 2790-2797.

[18] ELHAMIFAR E, VIDAL R. Sparse subspace clustering; algorithm, theory, and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2765-2781.

[19] LU C Y, FENG J S, LIN Z C, et al. Subspace Clustering by Block Diagonal Representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 41(2): 487-501.

[20] TANG K W, SU Z X, LIU Y, et al. Subspace segmentation with a large number of subspaces using infinity norm minimization[J]. Pattern Recognition, 2019, 89: 45-54.

[21] HU H, LIN Z C, FENG J J, et al. Smooth Representation Clustering[C]//Proceedings of the 2014 IEEE Computer Vision and Pattern Recognition. Washington, DC: IEEE Computer Society Press, 2014: 3834-3841.

[22] TANG K W, DUNSON D B, SU Z X, et al. Subspace segmentation by dense block and sparse representation[J]. Neural Networks, 2016, 75: 66-76.

[23] DUCHI J C, SHWARTZ S S, SINGER Y, et al. Efficient Projections onto the ?1-Ball for Learning in High Dimensions[C]//Proceedings of the 25th International Conference on Machine Learning. Madison: Omnipress, 2008: 272-279.

[24] LIN Z C, CHEN M M, MA Y. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices[EB/OL]. [2018-06-24]. https://arxiv. org/abs/1009.5055.

[25] CAI J F, CANDèS E J, SHEN Z W. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982.

[26] TANG K W, LIU R S, SU Z X, et al. Structure-constrained low-rank representation[J]. IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(12): 2167-2179.

[27] SIM T, BAKER S, BSAT M. The CMU pose, illumination, and expression database[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(12): 1615-1618.

Large subspace number subspace segmentation via fast convex infinity norm minimization

TANG Ke-wei, MU Meng-jiao, LI Jin-hong, ZHANG Jie, JIANG Wei, PENG Xing-xuan

(School of Mathematics, Liaoning Normal University, Dalian Liaoning 116029, China)

Subspace segmentation is one of the fundamentals in computer vision and machine learning. Given the large number of categories in practical problems concerning the data set, it is of great significance to address the issue of large subspace number subspace segmentation. Although spectral clustering-based methods received more attention in the field of subspace segmentation, the subspace number in the past experiments was usually less than 10. The infinity norm minimization was a recently proposed method specially for large subspace number subspace segmentation. It could effectively address this problem by reducing the difference of the representation matrix, but there remained some limitations. For example, the computation speed was not fast enough, and there was no theoretical guarantee for the independent subspaces. Therefore, a method named fast convex infinity norm minimization was proposed. This method can not only reduce the difference of the representation matrix, but also provide the theoretical guarantee for the independent subspace and enhance the computation speed, which has been testified by a large number of experiments.

subspace segmentation; spectral clustering-based methods; large subspace number; infinity norm; fast algorithm

TP 391

10.11996/JG.j.2095-302X.2020060954

A

2095-302X(2020)06-0954-08

2020-04-07；

2020-07-16

7April，2020；

16July，2020

國家自然科學(xué)基金項(xiàng)目(61702243，62076115，61702245，61771229)；遼寧省“興遼英才計劃”項(xiàng)目(XLYC1907169)；遼寧省教育廳項(xiàng)目(L201783642)；大連市青年科技之星項(xiàng)目(2019RQ033)

National Natural Science Foundation of China (61702243, 62076115, 61702245, 61771229); LiaoNing Revitalization Talents Program (XLYC1907169); Liaoning Educational Committee (L201783642); Program of Star of Dalian Youth Science and Technology (2019RQ033)

唐科威(1985-)，男，遼寧沈陽人，副教授，博士，碩士生導(dǎo)師。主要研究方向?yàn)橛嬎銠C(jī)視覺、機(jī)器學(xué)習(xí)等。E-mail：kwtang@lnnu.edu.cn

TANG Ke-wei (1985-), male, associate professor, Ph.D. His main research interests cover computer vision and machine learning. E-mail：kwtang@lnnu.edu.cn