Source-linked AI summary
Multi-view Low-rank Sparse Subspace Clustering
Maria Brbic, Ivica Kopriva
TL;DR
Multi-view subspace clustering commonly builds affinities separately by view, motivating a joint representation that integrates views while controlling low-rankness and sparsity. MLRSSC learns shared affinities with pairwise or centroid agreement, solves the resulting problems using ADMM, and extends them to nonlinear subspaces in an RKHS. It consistently outperforms other methods on one synthetic and four real-world datasets, while computational complexity remains a stated drawback.
Problem
Existing multi-view subspace clustering methods construct affinity matrices separately for each view, which can propagate noise across views.
Method
MLRSSC jointly learns a shared affinity representation with low-rank and sparsity constraints, pairwise or centroid agreement, ADMM optimization, and an RKHS kernel extension.
Results
MLRSSC consistently outperforms all other methods across tested measures on four real-world and one synthetic dataset.
Takeaways & Limitations
The experiments support combining low-rank and sparsity constraints when learning a shared multi-view affinity matrix.
Takeaways & Limitations
High computational complexity limits the current approach’s suitability for large-scale multi-view problems, and incomplete data remains future work.
Abstract
from arXiv · showhide
Most existing approaches address multi-view subspace clustering problem by constructing the affinity matrix on each view separately and afterwards propose how to extend spectral clustering algorithm to handle multi-view data. This paper presents an approach to multi-view subspace clustering that learns a joint subspace representation by constructing affinity matrix shared among all views. Relying on the importance of both low-rank and sparsity constraints in the construction of the affinity matrix, we introduce the objective that balances between the agreement across different views, while at the same time encourages sparsity and low-rankness of the solution. Related low-rank and sparsity constrained optimization problem is for each view solved using the alternating direction method of multipliers. Furthermore, we extend our approach to cluster data drawn from nonlinear subspaces by solving the corresponding problem in a reproducing kernel Hilbert space. The proposed algorithm outperforms state-of-the-art multi-view subspace clustering algorithms on one synthetic and four real-world datasets.
1 Introduction
Multi-view subspace clustering seeks shared cluster structure across complementary representations, while subspace methods address data whose geometry is not captured by spatial proximity. The paper proposes jointly learning a shared affinity structure with low-rank and sparsity constraints, plus a kernel extension for nonlinear subspaces.
- Multi-view clustering: Multi-view clustering combines complementary representations while assuming that the same cluster structure is shared across views.Examples include documents in multiple languages and images described by different feature descriptors.
- Subspace clustering: Standard proximity-based clustering can fail when points from different subspaces are close or points from the same subspace are far apart.This motivates subspace clustering, which identifies low-dimensional subspaces and cluster memberships.
- Affinity construction: Spectral subspace clustering depends critically on constructing an affinity matrix whose entries define similarities between data points.Sparse and low-rank subspace clustering address this construction through self-expressive representations.
- Existing multi-view methods: Existing multi-view methods typically construct an affinity matrix separately for each view before adapting spectral clustering to multi-view data.The paper identifies noise propagation across these view-specific affinity matrices as a potential problem.
- Proposed approach: MLRSSC jointly learns a shared subspace representation while encouraging both low-rankness and sparsity, with pairwise and centroid-based agreement schemes.The optimization problems are solved using ADMM, and the approach is extended to nonlinear subspaces in an RKHS.
2 Background and Related Work
Subspace clustering constructs affinities for data drawn from unions of subspaces, using low-rank, sparse, or combined representations before spectral clustering. The reviewed methods use convex relaxations and ADMM to obtain representations and convert them into affinity matrices.
- Subspace clustering setup: Subspace clustering assigns data points to unknown linear subspaces and begins by constructing an affinity matrix encoding pairwise similarity.The ideal affinity matrix is block diagonal with respect to the underlying subspaces.
- Low-rank representation: LRR seeks a low-rank representation matrix, with the nuclear norm used as a convex approximation to matrix rank.The text also describes SVD-based solutions and a noisy-data variant.
- Sparse representation: SSC represents each point as a sparse combination of points from its own subspace, using the ℓ1 norm to promote sparsity.The diagonal-zero constraint prevents representing a point using itself.
- Combined constraints: LRSSC combines low-rank and sparsity constraints, while noisy-data formulations approximate the representation under corruption.The supplied passages identify this combined model but do not provide its full displayed optimization objective.
- From representation to clusters: After obtaining a representation matrix with LRR, SSC, or LRSSC, the method constructs an affinity matrix and applies spectral clustering to its graph Laplacian.Spectral clustering then uses k-means on the Laplacian eigenvectors to obtain cluster memberships.
3 Multi-view Low-rank Sparse Subspace Clustering
MLRSSC learns view-specific representations jointly while encouraging consensus, sparsity, and low-rankness, then derives a shared affinity matrix for spectral clustering. It provides pairwise and centroid-based regularization schemes, supports corrupted data, and is optimized with ADMM.
- MLRSSC seeks a joint representation matrix balancing agreement across views with sparsity and low-rankness.
- Pairwise MLRSSC regularizes similarities between representation matrices, whereas centroid-based MLRSSC pulls them toward a common centroid.
- The optimization is convex under linear constraints, and ADMM provides exact subproblem solutions with global convergence guarantees.
- Pairwise MLRSSC: For pairwise MLRSSC, view representations are averaged element-wise to form Cavg, then spectral clustering uses W = |Cavg| + |Cavg|T.
- Complexity: Algorithm 1 has complexity O(TnvN^3); experiments typically converged in about 15–20 iterations, while spectral clustering costs O(N^3).
- Centroid-based MLRSSC: Centroid-based MLRSSC computes the joint affinity matrix directly from the centroid, W = |C∗| + |C∗|T, without combining view affinity matrices.
4 Kernel Multi-view Low-rank Sparse Subspace Clustering
Kernel MLRSSC extends multi-view low-rank sparse subspace clustering to nonlinear subspaces by implicitly mapping data into a high-dimensional feature space. The resulting optimization is solved through alternating updates and spectral clustering on the learned affinity matrix.
- Optimization: The algorithm alternates updates of view-specific variables, centroids, and dual variables before applying spectral clustering to the final affinity matrix.For the centroid-based procedure, the final affinity is W = |C*| + |C*|T.
- Kernel extension: Kernel MLRSSC addresses nonlinear subspaces by implicitly mapping data points into a high-dimensional reproducing-kernel Hilbert space.This extends the linear-subspace affinity model to nonlinear manifold structure.
- Kernel extension: The feature map Φ transforms the original input space X into a possibly infinite-dimensional feature space F.The kernel formulation uses dot products and Gram matrices rather than explicit feature coordinates.
- Optimization: Pairwise and centroid-based kernel MLRSSC retain the same update rule for A(v) while optimizing their respective feature-space objectives under zero-diagonal representation constraints.The two variants differ in their regularization structure, but their A(v) update is shared.
5 Experiments
Experiments evaluate MLRSSC on one synthetic and four real-world multi-view datasets against state-of-the-art methods and baselines. MLRSSC consistently achieves stronger clustering performance, with parameter stability, convergence within 20 iterations, and a computational-cost trade-off.
- Datasets and setup: MLRSSC is evaluated on one synthetic and four real-world datasets, including UCI Digit, Reuters, 3-sources, and Prokaryotic phyla.The experiments compare pairwise, centroid-based, and kernel MLRSSC variants with established multi-view subspace clustering methods and LRSSC baselines.
- Datasets and setup: The evaluation reports precision, recall, F-score, NMI, and adjusted rand index using means and standard deviations over 20 k-means runs.All compared methods use k-means as the final clustering step.
- Clustering results: MLRSSC consistently outperforms all compared methods across the five datasets and tested measures.Average NMI exceeds the second-best method by 7%, 9%, 4%, 12%, and 2% on 3-sources, Reuters, UCI Digit, Prokaryotic, and synthetic datasets, respectively.
- Clustering results: Pairwise and centroid-based MLRSSC perform comparably overall, while pairwise MLRSSC is significantly better on Prokaryotic except in recall.Linear MLRSSC performs better on 3-sources and Reuters, whereas kernel MLRSSC performs better on UCI Digit, Prokaryotic, and synthetic data, with additional kernel-parameter tuning.
- Parameter sensitivity: MLRSSC remains generally stronger across tested β1 and λ(v) values, with centroid-based MLRSSC as the main Prokaryotic exception.The results characterize MLRSSC as stable when β1, β2, and λ(v) are selected within an appropriate range.
- Computational time and convergence: MLRSSC is more efficient than CSMSC but has higher computational cost than Co-Reg SC and RMSC.On the UCI Digit dataset, pairwise and centroid regularization have similar computational times, and pairwise MLRSSC converges within 20 iterations on all four real-world datasets.
6 Concluding Remarks
MLRSSC learns a joint multi-view subspace representation with an affinity matrix constrained by sparsity and low-rankness. It also extends to nonlinear subspaces, while computational efficiency and incomplete-data handling remain future work.
- MLRSSC jointly learns an affinity matrix across views under sparsity and low-rank constraints.The approach uses a shared subspace representation across all views.
- The method derives ADMM-based algorithms for pairwise and centroid-based regularization schemes.
- MLRSSC extends to nonlinear subspaces by solving the corresponding optimization problem in reproducing kernel Hilbert space.
- Experiments on multi-view datasets from various domains show that the proposed algorithms outperform state-of-the-art multi-view subspace clustering algorithms.
- High computational complexity remains a drawback, motivating future work on large-scale problems and incomplete data.