Provable Subspace Clustering: When LRR meets SSC
Sparse Subspace Clustering (SSC) and Low-Rank Representation (LRR) are both considered as the state-of-the-art methods for subspace clustering. The two methods are fundamentally similar in that both are convex optimizations exploiting the intuition of "Self-Expressiveness". The main difference is that SSC minimizes the vector 1 norm of the representation matrix to induce sparsity while LRR minimizes 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 combining SSC and LRR, and develops theoretical guarantees of when the algorithm succeeds. The results reveal interesting insights into the strength and weakness of SSC and LRR and demonstrate how LRSSC can take the advantages of both methods in preserving the "Self-Expressiveness Property" and "Graph Connectivity" at the same time.
SUMMARY: This paper proposes a new subspace clustering 
      algorithm called Low Rank Sparse Subspace Clustering (LRSSC) and aims to 
      study the conditions under which it is guaranteed to produce a correct 
      clustering. The correctness is defined in terms of two properties. The 
      self-expressiveness property (SEP) captures whether a data point is 
      expressed as a linear combination of other points in the same subspace. 
      The graph connectivity property (GCP) captures whether the points in one 
      subspace form a connected component of the graph formed by all the data 
      points. The LRSSC algorithm builds on two existing subspace clustering 
      algorithms, SSC and LRR, which have complementary properties. The solution 
      of LRR is guaranteed to satisfy the SEP under the strong assumption of 
      independent subspaces and the GCP under weak assumptions (shown in this 
      paper). On the other hand, the solution of SSC is guaranteed to satisfy 
      the SEP under milder conditions, even with noisy data or data corrupted 
      with outliers, but the solution of SSC need not satisfy the GCP. This 
      paper combines the objective functions of both methods with the hope of 
      obtaining a method that satisfies both SEP and GEP for some range of 
      values of the relative weight between the two objective functions. Theorem 
      1 derives conditions under which LRSSC satisfies SEP in the deterministic 
      case. These conditions are natural generalizations of existing conditions 
      for SSC. But they are actually weaker than existing conditions. Theorem 2 
      derives conditions under which LRSSC satisfies SEP in the random case 
      (data drawn at random from randomly drawn subspaces). Overall, it is shown 
      that when the weight of the SSC term is large enough and the ratio of the 
      data dimension to the subspace dimension grows with the log of the number 
      of points, then LRSSC is guaranteed to satisfy SEP with high probability. 
      I say high, because it does not tend to 1. Finally, Proposition 1 and 
      Lemma 4 show that LRR satisfies GCP (presumably almost surely). 
      Experiments support that for a range of the SSC weight, LRSCC works. 
      Additional experiments on model selection show the usefulness of the 
      analysis. QUALITY: This is an excellent paper. It addresses a 
      difficult and important problem. It derives new conditions that advance 
      the state of the art for the subspace clustering problem. For the first 
      time, easy-to-verify conditions for the case of non-independent subspaces 
      are presented. The conditions are clean, intuitive and useful. Moreover, 
      for the first time an attempt to study both the SEP and the GCP properties 
      together is done. While the story is not complete yet, this is a clear 
      step in the right direction. That said, I do have some comments to improve 
      the paper. Most notably, the discussion in Section 4 needs improvement. 
      Also, there are a number of imprecisions in the literature review that 
      need to be corrected. Finally, the experiments on Hopkins 155 are not 
      entirely clear. My detailed comments are as follows: - For data 
      drawn from a single subspace, I was expecting that graph connectivity 
      would be defined as second eigenvalue of the Laplacian being larger than 
      zero, where the Laplacian = Degree - Affinity, and Affinity = |C|+|C|^T. 
      Somehow, the authors limit themselves to showing that all the entries of C 
      are nonzero. It is probably trivial, but I would have preferred making the 
      connection with connectedness (based on the eigenvalue of the Laplacian) 
      more explicit. - The whole paper is predicated on the idea that as 
      one varies lambda from 0 to infinity one goes from LRR to SSC. But this is 
      not the case, since for lambda = 0, the constraint diag(C) = 0 is not 
      present in standard LRR. Moreover, I don't think there is a value of 
      lambda for which one gets LRR. I was disappointed that this is not 
      mentioned explicitly till the very end of section 4. Can one write the 
      constraint as lambda diag(C) = 0 and the analysis follows? - 
      Following on the point above, it was disappointing that no result on the 
      graph connectivity is shown for lambda > 0. In other words, the paper 
      does not shed light on graph connectivity for SSC or LRSSC. Only for LRR. 
      - The Low Rank Subspace Clustering (LRSC) work of Favaro deserves 
      a discussion. Equation in (6) is in fact an extension of LRSC, not of LRR, 
      because LRSC uses the Frobeniuos norm of the error, while LRR uses the L21 
      norm. Of course they coincide in the noiseless case. Arguably, the name 
      LRSC is more appropriate than LRR throughout, since we are not talking 
      about a low rank representation in general, but one specifically designed 
      for the subspace clustering problem. - The proof of the success of 
      LRR for independent subspaces was not shown in Vidal et al. PAMI 2005 
      [23]. It was shown in Section 2.3 of Vidal et al. IJCV 2008, " Multiframe 
      motion segmentation with missing data using PowerFactorization and GPCA" 
      - To the best of my knowledge, the first application of subspace 
      clustering to hybrid system identification is Vidal et al. CDC 2003, which 
      is much earlier than Bako, Automatica 2011 [2]. - The experiments 
      on Figure 9 seem to be showing a performance that is worse than that of 
      SSC and LRR. As lambda goes to infinity, this should approximately 
      converge to the SSC performance, which is 1.52% for 2 motions, 4.40% for 3 
      motions, and 2.18% for two motions. The reported number of nearly 9% for 3 
      motions seems way off. I understand that the parameter setting may be 
      slightly different. But I wonder what happens if one uses the parameter 
      settings of Elhamifar. Would the behavior of getting a smaller error for 
      some lambda still hold in practice? Overall, I think the experiments needs 
      to be redone to be made comparable with the state of the art. - 
      The quality of English decreases as a function of the page number. -- 
      The articles "the" and "a" are missing in several places 
      (100,123,153,154,205,271,281) -- It should be "a d-dimensional 
      subspace" (085), -- There should be a space before references 
      (040,041,048,221,353), -- It should be "these subspaces, we say a 
      matrix C obeys the SEP" in line 100, -- What is the \perp symbol in 
      115. -- it should be "the only difference being the definition of mu" 
      in 179 -- It should be "Assume random sampling. If ..." in 207 -- 
      It should be "Combining Lemmas 1 and 2, we get" in line 229 -- It 
      should be "and random sampling. It holds" in 240 -- What is 
      probabilistic theorem? in line 245 -- It should be "ignoring constant 
      terms" or "ignoring the constant C" or something like that in 256 -- 
      The grammar of "The graph connectivity problem concerns when SEP is 
      satisfied, whether each block of the solution C to LRSSC represents a 
      connected graph" needs to be revised. -- It should be "If the 
      subspaces are independent, X is not full rank, and the data points" in 274 
      -- It should be "et al." not "et.al" -- There is a "the the" and 
      "if if" somewhere in the paper CLARITY: The paper very clearly 
      conveys the essence, originality and novelty of the contribution. But I 
      had read the previous papers on the subject, and in particular the papers 
      from Candes with the conditions for the deterministic case (inradius), 
      etc. I think that a reader unfamiliar with that paper may have 
      difficulties with definition 3 and the examples that follow. Now, the 
      technical details inside the proofs are of course harder to follow. One 
      minor thing is that the range of lambda values or lambda above a threshold 
      is mentioned earlier in the paper (e.g., 182), but such a range does not 
      appear till Remark 4, so the reader is left wondering what threshold is 
      the paper referring to. Another issue is that it is not clear what "vice 
      versa" refers to in Remark 4. Are you trying to say when lambda is smaller 
      than a threshold versus larger than a threshold? ORIGINALITY: The 
      paper is highly original. The core contributions are to find weaker 
      conditions for the correctness of SSC, new conditions for the correctness 
      of LRR, and conditions for the correctness of a new method LRSSC. To the 
      best of my knowledge, all the material presented in the paper is new. 
      IMPACT: Subspace clustering is receiving increased attention in 
      the community, and sparse and low rank methods are showing excellent 
      performance in many datasets. Understanding why these methods work is in 
      my view fundamental. This paper presents a fundamental step towards 
      achieving this understanding.