壓縮子空間聚類理論及其套用研究

《壓縮子空間聚類理論及其套用研究》是依託清華大學，由谷源濤擔任項目負責人的面上項目。

基本介紹

• 中文名：壓縮子空間聚類理論及其套用研究
• 依託單位：清華大學
• 項目負責人：谷源濤
• 項目類別：面上項目

項目摘要

隨著高清廣播、視頻監控、物聯網和社交網路等套用的普及，採集、存儲、傳輸和處理的數據量呈現爆炸式增長。雖然這些數據的維度很高，但內在的自由度遠小於其維度。在計算機視覺、圖像處理和大系統理論中，數據往往來自於若干個低維子空間，但具體位於哪個子空間是未知的。傳統子空間聚類模型直接在環境空間將原始數據劃分成多個低維子空間，這種方式在處理高維數據時需要極大的計算和存儲資源。本項目提出並研究壓縮子空間聚類理論，借鑑壓縮感知理論的思想，將原始樣本映射到壓縮空間中再做進一步處理，從而達到減小計算和存儲複雜度的目的。本項目將全面研究子空間的相對位置關係及樣本分布對子空間可分離性的影響，設計壓縮觀測方式並度量其保可分離性，研究壓縮空間的觀測樣本聚類方法和原子空間及樣本的恢復技術，具有重要的科學意義和理論價值。本項目將把理論結果套用於視頻編碼或社交網路等網際網路技術，藉助套用場景對系統進行全面驗證和展示。

結題摘要

隨著移動網際網路和海量存儲技術的發展，大尺度信號處理理論的重要意義日益凸顯。子空間聚類模型將樣本所在子空間作為分類依據，完美地利用了數據內在的線性結構特徵，在機器學習和計算機視覺等領域具有重要套用。經典的子空間聚類算法在高維空間上求解若干最最佳化問題，計算複雜度巨大。本項目提出了壓縮子空間聚類——即用高斯隨機矩陣對原始樣本進行降維壓縮，然後再對壓縮結果進行聚類，具有計算複雜度低、保護隱私和無需原始數據等優點。但同時帶來隱患——隨機壓縮可能降低兩個子空間的可分離性，增加聚類失敗機率。此問題難點是高斯矩陣投影既不保持向量的模長，也無法保持正交基底。藉助隨機矩陣理論和幾何技巧，本項目從理論層面徹底解決了這個問題。我們嚴格證明：只要投影后的背景空間維度不低於常數倍的子空間維度和子空間數量的對數中的較大值，那么投影后任意兩個子空間之間的投影弗洛貝紐斯範數距離被限制在投影前距離的小領域的機率會隨著新維度的增加以迅速趨向1。上述成果首次揭示了高維背景空間中的低維子空間經過高斯隨機投影后以極大機率滿足限制等距性質。它揭示了在對低維子空間進行處理時可以將其從任意高維的背景空間進行降維到一個中低維度的背景空間，而且保持原始數據的內部結構不發生本質變化。我們的發現意味著對於包括子空間聚類在內的眾多子空間相關的問題，都可以先隨機投影降維預處理，再用傳統算法以較小的計算成本和記憶體開銷進行處理，而且最終結果以大機率聚集於直接處理原始數據的結果。本項目的核心成果和降維領域理論界的JL引理（Johnson-Lindenstrauss Lemma）以及壓縮感知領域的理論基礎高斯隨機矩陣對稀疏信號的RIP具有相同的科學意義，只不過後兩者的研究對象都是歐氏空間的數據點，而本項目的研究對象是低維子空間；此外，它們研究的保距是數據點之間的歐氏距離，而本成果的距離是子空間之間的投影範數距離。這是世界上首次發現高斯隨機矩陣具有針對低維子空間的限制保距性質。