State-Dependent Lyapunov Method for Rank-1 Matrix Factorization

arXiv:2604.26993v1 Announce Type: cross Abstract: We study gradient descent for rank-1 matrix factorization through a certificate-based viewpoint. The central object is a parameterized quadratic certificate I(elta;,dot) whose level sets shrink along the dynamics, thereby inducing a monotone state parameter elta_t. In the certified regime, this mechanism yields convergence to a global minimizer; in the post-critical regime, it forces trajectories toward a terminal balanced manifold. To explain the origin of these certificates, we formulate a state-dependent Lyapunov framework based on structural axioms. Within this framework, the scalar certificate is uniquely determined, and the same local Lagrange analysis constrains the signal and noise blocks of rank-1 extensions. Thus, the certificates arise from the monotonicity structure of the dynamics, rather than from ad hoc algebraic constructions. We also provide numerical evidence beyond the proved cases. For the 2-dimensional rank-1 approximation problem X=diag(1,sigma) with sigmain(0,1), the experiments are consistent with the existence of a C^1 admissible certificate branch. For the quartic-augmented scalar loss frac12(ab-1)^2+mu(ab-1)^4, the same scalar certificate remains predictive for several values of mu after choosing an empirical threshold. These experiments suggest that the state-dependent Lyapunov method may extend beyond the settings proved in this paper.

Source: arXiv cs.LG | 2026-05-01