Abstract
Learning from multi-view data is important in many applications. In this paper, we propose a novel convex subspace representation learning method for unsupervised multi-view clustering. We first formulate the subspace learning with multiple views as a joint optimization problem with a common subspace representation matrix and a group sparsity inducing norm. By exploiting the properties of dual norms, we then show a convex min-max dual formulation with a sparsity inducing trace norm can be obtained. We develop a proximal bundle optimization algorithm to globally solve the minmax optimization problem. Our empirical study shows the proposed subspace representation learning method can effectively facilitate multi-view clustering and induce superior clustering results than alternative multiview clustering methods.
Introduction
In many real-world scenarios, data is "multi-view"—for example, a news story might be represented by text from different news agencies, or a webpage by its content and its incoming hyperlinks. The goal of multi-view clustering is to group these objects by leveraging the complementary information provided by all views.
The challenge is that most existing methods rely on alternating optimization (minimizing one variable while holding others constant). Because the underlying math is usually non-convex, these algorithms often converge to "local optima"—decent solutions, but not the best possible ones. Furthermore, many existing techniques are limited to only two views or lack a principled way to find a truly shared intrinsic representation. This paper introduces a novel convex formulation for multi-view subspace representation learning to address these limitations.
Methodology
The authors propose a Convex Subspace Representation Learning approach. The technical strategy involves three main steps:
- Joint Matrix Factorization: The problem is modeled as finding a common representation matrix ($\Psi$) and view-specific basis matrices ($B^{(v)}$). A group-sparsity inducing norm ($\ell_{2,1}$) is applied to $\Psi$ to encourage a compact, intrinsic representation.
- Convex Relaxation: The original formulation is non-convex. The authors use dual norm properties to transform the problem into a convex min-max formulation. This version uses a matrix trace norm (nuclear norm) as a regularizer, which is a well-known convex proxy for rank minimization.
- Optimization Algorithm: To solve this non-smooth min-max problem, they employ a proximal bundle method. This involves an inner loop using coordinate ascent to handle the matrix variables and an outer loop that uses subgradients to optimize the view-weighting parameters ($\theta$).
Unlike standard spectral clustering which identifies representations via eigenvectors, this method directly learns a shared subspace that minimizes reconstruction error across all views simultaneously.
Experimental Setup
The researchers evaluated their method on three real-world multi-view datasets, summarized in the table below:
- 3-Sources: News articles from BBC, Reuters, and the Guardian (6 topics, 3 views).
- Reuters Multilingual: Documents translated into five languages (6 categories). They created two subsets: Reuters1 (English, French, German) and Reuters2 (English, Spanish, Italian).
- WebKB: Webpages from four universities (Cornell, Texas, Washington, Wisconsin) described by two views: page content and anchor text of incoming links.
Results and Discussion
The performance was measured using Normalized Mutual Information (NMI), a standard metric for clustering quality. The proposed "Convex" method demonstrated significant improvements over various baselines.
Key Insights
- Global Optima Matter: The most striking insight is the comparison between the "Convex" and "NonConvex" versions of their algorithm. The convex version significantly outperformed the non-convex version on almost all datasets, proving that the "local optima" trap is a real hindrance in multi-view learning.
- Intrinsic Shared Space: The core philosophy is that if different views represent the same object, they must share a single "true" location in a latent subspace. By forcing the model to find this one shared $\Psi$, the clustering becomes much more robust to noise in any single view.
- Automated View Weighting: The dual formulation naturally incorporates a weighting mechanism ($\theta$) for different views. This allows the model to automatically prioritize more informative views (like page content) over less informative ones (like link text) during the learning process.
- Consistency: On the WebKB Wisconsin dataset, the Convex method achieved 30.3% NMI, nearly tripling the performance of the NonConvex version (11.8%) and doubling the best spectral baseline (10.8%). While other methods fluctuated across different university datasets, the Convex approach remained consistently high.
Conclusion
While the convex method offers superior performance and global optimality, it comes with increased computational complexity. The authors noted that the convex version can take up to an hour on some datasets compared to a few minutes for the non-convex version. Future work involves scaling the proximal bundle method for larger datasets and extending this convex framework into supervised and semi-supervised multi-view learning.
Summary updated