PaperlayerView exact revision on arXiv

Source-linked AI summary

Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework

Chun-Guang Li, Chong You, René Vidal

arXiv:1610.05211v2cs.CV

TL;DR

Conventional subspace clustering learns an affinity and segments it in separate stages, without explicitly modeling their dependence. The paper proposes S3C, which jointly learns structured sparse representations and segmentation, extends it with partial side-information through CS3C, and reports effectiveness across several datasets.

  • Problem

    Conventional subspace clustering separates affinity learning from spectral clustering, failing to explicitly capture their natural relationship.

  • Method

    S3C jointly optimizes a segmentation-dependent structured sparse representation and segmentation, while CS3C incorporates partial pairwise side-information into affinity learning.

  • Results

    S3C consistently outperforms SSC on synthetic data and outperforms SSC on Hopkins 155, while experiments span face, motion, synthetic, and cancer datasets.

  • Takeaways & Limitations

    The framework links affinity learning and segmentation through alternating optimization that combines ADMM with spectral clustering.

Abstract

from arXiv · show

Subspace clustering refers to the problem of segmenting data drawn from a union of subspaces. State-of-the-art approaches for solving this problem follow a two-stage approach. In the first step, an affinity matrix is learned from the data using sparse or low-rank minimization techniques. In the second step, the segmentation is found by applying spectral clustering to this affinity. While this approach has led to state-of-the-art results in many applications, it is sub-optimal because it does not exploit the fact that the affinity and the segmentation depend on each other. In this paper, we propose a joint optimization framework --- Structured Sparse Subspace Clustering (S$^3$C) --- for learning both the affinity and the segmentation. The proposed S$^3$C framework is based on expressing each data point as a structured sparse linear combination of all other data points, where the structure is induced by a norm that depends on the unknown segmentation. Moreover, we extend the proposed S$^3$C framework into Constrained Structured Sparse Subspace Clustering (CS$^3$C) in which available partial side-information is incorporated into the stage of learning the affinity. We show that both the structured sparse representation and the segmentation can be found via a combination of an alternating direction method of multipliers with spectral clustering. Experiments on a synthetic data set, the Extended Yale B data set, the Hopkins 155 motion segmentation database, and three cancer data sets demonstrate the effectiveness of our approach.

I. INTRODUCTION

Subspace clustering segments high-dimensional data drawn from multiple low-dimensional subspaces, but conventional methods separately learn affinities and cluster them. S3C integrates these stages by using segmentation information to improve structured sparse representations, with soft and constrained extensions.

  • Prior approach: Existing methods learn an affinity matrix before applying spectral clustering, making clustering quality dependent on the learned affinity.The affinity is commonly induced from a representation matrix C, such as |C| + |C^T|, followed by embedding and k-means.
  • Research gap: The two-stage pipeline fails to explicitly capture the natural relationship between affinity learning and segmentation.The paper argues that clustering can denoise an imperfect affinity and feed information back to improve the representation.
  • Contribution: S3C unifies sparse representation and spectral clustering by minimizing a segmentation-dependent structured sparse norm.Its alternating framework uses spectral-clustering output to construct a segmentation matrix that re-weights representation learning.
  • Variants: Soft S3C uses continuous spectral embeddings for reweighting, while hard S3C uses binary post-k-means assignments.The soft variant captures more information from the previous iteration and is described as more principled.
  • Extension: CS3C incorporates partial pairwise side-information into affinity learning for constrained subspace clustering.The paper reports evaluations on synthetic, face, motion-segmentation, and cancer datasets.
  • Problem: Subspace clustering segments data whose columns are drawn from a union of low-dimensional subspaces into their corresponding subspaces.The paper motivates this setting with applications including images, videos, text, and biological data.

A. Structured Subspace Clustering: A Unified Framework

The unified framework jointly searches for a representation matrix and segmentation matrix, linking their objectives through a subspace structured norm. Alternating optimization updates the representation with ADMM and estimates segmentation approximately with spectral clustering.

  • Motivation: Traditional subspace clustering computes a representation matrix and then applies spectral clustering, but this procedure fails to exploit their correlations.The representation is expected to be subspace-preserving, while the affinity derived from it supports segmentation.
  • Structured interaction: The subspace structured norm quantifies disagreement between the representation matrix C and segmentation matrix Q.For a correct Q, the norm vanishes for a subspace-preserving C and is positive otherwise.
  • Structured interaction: Substituting the affinity induced by C makes the structured norm equivalent to the spectral-clustering objective.This establishes the mathematical connection between representation learning and segmentation.
  • Joint objective: The joint optimization searches simultaneously for C, error matrix E, and a valid segmentation matrix Q under self-expressiveness and segmentation constraints.The representation regularizer promotes subspace preservation, while the structured term reduces inter-cluster affinity.
  • Optimization: Given Q, ADMM efficiently solves the convex representation-and-error subproblem; given C and E, spectral clustering approximately computes Q.Thus, the framework alternates between affinity learning and segmentation updates.

B. Structured Sparse Subspace Clustering (S3C)

