PaperlayerView exact revision on arXiv

Source-linked AI summary

Subspace Clustering by Block Diagonal Representation

Canyi Lu, Jiashi Feng, Zhouchen Lin, Tao Mei, Shuicheng Yan

arXiv:1805.09243v1cs.CV

TL;DR

Subspace clustering must group data points from a union of subspaces, while existing methods obtain block diagonal representations through case-specific analyses and indirect priors. The paper unifies the block-diagonal guarantee, introduces a direct regularizer and BDR method, and reports effective real-dataset experiments despite BDR’s nonconvexity.

  • Problem

    Existing subspace clustering methods share a potentially useful block diagonal property, but its guarantees are case-specific and their sparsity or low-rankness priors pursue it indirectly.

  • Method

    The paper derives Enforced Block Diagonal conditions and introduces a k-block diagonal regularizer used in the nonconvex Block Diagonal Representation method.

  • Results

    The unified conditions cover the block diagonal property of existing methods, and experiments on real datasets demonstrate BDR’s effectiveness.

  • Takeaways & Limitations

    Block diagonal structure is treated as a direct prior for subspace clustering rather than being approximated indirectly through sparsity or low-rankness.

  • Takeaways & Limitations

    Correct clustering still requires more than block diagonal structure: each block must be fully connected, while noise or corruptions can violate the assumptions supporting the property.

Abstract

from arXiv · show

This paper studies the subspace clustering problem. Given some data points approximately drawn from a union of subspaces, the goal is to group these data points into their underlying subspaces. Many subspace clustering methods have been proposed and among which sparse subspace clustering and low-rank representation are two representative ones. Despite the different motivations, we observe that many existing methods own the common block diagonal property, which possibly leads to correct clustering, yet with their proofs given case by case. In this work, we consider a general formulation and provide a unified theoretical guarantee of the block diagonal property. The block diagonal property of many existing methods falls into our special case. Second, we observe that many existing methods approximate the block diagonal representation matrix by using different structure priors, e.g., sparsity and low-rankness, which are indirect. We propose the first block diagonal matrix induced regularizer for directly pursuing the block diagonal matrix. With this regularizer, we solve the subspace clustering problem by Block Diagonal Representation (BDR), which uses the block diagonal structure prior. The BDR model is nonconvex and we propose an alternating minimization solver and prove its convergence. Experiments on real datasets demonstrate the effectiveness of BDR.

1 INTRODUCTION

Subspace clustering groups data points drawn from multiple linear subspaces, but existing spectral-type methods use indirect regularizers and prove block diagonal structure case by case. This paper unifies the theoretical analysis and directly pursues block diagonal representations with BDR.

  • Problem: Subspace clustering groups data points approximately drawn from a union of subspaces into clusters corresponding to their underlying subspaces.Applications include motion trajectories, face images, handwritten digits, and movie ratings.
  • Existing methods: Spectral-type methods learn an affinity matrix, embed the data, and apply k-means; their main difference is how the affinity matrix is constructed.Ideally, zero between-cluster affinities yield a block diagonal affinity matrix for clustering.
  • Representation structure: Self-expressiveness represents each sample as a linear combination of other samples, ideally using samples from the same subspace.This produces a k-block diagonal representation matrix whose blocks correspond to subspaces.
  • Clustering condition: A block diagonal representation can reveal true membership, but block diagonal structure alone does not guarantee correct clustering unless each block is fully connected.Sparse within-cluster connections can create the graph-connectivity issue in spectral clustering.
  • Research gap: Existing spectral-type methods commonly obtain the block diagonal property under subspace assumptions, while using sparsity or low-rankness as indirect structure priors.Their proofs are given case by case, and hard k-block constraints may be unnecessarily restrictive.
  • Contributions: The paper proposes unified Enforced Block Diagonal conditions, a k-block diagonal regularizer, and Block Diagonal Representation for directly pursuing the desired structure.BDR is nonconvex, and the paper proposes an efficient solver with a convergence guarantee.

2 THEORY OF BLOCK DIAGONAL PROPERTY

The paper develops unified EBD conditions that guarantee block-diagonal optimal representations under independent subspaces, explaining when regularized solutions recover clustering structure.

  • Representation structure: Under independent subspaces, feasible representations separate each point’s same-subspace contribution from zero contributions by all other subspaces.Theorem 1 characterizes this decomposition as XZB = X and XZC = 0.
  • Representation structure: Without regularization, the solution may retain a nonzero cross-subspace component and therefore need not be block diagonal or reveal true memberships.Regularization is introduced to enforce ZC = 0.
  • EBD conditions: The EBD conditions require permutation invariance, preference for the block-diagonal component, and additive separability across subspaces.The second condition is the key condition enforcing block diagonality, while the third is not necessary for enforcement.
  • EBD conditions: Several function families satisfy the EBD conditions, including element-, column-, and row-separable functions and positive combinations of such functions.Examples include ℓ0, ℓ1, ℓ2, ℓ2,1, and ℓ1,2 regularizers.
  • Unified guarantee: The unified theorem guarantees a block-diagonal optimal solution when the objective satisfies EBD conditions (1)–(2), or when condition (1) holds and the optimum is unique.The guarantee assumes independent subspaces and a nonempty feasible set.
  • Scope and limitation: The resulting within-subspace representation may be too sparse to be fully connected when subspace data columns are highly correlated.This creates a graph-connectivity issue for clustering despite the block-diagonal structure.

