Robust Matrix Factorization with Grouping Effect

Haiyan Jiang, Shuyu Li, Luwei Zhang, Haoyi Xiong, Dejing DouarXiv 2021 · arXiv

Abstract

Matrix Factorization (MF) is a fundamental technique in machine learning and computer vision, yet traditional methods often suffer from sensitivity to outliers and an inability to capture complex structural patterns within data. This paper introduces Robust Matrix Factorization with Grouping Effect (GRMF), a novel framework designed to enhance robustness and interpretability. By employing an $\ell_1$-loss objective and a non-convex grouping regularizer, GRMF generalizes the concept of sparsity to a "grouping effect," where latent factors cluster around multiple centers. Experimental results on several image datasets demonstrate that GRMF significantly outperforms existing methods in recovering data from extreme corruption, maintaining high accuracy even under 50% salt-and-pepper noise.

Introduction

Matrix Factorization is the engine behind diverse applications ranging from recommendation systems to facial recognition. The core objective is to decompose a high-dimensional data matrix into lower-rank latent factor matrices. However, real-world data is frequently plagued by two issues: extreme noise and hidden structural dependencies.

Standard MF techniques typically rely on squared error ($\ell_2$-loss), which is notoriously sensitive to outliers. Furthermore, while many models incorporate sparsity constraints to handle high-dimensional data, they often fail to exploit the "grouping effect"—the tendency of features to form clusters with similar values. The authors of this paper propose GRMF to address these gaps, creating a model that is both resilient to "grossly corrupted" data and capable of automatically discovering feature groups without prior supervision.

The GRMF Framework

The GRMF model is built upon three critical technical pillars designed to balance robustness with structural learning:

1. $\ell_1$-Loss Objective

Unlike traditional methods that minimize the sum of squared residuals, GRMF utilizes the $\ell_1$-norm for its reconstruction error. This choice is mathematically more robust to "salt-and-pepper" noise and heavy-tailed distributions, ensuring that a few extreme outliers do not disproportionately skew the factorization.

2. The Grouping Regularizer

The defining innovation of GRMF is the introduction of a non-convex regularization term, specifically a truncated $\ell_1$ penalty. While standard sparsity constraints push values toward zero, this penalty encourages values to cluster around multiple arbitrary centers. This "grouping effect" essentially enforces a logic where, if two latent values are sufficiently close, they are regularized to become identical. This allows the model to capture nuanced patterns that traditional sparse models might overlook.

3. Optimization Strategy

The resulting objective function is both non-convex and non-smooth, presenting a significant optimization challenge. To solve this, the authors employ an Alternating Minimization framework. The problem is decomposed into subproblems solved via:

  • Difference-of-Convex (DC) programming to manage the non-convexity of the grouping penalty.
  • Alternating Direction Method of Multipliers (ADMM) to handle the non-smooth nature of the $\ell_1$ terms.

Additionally, the paper introduces a Non-negative Matrix Factorization (NMF) variant of GRMF, ensuring latent factors remain positive—a requirement for physically meaningful interpretations in fields like image processing.

Experimental Evaluation

The researchers evaluated GRMF against five benchmark algorithms, including Robust Principal Component Analysis (RPCA) and Truncated SVD, using four prominent image datasets:

  • Extended Yale B (Faces under varying illumination)
  • COIL-20 (Objects at different rotation angles)
  • ORL (Faces with varying expressions and accessories)
  • JAFFE (Japanese female facial expressions)

To simulate extreme real-world conditions, the images were subjected to up to 50% salt-and-pepper noise. Performance was measured primarily through the Relative Mean Absolute Error (RMAE).

Key Insights and Results

Superior Recovery and Robustness

GRMF consistently achieved the lowest RMAE across all datasets. Under the most extreme condition (50% noise), most traditional benchmarks failed to produce recognizable reconstructions. In contrast, GRMF (and its variant RPMF) successfully recovered clean, recognizable images, demonstrating a unique ability to preserve essential features despite massive data corruption.

Automatic Structure Learning

A significant advantage of GRMF is its ability to learn grouping structures automatically. Unlike previous "group sparsity" methods that required predefined group memberships, GRMF discovers these clusters from the raw data. This leads to higher interpretability, as the model naturally groups similar facial features (such as skin tones or shadow regions) into uniform segments.

Rank Resilience

In many MF applications, choosing the correct "rank" (the size of latent factors) is difficult. While competing models often overfit or degrade in performance as the rank increases, GRMF exhibits "rank resilience." The grouping effect acts as a self-regulating mechanism that maintains low reconstruction error even when the rank is not perfectly tuned.

Conclusion and Future Work

GRMF represents a significant step forward in robust matrix factorization by bridging the gap between noise resilience and structural exploitation. By treating sparsity as a special case of a broader grouping effect, the model provides a more flexible and powerful tool for data decomposition.

The primary limitation of the current approach is its computational complexity. The nested optimization loops (Alternating Minimization, DC, and ADMM) make GRMF significantly slower than simpler SVD-based methods. Future research will likely focus on accelerating the training process and exploring more efficient initialization strategies to further enhance the model's utility in large-scale real-time applications.

Summary updated

Abstract

Although many techniques have been applied to matrix factorization (MF), they may not fully exploit the feature structure. In this paper, we incorporate the grouping effect into MF and propose a novel method called Robust Matrix Factorization with Grouping effect (GRMF). The grouping effect is a generalization of the sparsity effect, which conducts denoising by clustering similar values around multiple centers instead of just around 0. Compared with existing algorithms, the proposed GRMF can automatically learn the grouping structure and sparsity in MF without prior knowledge, by introducing a naturally adjustable non-convex regularization to achieve simultaneous sparsity and grouping effect. Specifically, GRMF uses an efficient alternating minimization framework to perform MF, in which the original non-convex problem is first converted into a convex problem through Difference-of-Convex (DC) programming, and then solved by Alternating Direction Method of Multipliers (ADMM). In addition, GRMF can be easily extended to the Non-negative Matrix Factorization (NMF) settings. Extensive experiments have been conducted using real-world data sets with outliers and contaminated noise, where the experimental results show that GRMF has promoted performance and robustness, compared to five benchmark algorithms.
BibTeX
@misc{jiang2021robust,
  author = {Haiyan Jiang and Shuyu Li and Luwei Zhang and Haoyi Xiong and Dejing Dou},
  title = {{Robust Matrix Factorization with Grouping Effect}},
  year = {2021},
  eprint = {2106.13681},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.13681},
}
Figure