Latent Complete Row Space Recovery for Multi-View Subspace Clustering

Hong Tao, Chenping Hou, Yuhua Qian, Jubo Zhu, Dongyun Yi

TL;DR

This paper introduces Latent Complete Row Space Recovery (LCRSR), a novel approach to multi-view subspace clustering that bypasses the computationally expensive step of building large affinity graphs. By directly recovering the shared "row space" of a latent representation, LCRSR achieves superior clustering accuracy while reducing computational complexity from cubic ($O(n^3)$) to quadratic ($O(n^2)$), making it significantly more scalable for large datasets.

What Problem Does This Paper Address?

In many real-world scenarios, we collect data from multiple sources or "views" (e.g., different camera angles in surveillance or both text and images for a webpage). Multi-view subspace clustering aims to group these data points based on the assumption that they are drawn from a union of low-dimensional subspaces.

Traditional methods usually follow a two-step process:

  1. Learn representations: They learn a "self-representation" matrix for each view.
  2. Construct a graph: They combine these into a massive affinity matrix and perform spectral clustering.

This approach has two major flaws:

  • View Insufficiency: Each individual view often only contains partial information. Merging these "incomplete" representations doesn't guarantee a complete picture of the underlying structure.
  • Scalability: Most existing methods have a time complexity that scales cubically with the number of samples ($n^3$). This makes them unusable for large-scale data.

Methods

The authors propose LCRSR, which shifts the focus from learning a full representation matrix to recovering the latent row space.

  • The Latent Assumption: They assume all views are generated from a single, shared latent representation ($L_0$) plus some view-specific sparse noise/errors ($S_0$).
  • Row Space Recovery: Mathematically, the row space of the data determines its cluster membership. Instead of calculating an $n \times n$ affinity matrix, LCRSR seeks an $n \times r$ matrix ($V$) that represents this row space, where $r$ is the rank (usually much smaller than $n$).
  • Robustness: The model uses the $\ell_1$-norm to handle "gross corruptions"—significant errors that might exist in specific views.
  • Optimization: They develop an efficient alternating iterative algorithm. Crucially, because it avoids the "graph construction" and "spectral clustering" steps, the complexity is reduced to $O(n^2(d+r)T)$, where $d$ is dimensionality and $T$ is the number of iterations.

Datasets

The authors evaluated LCRSR on a diverse set of eight datasets:

  • UCI Datasets: Dermatology (Derm) and Forest type mapping (Forest).
  • Text/Image/Gene: Prokaryotic phyla (Prok), Wikipedia articles (Wiki), Caltech7 (images), and USPS (handwritten digits).
  • Video (Background Subtraction): EPFL Laboratory sequences (Lab) and Dongzhimen Transport Hub Crowd (DTHC).

Key Insights and Ideas

  • The "Aha" Moment on Row Spaces: The paper leverages a key theoretical insight: you don't actually need a full representation matrix to cluster data. The row space of the latent representation contains all the necessary information to determine subspace membership.
  • Information Completeness: By modeling the data as coming from a shared latent representation rather than merging view-specific ones, the model ensures that the final clustering is based on the most complete information available across all views.
  • Efficiency via Dimension Reduction: By solving for an $n \times r$ matrix instead of an $n \times n$ matrix, the algorithm naturally scales better. The "bottleneck" becomes the number of samples squared, rather than cubed.

Key Results

  • Superior Accuracy: LCRSR consistently outperformed state-of-the-art baselines (like LMSC, MVSC, and CSMSC) across almost all metrics (NMI, Accuracy, F-score) on the tested datasets.
  • Massive Speedup: In the USPS dataset ($n \approx 9,000$), LCRSR took roughly 78 seconds, while the next best multi-view competitor (CSMSC) took over 500 seconds, and others (like MVSC) took over 62,000 seconds.
  • Background Subtraction: The method proved highly effective at "detaching" moving objects from static backgrounds in multi-camera video feeds, outperforming standard Robust PCA (RPCA) which often left "ghosts" of objects in the background.

Limitations and Future Work

  • Rank Parameter ($r$): The algorithm requires the rank $r$ of the latent representation to be provided or tuned manually. While the authors show the model is somewhat robust to this choice, an automated way to estimate the optimal rank would be a significant improvement.
  • Linearity: The model assumes the underlying subspaces are linear. Extending this to handle non-linear (manifold) structures using kernels or deep learning could be a promising future direction.
  • Memory: While $O(n^2)$ is better than $O(n^3)$, for truly massive datasets (millions of points), even quadratic complexity can become a hurdle, suggesting a need for further stochastic or online versions of the algorithm.

Summary updated

Abstract

Multi-view subspace clustering has been applied to applications such as image processing and video surveillance, and has attracted increasing attention. Most existing methods learn view-specific self-representation matrices, and construct a combined affinity matrix from multiple views. The affinity construction process is time-consuming, and the combined affinity matrix is not guaranteed to reflect the whole true subspace structure. To overcome these issues, the Latent Complete Row Space Recovery (LCRSR) method is proposed. Concretely, LCRSR is based on the assumption that the multi-view observations are generated from an underlying latent representation, which is further assumed to collect the authentic samples drawn exactly from multiple subspaces. LCRSR is able to recover the row space of the latent representation, which not only carries complete information from multiple views but also determines the subspace membership under certain conditions. LCRSR does not involve the graph construction procedure and is solved with an efficient and convergent algorithm, thereby being more scalable to large-scale datasets. The effectiveness and efficiency of LCRSR are validated by clustering various kinds of multi-view data and illustrated in the background subtraction task.
BibTeX
@article{tao2020latent,
  author = {Hong Tao and Chenping Hou and Yuhua Qian and Jubo Zhu and Dongyun Yi},
  title = {{Latent Complete Row Space Recovery for Multi-View Subspace Clustering}},
  journal = {IEEE Trans. Image Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=lVitgeQ8kDX},
}

Loading related content...

Figure