High-dimensional data often lie in or close to low-dimensional subspaces. Sparse subspace clustering methods with sparsity induced by L0-norm, such as L0-Sparse Subspace Clustering (L0-SSC), are demonstrated to be more effective than its L1 counterpart such as Sparse Subspace Clustering (SSC). However, these L0-norm based subspace clustering methods are restricted to clean data that lie exactly in subspaces. Real data often suffer from noise and they may lie close to subspaces. We propose noisy L0-SSC to handle noisy data so as to improve the robustness. We show that the optimal solution to the optimization problem of noisy L0-SSC achieves subspace detection property (SDP), a key element with which data from different subspaces are separated, under deterministic and randomized models. Our results provide theoretical guarantee on the correctness of noisy L0-SSC in terms of SDP on noisy data. We further propose Noisy-DR-L0-SSC which provably recovers the subspaces on dimensionality reduced data. Noisy-DR-L0-SSC first projects the data onto a lower dimensional space by linear transformation, then performs noisy L0-SSC on the dimensionality reduced data so as to improve the efficiency. The experimental results demonstrate the effectiveness of noisy L0-SSC and Noisy-DR-L0-SSC. Clustering is an important unsupervised learning procedure for analyzing a broad class of scientific data in biology, medicine, psychology and chemistry. On the other hand, high-dimensional data, such as facial images and gene expression data, often lie in low-dimensional subspaces in many cases, and clustering in accordance to the underlying subspace structure is particularly important. For example, the well-known Principal Component Analysis (PCA) works perfectly if the data are distributed around a single subspace. The subspace learning literature develops more general methods that recover multiple subspaces in the original data, and subspace clustering algorithms Vidal (2011) aim to partition the data such that data belonging to the same subspace are identified as one cluster. Among various subspace clustering algorithms, the ones that employ sparsity prior, such as Sparse Subspace Clustering (SSC) Elhamifar & Vidal (2013) and 0 -Sparse Subspace Clustering ( 0 -SSC) Yang et al. (2016) , have been proven to be effective in separating the data in accordance with the subspaces that the data lie in under certain assumptions. Sparse subspace clustering methods construct the sparse similarity matrix by sparse representation of the data. Subspace detection property (SDP) defined in Section 4.1 ensures that the similarity between data from different subspaces vanishes in the sparse similarity matrix, and applying spectral clustering Ng et al. (2001) on such sparse similarity matrix leads to compelling clustering performance. Elhamifar and Vidal Elhamifar & Vidal (2013) prove that when the subspaces are independent or disjoint, SDP can be satisfied by solving the canonical sparse linear representation problem using data as the dictionary, under certain conditions on the rank, or singular value of the data matrix and the principle angle between the subspaces. SSC has been successfully applied to a novel deep neural network architecture, leading to the first deep sparse subspace clustering method Peng et al. (2016) . Under the independence assumption on the subspaces, low rank representation Liu et al. (2010; is also proposed to recover the subspace structures. Relaxing the assumptions on the subspaces to allowing overlapping subspaces, the Greedy Subspace Clustering Park et al. (2014) and the LowRank Sparse Subspace Clustering achieve subspace detection property with high probability. The geometric analysis in Soltanolkotabi & Cands (2012) shows the theoretical results on subspace recovery by SSC. In the following text, we use the term SSC or 1 -SSC exchangeably to indicate the Sparse Subspace Clustering method in Elhamifar & Vidal (2013) . Real data often suffer from noise. Noisy SSC proposed in handles noisy data that lie close to disjoint or overlapping subspaces. While 0 -SSC Yang et al. (2016) has guaranteed clustering correctness via subspace detection property under much milder assumptions than previous subspace clustering methods including SSC, it assumes that the observed data lie in exactly in the subspaces and does not handle noisy data. In this paper, we present noisy 0 -SSC, which enhances 0 -SSC by theoretical guarantee on the correctness of clustering on noisy data. It should be emphasized that while 0 -SSC on clean data Yang et al. (2016) empirically adopts a form of optimization problem robust to noise, it lacks theoretical analysis on the correctness of 0 -SSC on noisy data. In this paper, the correctness of noisy 0 -SSC on noisy data in terms of the subspace detection property is established. Our analysis is under both deterministic model and randomized models, which is also the model employed in the geometric analysis of SSC Soltanolkotabi & Cands (2012) . Our randomized analysis demonstrates potential advantage of noisy 0 -SSC over its 1 counterpart as more general assumption on data distribution can be adopted. Moreover, we present Noisy Dimensionality Reduced 0 -Sparse Subspace Clustering (Noisy-DR-0 -SSC), an efficient version of noisy 0 -SSC which also enjoys robustness to noise. Noisy-DR-0 -SSC first projects the data onto a lower dimensional space by random projection, then performs noisy 0 -SSC on the dimensionality reduced data. Noisy-DR-0 -SSC provably recovers the underlying subspace structure in the original data from the dimensionality reduced data under deterministic model. Experimental results demonstrate the effectiveness of both noisy 0 -SSC and Noisy-DR-0 -SSC. We use bold letters for matrices and vectors, and regular lower letter for scalars throughout this paper. The bold letter with superscript indicates the corresponding column of a matrix, e.g. A i is the i-th column of matrix A, and the bold letter with subscript indicates the corresponding element of a matrix or vector. · F and · p denote the Frobenius norm and the vector p -norm or the matrix p-norm, and diag(·) indicates the diagonal elements of a matrix. H T ⊆ R d indicates the subspace spanned by the columns of T, and A I denotes a submatrix of A whose columns correspond to the nonzero elements of I (or with indices in I without confusion). σ t (·) denotes the t-th largest singular value of a matrix, and σ min (·) indicates the smallest singular value of a matrix. supp(·) is the support of a vector, P S is an operator indicating projection onto the subspace S . We present provable noisy 0 -SSC that recovers subspaces from noisy data through 0 -induced sparsity in a robust manner, with the theoretical guarantee on its correctness in terms of subspace detection property under both deterministic and randomized models. Experimental results shows the superior performance of noisy 0 -SSC. We also propose Noisy-DR-0 -SSC which performs noisy 0 -SSC on dimensionality reduced data and still provably recovers the subspaces in the original data. Experiment results demonstrate the effectiveness of both noisy 0 -SSC and Noisy-DR-0 -SSC. β = 0. Perform the above analysis for all 1 ≤ i ≤ n, we can prove that the subspace detection property holds for all 1 ≤ i ≤ n.
We propose Noisy-DR-L0-SSC (Noisy Dimension Reduction L0-Sparse Subspace Clustering) to efficiently partition noisy data in accordance to their underlying subspace structure.
{"src": "scitldr-AIC_train", "paper_id": "H1gjM1SFDr"}