Source-linked AI summary
Correlation Adaptive Subspace Segmentation by Trace Lasso
Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan
TL;DR
Subspace segmentation seeks to partition data drawn from a union of subspaces, but existing methods trade off sparse selection against grouping correlated data. CASS applies trace Lasso to balance these properties, with theory and experiments showing effectiveness across segmentation and semi-supervised settings.
Problem
Subspace segmentation requires an affinity matrix that is sparse across clusters while retaining enough within-cluster connections to group correlated data.
Method
CASS uses trace Lasso, which adapts to data correlation and balances sparsity with grouping effect.
Results
CASS achieves the best reported results across the evaluated Hopkins 155, Extended Yale B, MNIST, and semi-supervised experiments.
Takeaways & Limitations
CASS can produce affinity matrices close to block diagonal while preserving grouping of correlated data.
Takeaways & Limitations
For noisy data, obtaining a block-sparse solution is difficult, and the norm choice depends on the noise.
Abstract
from arXiv · showhide
This paper studies the subspace segmentation problem. Given a set of data points drawn from a union of subspaces, the goal is to partition them into their underlying subspaces they were drawn from. The spectral clustering method is used as the framework. It requires to find an affinity matrix which is close to block diagonal, with nonzero entries corresponding to the data point pairs from the same subspace. In this work, we argue that both sparsity and the grouping effect are important for subspace segmentation. A sparse affinity matrix tends to be block diagonal, with less connections between data points from different subspaces. The grouping effect ensures that the highly corrected data which are usually from the same subspace can be grouped together. Sparse Subspace Clustering (SSC), by using $\ell^1$-minimization, encourages sparsity for data selection, but it lacks of the grouping effect. On the contrary, Low-Rank Representation (LRR), by rank minimization, and Least Squares Regression (LSR), by $\ell^2$-regularization, exhibit strong grouping effect, but they are short in subset selection. Thus the obtained affinity matrix is usually very sparse by SSC, yet very dense by LRR and LSR. In this work, we propose the Correlation Adaptive Subspace Segmentation (CASS) method by using trace Lasso. CASS is a data correlation dependent method which simultaneously performs automatic data selection and groups correlated data together. It can be regarded as a method which adaptively balances SSC and LSR. Both theoretical and experimental results show the effectiveness of CASS.
1. Introduction
Subspace segmentation partitions data drawn from a union of subspaces, using an affinity matrix for spectral clustering. The paper motivates CASS as a trace-Lasso method that balances sparsity with grouping correlated data.
- Problem: Subspace segmentation aims to cluster data according to the underlying subspaces from which they were drawn.The problem applies to data approximately lying in a mixture of subspaces, including motion, face, and image segmentation.
- Problem: Spectral clustering requires an affinity matrix that is ideally block diagonal, with connections primarily among points from the same subspace.The matrix is constructed from representation coefficients measuring similarities between data points.
- Existing methods: SSC promotes sparse representations but can ignore correlated samples, whereas LRR and LSR group correlated data but generally produce dense representations.SSC may randomly select one representative from a correlated group; noisy LRR solutions are often dense because nuclear-norm minimization lacks subset selection.
- CASS: CASS uses trace Lasso to adapt to data correlation while encouraging both grouping effect and sparsity.Trace Lasso depends on X^T X, which encodes correlations among data, and adaptively interpolates SSC and LSR.
- Theory: Under independent subspaces and the proposed EBS conditions, CASS obtains a block-sparse solution.Trace Lasso is stated to satisfy the EBS conditions, while its grouping effect makes coefficients for correlated data approximately equal.
2. Correlation Adaptive Subspace Segmentation by Trace Lasso
CASS uses trace Lasso to adapt representation to data correlation, combining subset selection with grouping while preserving block sparsity under independent subspaces. It constructs an affinity matrix from leave-one-out coefficients and applies NCuts for segmentation.
- Trace Lasso: Trace Lasso adapts to data correlation by interpolating between the ℓ1-norm for uncorrelated data and the ℓ2-norm for highly correlated data.For intermediate correlations, trace Lasso lies between these two norms.
- CASS formulation: CASS uses trace Lasso for adaptive subset selection and is designed to balance sparsity with the grouping effect.The method is described as adaptively interpolating SSC and LSR.
- Theoretical properties: Under sufficiently sampled independent subspaces, CASS produces a block-sparse solution.This property follows because trace Lasso satisfies the enforced block sparse conditions.
- Noisy data: For noisy data, CASS supports different noise models through norm choices, while the appropriate norm depends on the noise type.The paper distinguishes ℓ2 modeling for small dense noise from ℓ1 modeling for a small fraction of gross corruptions.
- Theoretical properties: For correlated data, CASS groups data points through approximately equal coefficients, while retaining sparsity between clusters.The paper notes that CASS may have a weaker grouping effect than LRR and LSR.
- Segmentation algorithm: The algorithm excludes each target point from its dictionary, assembles the resulting coefficients into W*, symmetrizes them into an affinity matrix, and applies NCuts.The affinity matrix is defined as (|W*| + |W*T|)/2, and NCuts segments the data into k groups.
3. Experiments
Experiments compare CASS with SSC, LRR, and LSR on motion, face, and handwritten-digit segmentation, plus semi-supervised face classification. CASS achieves the strongest reported results while producing affinity structures that preserve grouping and enhance sparsity.
- Data sets and settings: The experiments use Hopkins 155 motion sequences, Extended Yale B face images, and a subset of MNIST digits, with PCA applied before segmentation.Hopkins 155 contains 156 two- or three-motion sequences; Extended Yale B tasks use 5, 8, or 10 subjects.
- Hopkins 155 motion segmentation: CASS achieves a 2.42% misclassification error across all 156 Hopkins 155 sequences, versus 2.50% for the best previously reported LSR result.The authors note that CASS can behave similarly to LSR when correlations are strong and PCA reduces dimensionality.
- Extended Yale B clustering: CASS outperforms SSC, LRR, and LSR on all three Extended Yale B clustering tasks, reaching 94.03%, 91.41%, and 81.88% for 5, 8, and 10 subjects.Improvements are especially significant for the 8- and 10-subject tasks.
- Semi-supervised learning: CASS achieves the best semi-supervised classification performance across the tested training-set sizes, with all accuracies above 90%.The experiment uses Markov random walks on affinity graphs for the 10-subject Extended Yale B task.
- MNIST segmentation: On MNIST, CASS obtains the best segmentation accuracy, 73.80%, while producing an affinity matrix close to block diagonal by preserving the grouping effect.The authors attribute remaining difficulty partly to handwritten digits not fitting the subspace structure well.
4. Conclusions and Future Work
CASS uses trace Lasso to jointly encourage sparsity and grouping, with theoretical, experimental, and semi-supervised evidence supporting its effectiveness while leaving several future directions.
- CASS uses trace Lasso to simultaneously encourage grouping effect and sparsity in subspace segmentation.Its adaptive behavior comes from balancing ℓ1-norm and ℓ2-norm.
- Theoretically, CASS can reveal the true segmentation when the subspaces are independent.
- Experiments on Hopkins 155, Extended Yale B, and MNIST show CASS effectiveness.Similar improvement is observed in semi-supervised learning on Extended Yale B.
- Future work includes learning compact discriminative dictionaries, exploring additional applications, and developing more scalable optimization algorithms.The paper specifically mentions classification, dimensionality reduction, and semi-supervised learning as potential applications.