Subspace Clustering (SC), a generalized task of Principle Component Analysis (PCA), has been used extensively for dimensionality reduction of high-dimensional data. Recently, several methods have been proposed to enhance the robustness of PCA and SC, but most of them are computationally expensive, especially for high-dimensional large-scale data. In this paper, we develop a much faster algorithm for optimizing the NP-hard SC objective using a sum of the $\alpha$ -th power of $\ell_2$ -norm with $0<\alpha \leq 2$, where $\alpha$ =2 is the standard choice and $\alpha$ <2 enhances the robustness of SC. The known implementations achieving a local optimum of the objective would be costly due to the alternation of two separate tasks: optimal cluster-membership assignment and optimal subspace selection, while the substitution of one process to a faster surrogate can cause failure in convergence. Furthermore, such an alternating method has been often criticized due to the sensitivity of initialization. To address the issues, our proposed algorithm has the following key features: (a) release nested robust PCA loops for subspace update, (b) use a simplified singular value decomposition that only requires a few matrix-vector multiplications instead of solving an expensive eigenvector problem and (c) initialize carefully to avoid poor clustering. We prove that it monotonically converges to a local minimum of the SC objective for any $0<\alpha \leq 2$ and finds the true clustering under a statistical assumption on data. In our experiments, it is shown to converge at an order of magnitude faster than the standard implementation optimizing the same objective, and outperforms known SC methods in the literature for MNIST handwritten digit dataset.
부분 공간 클러스터링은 고차원 데이터의 차원 축소를 위해 널리 사용되는 주성분 분석(PCA)을 일반화시킨 기법으로, 다양한 분야에서 고차원 데이터의 차원축소를 위한 방법으로 널리 사용되고 있다. 최근 부분 공간 클러스터링이 가진 잡음에 민감하다는 문제점을 해결하기 위해 다양한 연구들이 제안되었지만, 대부분의 연구들은 특히 대용량 고차원 데이터에 대해 연산 속도가 느리다는 단점을 안고 있다. 본 학위 논문에서는 기존 잡음에 강인한 부분 공간 클러스터링 접근방법들이 가진 연산량보다 훨씬 적은 연산량으로 기존 방법들에 비해 빠르게 문제를 해결할 수 있는 새로운 반복 알고리즘을 제안한다. 이를 위해 먼저 본 학위 논문은 기존 목표 함수를 $\ell_2$ -norm의 $\alpha$ 제곱의 합 형태의 함수로 바꿔 새로운 문제를 제시한다. 잡음에 대한 강인성은 $\alpha$ 의 값을 0에서 2사이의 값을 고르는 방식으로 조절한다. 이때, $\alpha$ =2는 일반적인 부분 공간 클러스터링 목표 함수와 같다. 본 학위 논문에서 제안하는 알고리즘은 새로 설정한 문제의 목표 함수를 해결하는 알고리즘이다. 이때 새로 제안한 목표 함수를 최적화하는 문제는 NP-hard 문제이기 때문에 일반적인 방법으로 최적화 문제를 푸는 것이 불가능하다. 이러한 문제를 해결하기 위해서 일반적으로 기대값 최대화 (EM) 알고리즘처럼 두 가지 최적화 문제를 번갈아 푸는 방법을 사용하는데, 본 학위 논문에서는 이런 반복적인 최적화 문제를 매 번 이상적으로 해결하는 대신, 빠르게 근사하여 전체 연산량을 줄이는 방법을 제안한다. 이 때문에 알고리즘의 정확한 수렴성이 보장되지 않게 되므로 본 학위 논문에서는 제안한 알고리즘이 국소 최소값으로 수렴함을 증명한다. 또한, 제안한 알고리즘이 초기화에 민감하다는 문제점을 안고 있기 때문에, 이를 해결하는 새로운 초기화 알고리즘을 제안하며, 특정한 데이터 환경에서 해당 초기화 알고리즘이 완벽한 클러스터를 복원한다는 것을 증명한다. 마지막으로 이 논문은 제안한 알고리즘의 우수성을 입증하기 위하여 다른 부분 공간 클러스터링 기법들의 잡음에 민감한 정도와 연산 속도를 다양한 데이터셋에 대해 비교 분석한다.
