Abstract
In high-dimensional data analysis, the assumption that all variables reside within a single low-dimensional subspace is often an oversimplification. The VARCLUST algorithm addresses this by modeling variables as linear combinations of hidden latent variables corrupted by noise, distributed across a union of subspaces. By framing variable clustering as a statistical model selection problem, VARCLUST identifies the number of clusters, the partition of variables, and the specific dimensionality of each cluster. This approach utilizes the PEnalized SEmi-integrated Likelihood (PESEL) for rank estimation and a modified Bayesian Information Criterion (mBIC) for variable assignment. Theoretical results demonstrate the consistency of the dimensionality estimator and the convergence of the algorithm. Empirical tests on synthetic and real-world datasets, including genomic and meteorological data, show that VARCLUST outperforms traditional sparse subspace clustering methods, particularly when clusters share underlying latent factors.
Introduction
Principal Component Analysis (PCA) is the standard tool for reducing the dimensionality of high-dimensional datasets. However, PCA assumes a global linear structure that may not exist in complex systems. In fields like genomics or environmental science, variables often form distinct functional units—such as genes within a specific biological pathway or sensors within a geographic microclimate.
Existing "subspace clustering" techniques typically focus on clustering observations (rows). Clustering variables (columns) presents a different set of challenges, particularly the "curse of dimensionality" where the number of variables ($p$) significantly exceeds the number of observations ($n$). VARCLUST was developed to provide a flexible, theoretically grounded framework for variable clustering that can handle varying cluster dimensions and provide robust performance in $p \gg n$ scenarios.
The VARCLUST Framework
Statistical Model Selection
VARCLUST treats variable clustering as a model selection problem. A model is defined by three components:
- $K$: The total number of clusters.
- $\Pi$: The partition of variables into these clusters.
- $\vec{k}$: The vector of dimensions (ranks) for the linear subspaces spanning each cluster.
The algorithm seeks to maximize the posterior probability of the model given the data. To achieve this, the authors employ Laplace approximations to derive a consistent mBIC, which serves as the objective function to be maximized.
The Algorithm: A $K$-Centroids Approach
VARCLUST extends the ClustOfVar algorithm—which was limited to 1-dimensional subspaces—into a more general $K$-centroids framework. The process is iterative:
- Dimension Estimation (PESEL): For a given partition of variables, the algorithm must determine the intrinsic dimensionality of each cluster. This is done using the PEnalized SEmi-integrated Likelihood (PESEL) criterion. The authors provide a mathematical proof that PESEL is a consistent estimator of the true dimension.
- Variable Assignment (mBIC): Variables are reassigned to the cluster whose "centroid" (represented by its principal components) yields the highest mBIC. This criterion naturally penalizes complexity, preventing the model from over-fitting by adding unnecessary clusters or dimensions.
- Convergence: The algorithm iterates between these steps. The authors prove that each iteration is guaranteed to increase the Laplace approximation to the model's posterior probability, ensuring convergence to a local optimum.
Empirical Performance
Synthetic Benchmarks
The authors compared VARCLUST against popular machine learning methods, including Sparse Subspace Clustering (SSC) and Low Rank Subspace Clustering (LRSC). In scenarios where subspaces were independent, most methods performed well. However, when subspaces shared underlying latent factors (overlapping structures), VARCLUST significantly outperformed its competitors. Its ability to account for specific noise levels and individual cluster dimensions allows it to disentangle shared signals that confuse other algorithms.
Real-World Applications
- Meteorological Data: The algorithm was applied to air quality data from 56 sensors in Kraków, Poland. Without any geographic input, VARCLUST grouped sensors into clusters that corresponded to physical neighborhoods, effectively identifying localized pollution patterns.
- Genomic Data (TCGA): In an analysis of the TCGA breast cancer dataset (over 60,000 mRNA transcripts), VARCLUST identified gene clusters that aligned with known Gene Ontology (GO) biological pathways, such as metabolic processes and cell-cell adhesion. This demonstrates the algorithm's utility in discovering biologically meaningful structures in massive, noisy datasets.
Conclusion
VARCLUST provides a robust and theoretically sound methodology for variable clustering. By moving beyond the assumption of a single global subspace and providing a consistent way to estimate local dimensions, it offers a powerful tool for high-dimensional data exploration. The method is computationally accessible through the varclust R package, which supports parallel processing to handle large-scale data. Future work remains in exploring the behavior of the PESEL criterion in extreme high-dimensional limits where both $n$ and $p$ grow at similar rates.
Summary updated