Latent Complete Row Space Recovery for Multi-view Subspace Clustering

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

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.

Introduction

In many real-world scenarios, data is collected from multiple sources or "views," such as different camera angles in a surveillance system or combined text and image data 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. However, traditional methods face two major hurdles: view insufficiency, where individual views only provide partial information, and poor scalability, as most methods scale cubically ($O(n^3)$) with the number of samples.

This paper introduces Latent Complete Row Space Recovery (LCRSR), a novel approach 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 to quadratic ($O(n^2)$), making it significantly more scalable for large-scale datasets.

Methodology

LCRSR shifts the focus from learning a full representation matrix to recovering the latent row space. The core assumption is that all views are generated from a single, shared latent representation ($L_0$) plus view-specific sparse noise or errors ($S_0$).

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 the rank $r$ is typically much smaller than the number of samples $n$. To handle "gross corruptions"—significant errors that might exist in specific views—the model utilizes the $\ell_1$-norm for robustness. The resulting optimization problem is solved via an efficient alternating iterative algorithm that avoids the "graph construction" and "spectral clustering" steps entirely.

Experimental Evaluation

The authors evaluated LCRSR on a diverse set of eight datasets, ranging from UCI benchmarks (Dermatology, Forest) and text/image data (Wikipedia, Caltech7, USPS) to multi-view video sequences for background subtraction (EPFL Laboratory and Dongzhimen Transport Hub Crowd).

Multi-view video datasets (a) EPFL Laboratory and (b) Dongzhimen Transport Hub Crowd used for background subtraction tasks.

In background subtraction tasks, LCRSR proved highly effective at detaching moving objects from static backgrounds across multiple camera feeds. Unlike standard Robust PCA (RPCA), which often leaves "ghosts" of moving objects in the background, LCRSR leverages the shared information across views to produce cleaner results.

Key Results and Discussion

LCRSR consistently outperformed state-of-the-art baselines across metrics such as NMI, Accuracy, and F-score. A standout result was observed in the USPS dataset ($n \approx 9,000$), where LCRSR completed the task in roughly 78 seconds, while competing multi-view methods took between 500 and 62,000 seconds.

Comparison of recovery performance between RPCA and LCRSR across varying rank and sparsity parameters; white regions indicate successful recovery.

The technical advantage of LCRSR lies in its theoretical insight: the row space of the latent representation contains all necessary information for subspace membership. By modeling a shared latent representation rather than merging view-specific ones, the model ensures information completeness. Furthermore, solving for an $n \times r$ matrix instead of an $n \times n$ matrix allows the algorithm to scale quadratically, making it a viable solution for larger datasets.

Conclusion and Future Work

LCRSR offers a scalable and robust framework for multi-view subspace clustering. While the current model assumes linear subspaces and requires manual tuning of the rank parameter $r$, it represents a significant step forward in efficiency. Future research may explore automated rank estimation and extending the framework to handle non-linear manifold structures through deep learning or kernel methods.

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},
}
Figure