An Accelerated Bregman Algorithm for ReLU-based Symmetric Matrix Decomposition

Qingsong WangarXiv 2025 · OpenReview

TL;DR

This paper introduces a novel method for decomposing symmetric matrices that are both non-negative and sparse, leveraging the ReLU activation function to capture complex relationships. They propose an efficient "Accelerated Alternating Partial Bregman" (AAPB) algorithm that demonstrates improved convergence and performance over existing methods, particularly for real-world datasets.

What Problem Does This Paper Address?

Low-rank matrix approximation is a cornerstone of many data science tasks, enabling dimensionality reduction and efficient data representation. However, real-world data often exhibit specific structures like symmetry, non-negativity, and sparsity, which standard methods struggle to fully exploit. Symmetric matrices are common in areas like recommender systems, graph analysis, and kernel methods, where relationships are bidirectional. While existing "Nonlinear Matrix Decomposition" (NMD) methods, particularly those using the ReLU activation function, have shown promise for general sparse matrices, the specific case of symmetric non-negative sparse matrices has been less explored. This paper aims to fill that gap by proposing a model and an efficient algorithm tailored for this specific, yet important, matrix structure.

Methods

The core of the paper is the introduction of the ReLU-based Nonlinear Symmetric Matrix Decomposition (ReLU-NSMD) model. This model aims to find a low-rank symmetric matrix $X$ such that $M \approx \max(0, X)$, where $M$ is the input symmetric, non-negative, and sparse matrix. The $\max(0, \cdot)$ function (ReLU) is key here, as it implicitly allows for a broader range of solutions for $X$ when $M$ has zero entries, potentially leading to better low-rank approximations.

To solve this non-convex and non-differentiable optimization problem, the authors propose an Accelerated Alternating Partial Bregman (AAPB) algorithm. This algorithm builds upon existing techniques like Proximal Alternating Linearized Minimization (PALM) but incorporates two key innovations:

  1. Bregman Proximal Gradient (BPG): Instead of standard Euclidean distances, BPG uses Bregman distances. This is crucial because the objective function in their problem doesn't satisfy the standard Lipschitz continuity condition required by many proximal gradient methods. Bregman distances, combined with a specific kernel function, allow them to establish an "L-smooth adaptable property," which is essential for convergence guarantees.
  2. Acceleration: The algorithm incorporates an extrapolation technique (using parameter $\beta_k$) to speed up convergence, drawing inspiration from recent advancements in optimization.

The algorithm iteratively updates two matrices, $W$ and $U$, where the symmetric matrix $X$ is represented as $U U^T$. The $W$-subproblem has a closed-form solution, while the $U$-subproblem is solved using the Bregman proximal gradient step with the acceleration.

Datasets

The paper evaluates its proposed model and algorithm on:

  • Synthetic Datasets: Generated using a pseudo-code that controls matrix dimensions ($m, n$), rank ($r$), and sparsity ($p$). This allows for systematic testing under varying conditions.
  • Real Datasets: Six publicly available datasets are used: ORL, Yable, COIL20, COIL100, PIE, and TDT2. These datasets are described by their dimensions ($m, n$) and the target rank ($r$).

Key Insights and Ideas

  • ReLU for Symmetric Matrices: The paper demonstrates that applying the ReLU activation function to the decomposition of symmetric matrices can yield better low-rank approximations than direct low-rank methods, especially for non-negative sparse data. This is because ReLU can implicitly handle the zero entries in the target matrix $M$ by allowing corresponding entries in $X$ to be non-positive.
  • Bregman Distance for Non-Lipschitz Optimization: The use of Bregman distances is a critical adaptation for solving optimization problems where standard Lipschitz continuity assumptions don't hold. This allows for theoretical convergence guarantees in challenging non-convex settings.
  • Acceleration Enhances Performance: The inclusion of an extrapolation technique (parameter $\beta_k$) demonstrably improves the convergence speed and numerical accuracy of the algorithm, as shown in both synthetic and real-world experiments.
  • Symmetric Structure Matters: The paper highlights that explicitly modeling the symmetric nature of the matrix, rather than treating it as a general matrix, can lead to more effective decomposition and better results.

Key Results

  • Algorithm Efficiency: The proposed AAPB algorithm is shown to be efficient, with a closed-form solution for one of the subproblems and a theoretically guaranteed convergence rate.
  • Improved Accuracy: Numerical experiments on synthetic datasets show that as the extrapolation parameter $\beta_k$ increases, the relative error generally decreases, indicating better approximation quality.
  • Competitive Performance on Real Data: On several real-world datasets, the proposed ReLU-NSMD model with the AAPB algorithm achieves lower relative errors compared to other state-of-the-art symmetric non-negative matrix factorization models (SymANLS, SymHALS, NSMD-APB). For instance, on the PIE dataset, their method achieved a relative error of 3.0e-1, while others were around 3.7e-1 to 3.9e-1.
  • Acceleration Benefits: Comparisons with a non-accelerated version (NSMD-APB, equivalent to $\beta_k=0$) show that the acceleration technique leads to faster convergence and better final results on real datasets.

Limitations and Future Work

  • Parameter Tuning: While the paper explores the effect of the extrapolation parameter $\beta_k$, optimal tuning for different datasets might still be an area for further investigation.
  • Regularization Choices: The paper mentions that other regularization terms (e.g., sparsity, graph regularization) could be incorporated but focuses primarily on Tikhonov regularization. Exploring the impact of different regularization strategies on numerical performance is a potential future direction.
  • Broader Applications: The authors suggest that exploring more models and applications of ReLU-based symmetric matrix factorization remains an avenue for future research. This could include applying the method to different domains or exploring variations of the ReLU function.

Summary updated

Abstract

Symmetric matrix decomposition is an active research area in machine learning. This paper focuses on exploiting the low-rank structure of non-negative and sparse symmetric matrices via the rectified linear unit (ReLU) activation function. We propose the ReLU-based nonlinear symmetric matrix decomposition (ReLU-NSMD) model, introduce an accelerated alternating partial Bregman (AAPB) method for its solution, and present the algorithm's convergence results. Our algorithm leverages the Bregman proximal gradient framework to overcome the challenge of estimating the global $L$-smooth constant in the classic proximal gradient algorithm. Numerical experiments on synthetic and real datasets validate the effectiveness of our model and algorithm.
BibTeX
@misc{wang2025accelerated,
  author = {Qingsong Wang},
  title = {{An Accelerated Bregman Algorithm for ReLU-based Symmetric Matrix Decomposition}},
  year = {2025},
  eprint = {2503.16846},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.16846},
}
Figure