An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition

Qingsong Wang, Yunfei Qu, Chunfeng Cui, Deren Han

TL;DR

This paper introduces a novel algorithm, AAPB, for a more generalized form of matrix decomposition that leverages the ReLU activation function. This method is particularly effective for sparse, non-negative data and offers improved convergence speed and accuracy compared to existing techniques, making it valuable for tasks like clustering and feature extraction.

What Problem Does This Paper Address?

Traditional low-rank matrix decomposition methods, like Singular Value Decomposition (SVD) and Non-negative Matrix Factorization (NMF), work well when data inherently has a low-rank structure. However, many real-world datasets, especially large, sparse, and non-negative ones, don't perfectly fit this assumption. This limitation is particularly evident with identity matrices, which are sparse but full-rank. To address this, researchers have explored using the Rectified Linear Unit (ReLU) activation function in matrix decomposition (ReLU-NMD) to capture intrinsic low-rank properties of sparse matrices. However, existing ReLU-NMD models face challenges like computational complexity, numerical instability, and the inability to incorporate various regularization terms (like sparsity and non-negativity) simultaneously. This paper aims to bridge this gap by proposing a more flexible model and an efficient algorithm to solve it.

Methods

The core of this paper is the development of an Accelerated Alternating Partial Bregman (AAPB) algorithm. This algorithm is designed to solve a generalized two-block optimization problem that encompasses the authors' proposed ReLU-based matrix decomposition model. The AAPB algorithm combines ideas from alternating minimization and Bregman proximal gradient methods.

Key methodological aspects include:

  • Generalized Model: The paper proposes a model that incorporates regularization terms ($H_1(U)$ and $H_2(V)$) for the factor matrices, allowing for simultaneous promotion of low-rankness, sparsity, and non-negativity.
  • Alternating Partial Bregman (APB): This is the foundation of their approach. It iteratively updates variables by leveraging closed-form solutions for certain subproblems (like the W-subproblem) and using Bregman proximal gradient for others where closed-form solutions are not available.
  • Acceleration: The AAPB algorithm incorporates an extrapolation technique to accelerate convergence, which is a key improvement over standard APB.
  • L-smooth Adaptable Property: The convergence analysis relies on this property, which is a generalization of Lipschitz continuity and is crucial for analyzing nonconvex and nonsmooth optimization problems.
  • Closed-form Solutions: For specific regularization choices, the paper derives closed-form solutions for the (U, V)-subproblem, which significantly speeds up computation.

Datasets

The paper evaluates its proposed methods on:

  • Synthetic Datasets: Generated using randn with specific parameters to test the algorithms' performance.
  • Real-World Datasets:
    • Graph Regularized Clustering: COIL20, PIE, and TDT2 datasets were used.
  • Sparse NMF Basis Compression: ORL and YaleB facial image datasets were used.
  • Other Real-World Datasets (for problem (24)): netz4504-dual, mycielskian11, and the MNIST dataset.

Key Insights and Ideas

  • ReLU's Power for Sparsity: The paper strongly suggests that the ReLU function's inherent properties are particularly well-suited for handling sparse data structures, leading to better performance in such scenarios.
  • Unified Framework: The proposed model (9) offers a unified framework to simultaneously enforce low-rankness, sparsity, and non-negativity in matrix decomposition, which is a significant advantage over methods that focus on only one or two of these properties.
  • Efficiency of AAPB: The acceleration technique in AAPB, combined with the ability to derive closed-form solutions for subproblems in specific cases, leads to significantly faster convergence compared to existing methods.
  • Flexibility of Bregman Methods: The use of Bregman distances makes the algorithm adaptable to various regularization terms, offering broad applicability.

Key Results

  • Convergence Guarantees: The paper establishes both sublinear and global convergence properties for the AAPB algorithm under mild assumptions.
  • Improved Clustering Accuracy: In graph-regularized clustering experiments, the proposed ReLU-based model (20) consistently outperformed classical graph-regularized NMF (21) and direct K-means, with the accelerated AAPB version showing the best results. For example, on the TDT2 dataset, NMD-AAPB achieved 84.24% accuracy compared to 77.69% for NMD-APB and 75.43% for BPG.
  • Effective Sparse NMF Compression: Numerical experiments on ORL and YaleB datasets demonstrated that NMD-APB and NMD-AAPB effectively compress sparse NMF bases, achieving lower relative errors than TSVD. For the YaleB dataset, NMD-AAPB achieved a TolNMF of 0.16, compared to 0.17 for NMD-APB and 0.19 for TSVD.
  • Faster Convergence: Numerical results (Figure 4 and 5) show that NMD-APB and NMD-AAPB converge significantly faster than PPALM and iPPALM, especially on real-world datasets.

Limitations and Future Work

  • Parameter Tuning: While the paper sets the extrapolation parameter $\beta_k$ to a fixed value (0.6) for simplicity, it notes that an adaptive approach could potentially yield even better results. Finding optimal parameters for the regularization terms ($\mu_0, \eta_1, \eta_2$) is also a practical consideration.
  • Closed-form Solutions: The paper highlights that while closed-form solutions exist for certain regularization choices, for more complex or arbitrary regularization terms, the subproblems might not have closed-form solutions, requiring further algorithmic development.
  • Generalization: The paper focuses on two-block optimization problems. Extending the AAPB framework to handle more blocks or different types of optimization problems could be a future direction.
  • Theoretical Analysis: While convergence is established, further theoretical insights into the behavior of the algorithm with different kernel-generating distances or under more relaxed assumptions could be explored.

Summary updated

Abstract

Despite the remarkable success of low-rank estimation in data mining, its effectiveness diminishes when applied to data that inherently lacks low-rank structure. To address this limitation, in this paper, we focus on non-negative sparse matrices and aim to investigate the intrinsic low-rank characteristics of the rectified linear unit (ReLU) activation function. We first propose a novel nonlinear matrix decomposition framework incorporating a comprehensive regularization term designed to simultaneously promote useful structures in clustering and compression tasks, such as low-rankness, sparsity, and non-negativity in the resulting factors. This formulation presents significant computational challenges due to its multi-block structure, non-convexity, non-smoothness, and the absence of global gradient Lipschitz continuity. To address these challenges, we develop an accelerated alternating partial Bregman proximal gradient method (AAPB), whose distinctive feature lies in its capability to enable simultaneous updates of multiple variables. Under mild and theoretically justified assumptions, we establish both sublinear and global convergence properties of the proposed algorithm. Through careful selection of kernel generating distances tailored to various regularization terms, we derive corresponding closed-form solutions while maintaining the $L$-smooth adaptable property always holds for any $L\ge 1$. Numerical experiments, on graph regularized clustering and sparse NMF basis compression confirm the effectiveness of our model and algorithm.
BibTeX
@article{wang2025accelerated,
  author = {Qingsong Wang and Yunfei Qu and Chunfeng Cui and Deren Han},
  title = {{An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition}},
  journal = {J. Sci. Comput},
  year = {2025},
  doi = {10.1007/s10915-025-03067-w},
}
Figure