Fast and Effective Computation of Generalized Symmetric Matrix Factorization
This work addresses a foundational computational bottleneck in machine learning and related fields by providing a fast and effective algorithm for a broad class of matrix factorization problems, though it is incremental as it builds on existing splitting and convergence techniques.
The paper tackles the problem of computing generalized symmetric matrix factorization, a nonconvex and nonsmooth model unifying many matrix factorization tasks, by proposing an average-type nonmonotone alternating updating method (A-NAUM) that ensures global convergence to stationary points and demonstrates efficiency in numerical experiments on real datasets.
In this paper, we study a nonconvex, nonsmooth, and non-Lipschitz generalized symmetric matrix factorization model that unifies a broad class of matrix factorization formulations arising in machine learning, image science, engineering, and related areas. We first establish two exactness properties. On the modeling side, we prove an exact penalty property showing that, under suitable conditions, the symmetry-inducing quadratic penalty enforces symmetry whenever the penalty parameter is sufficiently large but finite, thereby exactly recovering the associated symmetric formulation. On the algorithmic side, we introduce an auxiliary-variable splitting formulation and establish an exact relaxation relationship that rigorously links stationary points of the original objective function to those of a relaxed potential function. Building on these exactness properties, we propose an average-type nonmonotone alternating updating method (A-NAUM) based on the relaxed potential function. At each iteration, A-NAUM alternately updates the two factor blocks by (approximately) minimizing the potential function, while the auxiliary block is updated in closed form. To ensure the convergence and enhance practical performance, we further incorporate an average-type nonmonotone line search and show that it is well-defined under mild conditions. Moreover, based on the Kurdyka-Åojasiewicz property and its associated exponent, we establish global convergence of the entire sequence to a stationary point and derive convergence rate results. Finally, numerical experiments on real datasets demonstrate the efficiency of A-NAUM.