Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization

Symmetric non-negative matrix factorization (SymNMF) is a powerful tool for identifying latent group structures in dependence matrices, such as correlation matrices or tail pairwise dependence matrices (TPDM) used in financial risk. However, the standard objective function requires $O(n^2)$ memory, which limits its application to moderate-sized datasets. This paper addresses this bottleneck by reformulating the SymNMF objective using a trace identity, which removes the need to store $n \times n$ intermediate matrices. The authors evaluate seven algorithm families and over 30 configurations on a GPU-accelerated framework, testing performance on inputs ranging from $n=10^2$ to $n=10^6$.

The trace-identity reformulation effectively doubles the maximum feasible problem size on a single GPU, allowing for efficient computation at $n \approx 10^5$. For multi-node distributions, the approach scales to $n=10^6$. The study finds that at this large scale, the choice of the fastest solver depends heavily on the spectral structure of the input matrix:

• Full-batch AdaGrad performs best on correlation matrices, which typically exhibit a dominant low-rank structure and allow for shorter run times.
• Block-SVRG AdaptGrow is superior for tail-dependence matrices, which are often ill-conditioned and flat, as its lower per-iteration cost is better suited for the longer factorization runs required.

Additionally, the authors demonstrate that while spherical K-means is a cheaper alternative for hard clustering, it becomes degenerate when the matrix collapses toward a single common factor, making soft factorization (SymNMF) necessary in those regimes.

This work provides a practical roadmap for deploying SymNMF in high-dimensional settings, such as large-scale financial portfolio risk estimation. By identifying which adaptive first-order methods are most reliable and efficient for different types of dependence structures, the authors bridge the gap between theoretical matrix factorization and real-world, large-scale data analysis. The provided open-source implementation and systematic benchmarking offer a foundation for future research in high-dimensional latent structure discovery.