S3C combines the standard sparse penalty with a segmentation-dependent penalty, producing a structured sparse representation that discourages cross-subspace coefficients. The formulation generalizes SSC while accommodating noise models and related extensions.

  • Structured sparse norm: S3C combines the standard ℓ1 penalty with a subspace structured norm to penalize coefficients connecting points assigned to different subspaces.The trade-off parameter α controls the contribution of the structured term.
  • Structured sparse norm: The combined objective remains a weighted ℓ1 norm, which facilitates updating the coefficient matrix during optimization.The paper prefers this construction partly because it preserves useful algorithmic properties of ℓ1-based SSC.
  • Noise modeling: The error norm is selected according to prior knowledge about the pattern of noise or corruption.The paper associates ℓ2,1, Frobenius, and ℓ1 norms with different corruption or noise patterns.
  • Framework: The resulting optimization problem is called Structured Sparse Subspace Clustering, or S3C.S3C is the named formulation obtained after incorporating the structured sparse norm into the unified framework.
  • Relation to SSC: S3C generalizes SSC by jointly searching for the sparse representation and segmentation instead of solving them sequentially.When α is zero or Q is initialized noninformatively, the representation subproblem reduces to SSC.
  • Relation to prior methods: Unlike reweighted ℓ1 minimization, S3C reweights coefficients using a segmentation matrix Q rather than the coefficient matrix C itself.The framework is designed to integrate affinity learning and clustering without requiring exact prior segmentation.

C. Constrained Structured Sparse Subspace Clustering: An Extension to Incorporate Side Information

CS^3C incorporates partial must-link and cannot-link side-information by weighting the sparse representation, while retaining the alternating optimization framework used for S^3C.

  • Side-information incorporation: CS^3C encodes must-link and cannot-link constraints by weighting entries of the ℓ1 representation norm with a side-information matrix Ψ.Must-link pairs receive exp(-1), cannot-link pairs exp(+1), and unspecified pairs receive weight 1.
  • Side-information incorporation: Without side-information, the weighted norm ∥C∥Ψ,Q reduces to the original structured sparse norm ∥C∥1,Q.
  • Optimization: The structured sparse representation subproblem is solved with ADMM by alternately updating C, A, E, and the Lagrange multipliers.The algorithm initializes the variables, updates the primal and multiplier variables, increases µ, and checks a reconstruction-residual convergence condition.
  • Optimization: Updating C uses entrywise shrinkage thresholds that depend on the subspace structure matrix Θ rather than one uniform threshold.This is the algorithmic change from standard SSC induced by the subspace structured ℓ1 norm.

B. Spectral Clustering

The spectral-clustering step derives the segmentation matrix from the affinity induced by the coefficient matrix through a graph-Laplacian eigenproblem.

  • Spectral formulation: Given C and E, the segmentation subproblem becomes a spectral-clustering problem based on the graph Laplacian of the data affinity matrix.
  • Graph construction: The affinity matrix is defined as ¯A = 1/2(|C| + |C⊤|), and its degree matrix ¯D contains the row-sum degrees.
  • Spectral formulation: Relaxing Q ∈ Q to Q⊤¯DQ = I yields a normalized-cut formulation solved from the smallest Laplacian eigenvalues.
  • Hard and soft variants: Hard S^3C applies k-means to the rows of the spectral embedding to obtain a binary clustering indicator matrix Q.

C. Algorithm Summary

The S^3C algorithms alternate between sparse representation updates and spectral clustering, with CS^3C modifying the coefficient update to use side-information weights.

  • S^3C procedure: S^3C initializes the coefficients and errors with SSC, then alternates spectral clustering for Q with ADMM for (C, E) until convergence.
  • Hard and soft variants: Hard S^3C constructs a binary structure matrix Θ from the clustering indicator matrix, whereas soft S^3C constructs a real-valued Θ from Q.
  • Computational cost: The main computational burden is solving the structured sparse representation problem, with cost O(T1T2(N^3 + DN^2)).The stated cost arises from matrix inversion and multiplication in the update for A.
  • CS^3C extension: CS^3C changes the coefficient-update step to incorporate Ψ while leaving the remaining optimization procedure largely unchanged.Cannot-link constraints increase penalties, while must-link constraints encourage corresponding coefficient entries.

A. Effects of Using Subspace Structured Norm

The subspace structured norm couples representation learning with segmentation, enabling alternating refinement toward subspace-preserving coefficients and improved clustering behavior under suitable parameters.

  • Joint refinement: The subspace structured norm ∥C∥Q captures the interaction between the representation matrix C and segmentation matrix Q.
  • Joint refinement: When C is subspace-preserving, ∥C∥Q vanishes for the correct binary segmentation matrix Q.
  • Joint refinement: If spectral clustering remains correct despite an imperfectly subspace-preserving C, the next iteration refines C toward being subspace-preserving.
  • Joint refinement: If both subspace preservation and clustering are imperfect, the previous segmentation still refines the representation and provides a better clustering initialization.
  • Theoretical and empirical effects: Under the first two cases, S^3C is guaranteed not to produce an optimal solution worse than original SSC; experiments report improvements under suitable parameters.The observed improvements concern clustering accuracy, affinity connectivity, and the subspace-preserving property of C.