3 SUBSPACE CLUSTERING BY BLOCK DIAGONAL REPRESENTATION

The paper defines a regularizer that directly pursues k-block diagonal affinity structure, then uses it in BDR with an alternating solver for subspace clustering. The method is nonconvex, has a practical convergence guarantee, and improves clustering errors on Hopkins 155.

  • Block Diagonal Regularizer: The k-block diagonal regularizer, defined as the sum of the k smallest Laplacian eigenvalues, equals zero exactly when the affinity matrix has k connected components.The construction uses the Laplacian spectrum to characterize connected blocks directly.
  • Block Diagonal Regularizer: Unlike sparsity-based approximation, the proposed regularizer directly encourages block diagonality and controls the number of blocks, although it is nonconvex.The paper notes that rank and nuclear-norm alternatives do not directly control the targeted number of blocks.
  • Block Diagonal Representation: BDR introduces an intermediate representation B and penalizes the discrepancy between Z and B, yielding equivalent models when λ > 0 is sufficiently large.The discrepancy term also makes the Z and B subproblems strongly convex, with unique and stable solutions.
  • Experiments: In a noise-free five-subspace example, BDR produces a k-block diagonal B, whereas the shape interaction matrix and Z are dense and non-block-diagonal.The example uses D = 30, r = 5, and n = 250; the figure compares the matrices and their binarized versions.
  • Optimization of BDR: BDR is solved by alternating updates of W, Z, and B; every subproblem is convex with a closed-form solution, and every limit point is stationary.The convergence guarantee requires no unverifiable assumptions.

4 EXPERIMENTS

Experiments on motion segmentation, face clustering, and handwritten digit clustering evaluate BDR against existing subspace clustering methods. Across these datasets, BDR generally achieves strong clustering performance while offering favorable computational efficiency and empirically decreasing objective values.

  • Motion Segmentation: BDR-B and BDR-Z outperform existing methods on Hopkins 155 in both original and PCA-projected feature settings.The reported mean clustering-error improvements are from 2.18% to 0.93% and from 2.41% to 1.08%, respectively.
  • Motion Segmentation: BDR methods produce almost-correct segmentations for more Hopkins 155 sequences than existing methods.This indicates that the improvement is distributed across most sequences rather than driven only by a few cases.
  • Motion Segmentation: BDR-Z on 2F-dimensional Hopkins 155 data outperforms many state-of-the-art methods using additional preprocessing or post-processing.LatLRR is slightly better but requires more complex processing and higher computational cost.
  • Face Clustering: On Extended Yale B, BDR-B and BDR-Z achieve similar performance and outperform other methods in most cases, with larger improvements as the number of subjects increases.The experiment uses face subsets containing 2, 3, 5, 8, or 10 subjects.
  • Face Clustering: BDR offers a performance–cost trade-off on Extended Yale B: it is faster than most methods except LSR, while S3C is the slowest.BDR-B and BDR-Z have similar running times; LSR remains much faster because it has a closed-form solution.
  • Handwritten Digit Clustering: On MNIST, BDR-B and BDR-Z obtain the smallest clustering errors in most subject-count settings and are more efficient than most methods except LSR.For a five-subject subset, the objective value decreases monotonically across iterations, consistent with the convergence analysis.

5 CONCLUSION AND FUTURE WORKS

The paper unifies theoretical guarantees for block diagonal representations and introduces BDR, which directly encourages this structure. It also provides a convergent solver despite BDR’s nonconvexity and identifies extensions and recovery theory as future directions.

  • 5 CONCLUSION AND FUTURE WORKS: The proposed framework shows that EBD conditions or solution uniqueness guarantee the block diagonal property for a general problem.This unifies case-specific observations across existing spectral-type subspace clustering methods.
  • 5 CONCLUSION AND FUTURE WORKS: The first k-block diagonal regularizer directly encourages k-block diagonal matrices, yielding the Block Diagonal Representation method.BDR uses the block diagonal structure prior rather than indirect sparsity or low-rank priors.
  • 5 CONCLUSION AND FUTURE WORKS: BDR is nonconvex, but the proposed alternating minimization solver has a convergence guarantee without restrictive assumptions.Numerical experiments on real datasets demonstrate BDR’s effectiveness.
  • 5 CONCLUSION AND FUTURE WORKS: Future work includes extending the regularizer to affinity-matrix applications and studying statistical recovery guarantees for block diagonal matrix problems.The paper also identifies optimization challenges caused by the regularizer’s nonconvexity.

