Subspace segmentation or subspace learning is a challenging and complicated task in machine learning. This paper builds a primary frame and solid theoretical bases for the minimal subspace segmentation (MSS) of finite samples. Existence and conditional uniqueness of MSS are discussed with conditions generally satisfied in applications. Utilizing weak prior information of MSS, the minimality inspection of segments is further simplified to the prior detection of partitions. The MSS problem is then modeled as a computable optimization problem via self-expressiveness of samples. A closed form of representation matrices is first given for the self-expressiveness, and the connection of diagonal blocks is then addressed. The MSS model uses a rank restriction on the sum of segment ranks. Theoretically, it can retrieve the minimal sample subspaces that could be heavily intersected. The optimization problem is solved via a basic manifold conjugate gradient algorithm, alternative optimization and hybrid optimization, taking into account of solving both the primal MSS problem and its pseudo-dual problem. The MSS model is further modified for handling noisy data, and solved by an ADMM algorithm. The reported experiments show the strong ability of the MSS method on retrieving minimal sample subspaces that are heavily intersected.
As shown in Theorem , the LRR gets the MSDR if and only if the subspaces are independent, that is, @math . This condition implies that each subspace does not intersect with the sum of other subspaces, or equivalently, @math , which is much stricter than that given in Theorem . It is proven by @cite_2 that the iPursuit can separate two subspaces ( @math ) with a high probability. This is one of the special cases shown in Corollary . The condition for LRSSC is similar with that of SSC in the same form and is stricter. We omit the comparison the condition with that of LRSSC, but a detailed comparison with SSC is given below.
@cite_2
2185081213
An important problem in analyzing big data is subspace clustering , i.e., to represent a collection of points in a high-dimensional space via the union of low-dimensional subspaces. Sparse subspace clustering (SSC) and Low-rank representation (LRR) are the state-of-the-art methods for this task. These two methods are fundamentally similar in that both are based on convex optimization exploiting the intuition of Self-Expressiveness. The main difference is that the SSC minimizes the vector @math norm of the representation matrix to induce sparsity while LRR minimizes the nuclear norm (aka trace norm) to promote a low-rank structure. Because the representation matrix is often simultaneously sparse and low-rank, we propose a new algorithm, termed Low-rank sparse subspace clustering (LRSSC), by the combining SSC and LRR, and develop theoretical guarantees of the success of the algorithm. The results reveal interesting insights into the strengths and the weaknesses of SSC and LRR, and demonstrate how the LRSSC can take advantage of both methods in preserving the Self-Expressiveness Property and Graph Connectivity at the same time. A byproduct of our analysis is that it also expands the theoretical guarantee of SSC to handle cases when the subspaces have arbitrarily small canonical angles but are nearly independent.