Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering

Xiao Fu, Kejun Huang, Bo Yang, Wing-Kin Ma, Nicholas D. SidiropoulosIEEE TSP 2016 · DOI

Introduction

Structured Matrix Factorization (SMF) is a fundamental technique in data science used to decompose complex data matrices into meaningful, interpretable parts. This process is essential for tasks such as "unmixing" pixels in hyperspectral satellite imagery or identifying latent topics within large document collections. The core idea is to represent a data matrix $X$ as the product of a signature matrix $A$ and a proportion matrix $S$, where $X \approx AS$.

Figure 1: The standard SMF model where a data matrix $X$ (pixels/documents) is decomposed into a signature matrix $A$ (materials/topics) and a proportion matrix $S$ (abundances/weights).

The Volume Minimization Approach

A prominent method for solving SMF is Volume Minimization (VolMin). Geometrically, this approach assumes that data points are convex combinations of "pure" sources, which act as the vertices of a simplex. The goal of VolMin is to find the smallest possible simplex (the one with minimum volume) that encloses all the observed data points.

However, traditional VolMin algorithms suffer from two major drawbacks:

  1. Sensitivity to Outliers: Outliers located far from the main data cluster can "stretch" the simplex, leading to a poor fit for the majority of the data.
  2. Computational Complexity: The optimization problem, often involving log-determinant minimization, is non-convex and difficult to solve efficiently, particularly for high-dimensional datasets.
Figure 2: Geometric interpretation of the VolMin problem. The shaded region represents the ideal minimum-volume convex hull, while the dashed lines show how a larger hull might enclose the data, illustrating the need for precise volume minimization.

The RVolMin Algorithm

To overcome these challenges, the authors proposed RVolMin, a robust and efficient optimization framework. RVolMin introduces several key innovations:

  • Robust Loss Function: By utilizing an $\ell_2/\ell_p$ mixed norm, the algorithm implements an automated weighting system. Points that do not fit the model (outliers) are assigned lower weights, effectively allowing the algorithm to ignore them during the factorization process.
  • Efficient Optimization: The framework employs Inexact Block Coordinate Descent (BCD) and Nesterov acceleration. This combination allows the algorithm to converge significantly faster than traditional methods—up to 15 times faster per iteration than standard ADMM-based approaches.
  • Theoretical Unification: The authors provided a rigorous proof showing the equivalence of two previously competing conditions for VolMin identifiability, establishing a more solid theoretical foundation for the field.

Experimental Results

The RVolMin algorithm was evaluated against state-of-the-art methods using synthetic data, hyperspectral imagery (AVIRIS Moffett Field), and document corpora (Reuters-21578).

  • Robustness and Accuracy: In simulations with high outlier levels, RVolMin achieved much lower Mean Squared Error (MSE) than previous benchmarks like SISAL. On the Reuters dataset, it improved document clustering accuracy by over 4% compared to Locally Consistent Concept Factorization (LCCF).
  • Real-World Application: In hyperspectral unmixing, RVolMin successfully identified the spectral signatures of materials like water, even in the presence of complex "lake shore" outliers that caused other algorithms to fail.

Conclusion

RVolMin represents a significant advancement in robust matrix factorization. By combining a "self-cleaning" robust loss function with accelerated optimization, it provides a practical solution for decomposing noisy, high-dimensional data. Future work may focus on automated hyperparameter selection and further scaling the algorithm for massive datasets.

Summary updated

BibTeX
@article{fu2016robust,
  author = {Xiao Fu and Kejun Huang and Bo Yang and Wing-Kin Ma and Nicholas D. Sidiropoulos},
  title = {{Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering}},
  journal = {IEEE Trans. Signal Process.},
  year = {2016},
  doi = {10.1109/tsp.2016.2602800},
}
Figure