Supplementary Material

The supplementary material contains proofs of selected propositions and theorems and should be read together with the main paper.

  • Supplementary Material: The document provides proofs for some propositions and theorems from the main submission.Equation, proposition, and theorem numbering continues from the main paper.
  • Supplementary Material: The supplement is intended to be read alongside the main submission.Its numbering depends on the corresponding main-paper document.
  • Supplementary Material: The document serves as supporting proof material rather than a standalone presentation of the paper.This follows from its stated role of giving proofs and continuing the main submission’s numbering.

A.1 Proof of Proposition 1

The proof establishes the proposition directly from the definitions of the Enforced Block Diagonal conditions.

  • A.1 Proof of Proposition 1: The proposition follows immediately from the definitions of the EBD conditions.The proof does not introduce an additional derivation beyond applying those definitions.
  • A.1 Proof of Proposition 1: The proof’s strategy is definitional rather than computational or experimental.Its sole stated justification is that the result is obvious from the EBD definitions.
  • A.1 Proof of Proposition 1: Proposition 1 is therefore tied directly to how the paper defines the EBD conditions.Understanding those definitions is sufficient for the stated proof step.

A.2 Proof of Proposition 2

The proof verifies the EBD conditions for an entry-separable objective by using permutation invariance, nonnegative entry penalties, and separability.

  • A.2 Proof of Proposition 2: Permutation conjugation preserves the entries of Z while rearranging their positions, so separability ensures EBD condition (1).The proof compares P⊤ZP with Z for any permutation matrix P.
  • A.2 Proof of Proposition 2: EBD condition (2) follows when each entry penalty is nonnegative and vanishes exactly when its argument is zero.The proof states this condition is equivalent to gij(zij) ≥ 0 and gij(zij) = 0 iff zij = 0.
  • A.2 Proof of Proposition 2: EBD condition (3) holds naturally because the objective is separable with respect to the entries of Z.The argument treats f as separable entry by entry.

A.3 Proof of Proposition 3

The proof verifies the three EBD conditions for column- and row-separable functions, then establishes closure properties for positive combinations and sums.

  • Column-separable functions: Column-separable functions satisfy EBD condition (1) because permutation matrices reorder columns while preserving column entries.
  • Column-separable functions: EBD condition (2) follows from the assumed inequality, with equality if and only if the representation equals the block-diagonal target.
  • Column-separable functions: EBD condition (3) follows from the definition of the block-diagonal target and the equality assumption relating the full and within-subspace data.
  • Row-separable functions: The analogous row-separable proof verifies EBD conditions (1)–(3) using row permutations, the assumed inequality, and the corresponding equality condition.
  • Closure properties: Positive combinations preserve all three EBD conditions, and adding a function satisfying only the first part of condition (2) preserves the required properties.

A.7 Proof of Theorem 2

The proof establishes EBD conditions for several regularizers by applying propositions to separable norms, trace Lasso, nuclear norms, and the block-diagonal-inducing term.

  • Separable norms: The ℓ2,1-norm is column-separable, while the ℓ1,2-norm is row-separable; their EBD conditions follow from the corresponding propositions.
  • Trace Lasso: Trace Lasso satisfies the proposition’s conditions through permutation invariance, a partition-based inequality, and the equality characterization when the omitted block vanishes.
  • Combined norms: The sum ∥Z∥1 + λ∥Z∥∗ satisfies all EBD conditions because the component norms satisfy the required closure properties.
  • Block-diagonal-inducing term: For the block-diagonal-inducing term, permutation similarity preserves the entries of Z⊤Z while changing their positions, establishing EBD condition (1).
  • Block-diagonal-inducing term: Decomposing Z into block-diagonal and complementary parts yields the EBD inequality, with equality exactly when the complementary part is zero.

B.2 Proof of Proposition 8

The proof shows that the alternating updates produce a monotonically decreasing, bounded objective sequence and consequently bounded iterates.

  • Descent and boundedness: Optimality of the W, Z, and B updates supplies successive descent relations for the objective with its constraint indicators.
  • Descent and boundedness: The objective is monotonically decreasing and nonnegative, which implies that the sequences {Zk}, {Bk}, and {Wk} are bounded.
  • Descent and boundedness: Summing the descent inequality over iterations provides the cumulative bound used to establish the algorithm’s convergence properties.

B.3 Proof of Theorem 6

The proof extracts a convergent subsequence of the bounded iterates, shows its successive updates share the same limit, and verifies stationarity at that limit.

  • Limit-point analysis: Boundedness yields a subsequence converging to (Z∗, B∗, W∗), and the corresponding next iterates converge to the same point.
  • Stationarity: The optimality conditions of the three updates become the limiting subgradient and gradient conditions at (Z∗, B∗, W∗).
  • Stationarity: Therefore, (Z∗, B∗, W∗) is a stationary point of problem (14).
Loading 1805.09243v1…