Subspace clustering algorithms are notorious for their scalability issues because building and processing large affinity matrices are demanding. In this paper, we introduce a method that simultaneously learns an embedding space along subspaces within it to minimize a notion of reconstruction error, thus addressing the problem of subspace clustering in an end-to-end learning paradigm. To achieve our goal, we propose a scheme to update subspaces within a deep neural network. This in turn frees us from the need of having an affinity matrix to perform clustering. Unlike previous attempts, our method can easily scale up to large datasets, making it unique in the context of unsupervised learning with deep architectures. Our experiments show that our method significantly improves the clustering accuracy while enjoying cheaper memory footprints.
@math -Subspace Clustering @cite_32 @cite_23 , an iterative methods, can be considered as a generalization of @math -means algorithm. @math -SC shows fast convergence behavior and can handle both linear and affine subspaces explicitly. However, @math -SC methods are sensitive to outliers and initialization. Attempts to make @math -SC methods more robust include the work of Zhang al @cite_17 and Balzano al @cite_34 . In the former, best @math subspaces from a large number of candidate subspaces are selected using a greedy combinatorial algorithm @cite_17 to make the algorithm robust to data corruptions. Balzano al propose a variant of @math subspaces method named @math -GROUSE which can handle the missing data in subspace clustering. However, the resulting methods seem not to producing competitive results compared to methods relying on affinity matrices.
@cite_34 @cite_32 @cite_23 @cite_17
2162991150 1606778734 2118858274 2004744336
Linear subspace models have recently been successfully employed to model highly incomplete high-dimensional data, but they are sometimes too restrictive to model the data well. Modeling data as a union of subspaces gives more flexibility and leads to the problem of Subspace Clustering, or clustering vectors into groups that lie in or near the same subspace. Low-rank matrix completion allows one to estimate a single subspace from incomplete data, and this work has recently been extended for the union of subspaces problem [3]. However, the algorithm analyzed there is computationally demanding. Here we present a fast algorithm that combines GROUSE, an incremental matrix completion algorithm, and k-subspaces, the alternating minimization heuristic for solving the subspace clustering problem. k-GROUSE is two orders of magnitude faster than the algorithm proposed in [3] and relies on a slightly more general projection theorem which we present here. Recently, Bradley and Mangasarian studied the problem of finding the nearest plane to m given points in ℝn in the least square sense. They showed that the problem reduces to finding the least eigenvalue and associated eigenvector of a certain n×n symmetric positive-semidefinite matrix. We extend this result to the general problem of finding the nearest q-flat to m points, with 0≤q≤n−1. In many applications it is desirable to cluster high dimensional data along various subspaces, which we refer to as projective clustering. We propose a new objective function for projective clustering, taking into account the inherent trade-off between the dimension of a subspace and the induced clustering error. We then present an extension of the k-means clustering algorithm for projective clustering in arbitrary subspaces, and also propose techniques to avoid local minima. Unlike previous algorithms, ours can choose the dimension of each cluster independently and automatically. Furthermore, experimental results show that our algorithm is significantly more accurate than the previous approaches. We present a simple and fast geometric method for modeling data by a union of affine subspaces. The method begins by forming a collection of local best-fit affine subspaces, i.e., subspaces approximating the data in local neighborhoods. The correct sizes of the local neighborhoods are determined automatically by the Jones' β 2 numbers (we prove under certain geometric conditions that our method finds the optimal local neighborhoods). The collection of subspaces is further processed by a greedy selection procedure or a spectral method to generate the final model. We discuss applications to tracking-based motion segmentation and clustering of faces under different illuminating conditions. We give extensive experimental evidence demonstrating the state of the art accuracy and speed of the suggested algorithms on these problems and also on synthetic hybrid linear data as well as the MNIST handwritten digits data; and we demonstrate how to use our algorithms for fast determination of the number of affine subspaces.