B. Role of Parameter α in S3C

S3C’s parameter α controls the balance between the current SSC solution and the previous segmentation structure. Increasing α during iterations can improve performance, but the resulting alternating algorithm has no optimality guarantee.

  • Role of α: α balances the standard ℓ1 term against the segmentation-dependent norm, with larger values making C more dependent on the previous segmentation matrix Q.Small α produces a solution closer to SSC, whereas large α gives Q greater influence.
  • Strategies for α: Performance improved when α increased during iterations instead of remaining fixed.The paper reports either updating α ← να or progressively reweighting the two norm terms.
  • Strategies for α: The evaluated strategies are fixed α, gradually increasing α, and jointly increasing α while decreasing the ℓ1 term.The latter two use ν > 1 and iteration index T.
  • Convergence: Algorithm 2 has no guarantee of convergence to a global or local optimum because its Q-update approximates a relaxed objective.The experiments nevertheless show convergence for proper parameter settings.
  • Stopping criteria: When α changes during iterations, objective-function and coefficient-change criteria are no longer valid stopping rules.The paper recommends alternative criteria based on changes in the segmentation structure or related quantities.

V. EXPERIMENTS

The experiments evaluate S3C across synthetic, face, motion, and cancer gene-expression data using clustering error and graph-structure measures. Experimental settings largely match SSC, with S3C-specific parameters tuned separately.

  • Datasets: The evaluation covers a synthetic dataset, a face-clustering dataset, a motion-segmentation dataset, and three cancer gene-expression datasets.These datasets are used to assess the effectiveness of S3C.
  • Experimental setup: S3C uses the same general settings as SSC, and hard S3C’s first iteration is equivalent to standard SSC.The default schedule uses ν = 1.2 and Tmax = 10, while the number of clusters is assumed known.
  • Experimental setup: The SSC parameter λ is retained in S3C, while α is tuned on each dataset, with defaults α = 0.1 for hard S3C and α = 1 for soft S3C.The reported evaluations record mean and median subspace-clustering error, along with dispersion statistics.
  • Evaluation measures: SPR measures the fraction of each representation column’s ℓ1 norm contributed by the correct subspaces, and SPR = 1 exactly when C is subspace-preserving.SPR is averaged over all columns and lies in [0, 1].
  • Evaluation measures: CONN measures affinity-graph connectivity using the second-smallest normalized-Laplacian eigenvalue, averaged over subgraphs corresponding to individual subspaces.The reported connectivity is zero exactly when the relevant graph is disconnected.

A. Experiments on Synthetic Data

Experiments evaluate S3C across synthetic, face-clustering, convergence, and motion-segmentation settings, with results generally favoring the joint structured approach over SSC. The studies also examine parameter sensitivity, iterative refinement, and hard versus soft structure matrices.

  • Synthetic data: Both hard S3C and soft S3C consistently outperform SSC on the synthetic data, with larger improvements under 10–50% corruption.Hard S3C performs slightly better than soft S3C in these experiments.
  • Parameter sensitivity: Using an appropriate α improves S3C’s clustering error, affinity connectivity, and subspace-preserving rate, with a reasonable range reported as [10^-3, 2].The study evaluates ERR, CONN, and SPR across 163 two-subject choices in Extended Yale B.
  • Iterative refinement: Hard S3C reduces clustering error from 27.60% to 6.77%, while soft S3C reduces it to 1.56% in the visualization experiment.The hard and soft variants iteratively reweight representation learning using binary and continuous structure matrices, respectively.
  • Hard versus soft structure: Soft structure matrices retain confidence or uncertainty information discarded by binary hard matrices, yielding more accurate clustering results in the illustrated case.Soft S3C converges at the fourth iteration in the corresponding visualization, whereas hard S3C converges at the third.
  • Convergence: During soft S3C iterations, coefficient and structure matrices become more consistent, while structured-norm and k-means-cost elbow trends can support model selection.The convergence evaluation uses three α-setting strategies and tracks relative matrix changes, structured norm, and k-means cost.
  • Extended Yale B: Across all 38 Extended Yale B subjects, SSC, hard S3C, and soft S3C obtain average clustering errors of 34.09%, 27.04%, and 19.82%, respectively.Using α = 0.5 further reduces soft S3C’s clustering error to 15.50%.

C. Experiments on Hopkins 155 Database

On Hopkins 155, the paper evaluates S3C for multi-view affine motion segmentation across videos containing two or three motions. S3C outperforms SSC, with soft S3C slightly better than hard S3C, although gains are minor because the database has relatively low noise.

  • Hopkins 155 contains 155 video sequences with two or three motions, represented as two or three low-dimensional subspaces.
  • S3C algorithms outperform SSC on Hopkins 155, but the improvement is relatively minor because the database has relatively low noise.
  • Soft S3C yields slightly better results than hard S3C by using continuous real-valued weights that retain more detailed information from previous clustering iterations.
  • S3C is evaluated without coefficient selection, thresholding, or ℓ∞ normalization postprocessing.
  • Average processing time per sequence is 4.13s for SSC, 4.68s for hard S3C, and 5.30s for soft S3C.
Loading 1610.05211v2…