基於互相干性考量於雜訊干擾下以匹配追求群分稀疏子空間 之效能保證

Abstract

本碩士論文是壓縮式感測(Compressive Sensing, CS)的概念與演算法應用於群分稀疏子空間(Sparse Subspace)上的一個研究，讓每筆資料與其他少量資料建立關聯性，並藉此關聯性達成分群之目的，且已有相當多研究發現此關聯性具有某種程度上的稀疏性時，可以有一定程度的分群效果。 在本碩士論文中，我們討論歸一化的資料落在某些子空間之聯集上並且加上有界之雜訊，希望在子空間的資訊全然未知的情形下，可以同時把資料妥善分群並且讓每群資料大致上落在其中一個子空間附近，我們考慮以匹配追求(Matching Pursuit, MP)與正交匹配追求(Orthogonal Matching Pursuit, OMP)取代運算複雜度較高的 最小化重建方法來建構資料間的關聯性，透過這些數值化的關聯性，可以由譜分群(Spectral Clustering)來分離出每群比較可能落在相同子空間的資料。 基於一些幾何的基礎，我們進行演算法的分析且得到基於互相干性考量下的效能保證，而從模擬中亦可觀察到這兩種演算法皆有一定程度的穩健度，並且應用於臉部辨識時也會有不錯的表現。

High-dimensional signal processing is ubiquitous in many areas of applications. Often, high-dimensional data lie close to some low-dimensional structures corresponding to several classes or categories. In this paper, we consider noisy data points lie close to union of some unknown low-dimensional subspaces. Following the MP and OMP based sparse subspaces clustering proposed by Tschannen and Bölcskei, we construct sparse representation for each data under bounded noise assumption. Then spectral clustering can be used to separate the data that each group is likely to fall on the same subspace. Based on some geometric structures, we analyze the algorithms and obtain coherence-based performance guarantees. Simulations show that these two algorithms not only have certain degree of robustness but also have nice performance in face recognition.