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

• URL: http://arxiv.org/abs/2607.24518v1
• Date: Mon, 27 Jul 2026 14:56:00 GMT
• Title: Low-Rank Dependence Decomposition via Accelerated Symmetric Non-negative Matrix Factorization
• Abstract summary: We present a large-scale GPU study of seven algorithm families (over 30 configurations) on absolute Pearson correlation and tail pairwise dependence matrices.<n>A trace-identity reformulation eliminates all $n times n$ intermediates, so a single GPU reaches $n approx 105$ and multi-node distribution scales to $n = 106$ and beyond.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Symmetric non-negative matrix factorization (SymNMF) recovers latent group structure from a dependence matrix, but its dense, quadratic-memory objective has confined prior work to moderate sizes. We present a large-scale GPU study of seven algorithm families (over 30 configurations) on absolute Pearson correlation and tail pairwise dependence matrices from Extreme Value Theory, two proxies for empirical risk-factor estimation on large portfolios. A trace-identity reformulation eliminates all $n \times n$ intermediates, so a single GPU reaches $n \approx 10^5$ and multi-node distribution scales to $n = 10^6$ and beyond. Under a two-phase protocol, eleven methods converge at moderate scale; six remain efficient enough at $n = 10^5$ (five AdaGrad-family plus ADMM), and five AdaGrad-family methods still converge at $n = 10^6$: AdaGrad, RMSprop, and three we introduce (Piecewise AdaGrad, Row-Stochastic SVRG, Block-SVRG AdaptGrow). At $n = 10^6$ the fastest solver tracks the matrix spectrum: Block-SVRG AdaptGrow wins on the flat, ill-conditioned tail-dependence spectrum, where its lower per-iteration cost decides a long factorization, and full-batch AdaGrad wins on the dominant-low-rank correlation spectrum, where the run is short. We also benchmark spherical K-means as a hard-label baseline: cheaper when angular cluster structure is present, yet provably degenerate once the matrix collapses toward a single common factor, where the soft factorization remains necessary.

Related papers

• Near-Optimal Nonconvex Matrix Completion [6.287662267319984]
  We study the problem of recovering a low-rank spectral error from a subset of its entries.<n>The method converges condition number methods for the problem.<n>The two methods achieve exact recovery with high probability from $O(nlog nlog(n)$(nrlogr)$(nrlogr)$ observations, respectively.
  arXiv  Detail & Related papers  (2026-09-15T11:57:44Z)
• Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering [0.7614628596146601]
  For arbitrary positive row marginals of equal total mass, the joint KL projection reduces exactly to a strictly convex gauge-fixed dual with only $r-1 effective variables.<n>We specialize this geometry to induce doubly (DS) graph learning through $W=UnameDiag(g)-1Vtop$.<n>Combined with observed sparse fitting, a anchor-edge manifold regularizer, and Bregman backtracking, the resulting mirror-descent method preserves exact feasibility at every accepted step.
  arXiv  Detail & Related papers  (2026-08-09T11:29:05Z)
• Adaptive operator-generated subspaces for effective many-body Hamiltonians [0.0]
  We present the Adaptive Clifford-Algebra Subspacesolver (A-CASE)<n>Overlap, Hamiltonian, observable, and response matrices are reconstructed from one shared Pauli-expectation bank.<n>A grouped iteration propagates finite-shot variability through thresholding, root matching, spectral weights, susceptibility, and broadening.
  arXiv  Detail & Related papers  (2026-08-01T09:51:25Z)
• A Provable Oracle-Free Quantum Algorithm for Nonlinear Dynamics on Hybrid Oscillator-Qubit Processors [14.814423713691623]
  We develop a hybrid qubit-qumode algorithm for nonlinear ordinary differential equations of the form $dotmathbfx=mathbff(mathbfx)$ with warped degree$L$.<n>The algorithm propagates the state density and returns the trajectory as the peak of that density in the small-noise limit.
  arXiv  Detail & Related papers  (2026-07-30T17:10:47Z)
• Exponential Reduction of Mesh Dependence in Quantum Estimation of Parabolic PDE Observables [3.3636842548621275]
  We develop a quantum PDE algorithm that estimates linear and quadratic observables and places fine-coarse cancellation inside the circuit before measurement.<n>We also give a non-Fourier realization based on energyorthogonal dyadic midpoint details in one dimension.
  arXiv  Detail & Related papers  (2026-07-20T16:09:24Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of machine learning algorithms.<n>This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude.<n> Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation.
  arXiv  Detail & Related papers  (2026-06-04T16:04:31Z)
• Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem [1.3537117504260623]
  We show a new class linking group theory, matrix analysis, and statistical estimation.<n>This problem does not appear in the standard catalogs of computational complexity.
  arXiv  Detail & Related papers  (2026-04-04T09:02:16Z)
• go-$m$HC: Direct Parameterization of Manifold-Constrained Hyper-Connections via Generalized Orthostochastic Matrices [0.0]
  We introduce a novel exact parameterization grounded in the theory of generalized orthostochastic matrices.<n>We instantiate this parameterization in go-$m$HC.<n>Our method composes naturally with Kronecker-factorized methods, substantially recovering expressivity at similar FLOP costs.
  arXiv  Detail & Related papers  (2026-04-02T17:51:19Z)
• Evolution Strategies at the Hyperscale [57.75314521465674]
  We introduce EGGROLL, an evolution strategies (ES) algorithm designed to scale backprop-free optimization to large population sizes.<n>ES is a set of powerful blackbox optimisation methods that can handle non-differentiable or noisy objectives.<n>EGGROLL overcomes these bottlenecks by generating random matrices $Ain mathbbRmtimes r, Bin mathbbRntimes r$ with $rll min(m,n)$ to form a low-rank matrix perturbation $A Btop$
  arXiv  Detail & Related papers  (2025-11-20T18:56:05Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.422662003404586]
  We propose an alternating preconditioned gradient descent (APGD) algorithm for noisy matrix sensing problems.<n>APGD consistently achieves the fastest convergence and the lowest computation time compared to the existing alternatives.
  arXiv  Detail & Related papers  (2025-02-01T15:44:39Z)
• Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering [12.544602297450533]
  We aim to identify clusters of nodes where most edges fall within clusters and only few edges fall between clusters. A core step of spectral clustering is performing an eigendecomposition of the corresponding graph Laplacian matrix. This paper introduces a parallelizable approach to dilating the spectrum in order to accelerate SVD solvers and in turn, spectral clustering.
  arXiv  Detail & Related papers  (2022-07-29T10:13:07Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.