DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Shin, Jinwoo | - |
dc.contributor.advisor | 신진우 | - |
dc.contributor.author | Chun, SangHyuk | - |
dc.contributor.author | 전상혁 | - |
dc.date.accessioned | 2017-03-29T02:38:07Z | - |
dc.date.available | 2017-03-29T02:38:07Z | - |
dc.date.issued | 2016 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=649637&flag=dissertation | en_US |
dc.identifier.uri | http://hdl.handle.net/10203/221748 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전기및전자공학부, 2016.2 ,[iv, 25 p. :] | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Unsupervised Learning | - |
dc.subject | Subspace Clustering | - |
dc.subject | Robust Optimization | - |
dc.subject | High-dimensional Spaces | - |
dc.subject | Iterative Algorithms | - |
dc.subject | 비지도학습 | - |
dc.subject | 부분공간클러스터링 | - |
dc.subject | 로버스트 최적화 | - |
dc.subject | 고차원공간 | - |
dc.subject | 반복 알고리즘 | - |
dc.title | Scalable iterative algorithm for robust subspace clustering | - |
dc.title.alternative | 대용량 부분 공간 클러스터링 반복 알고리즘에 대한 연구 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 325007 | - |
dc.description.department | 한국과학기술원 :전기및전자공학부, | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.