提出高效算法求解广义对称矩阵分解,提升计算速度与精度。
Fast and Effective Computation of Generalized Symmetric Matrix Factorization
- 基于辅助变量分裂和松弛势函数,设计平均型非单调更新方法。
- 在温和条件下保证全局收敛,理论推导出收敛速率结果。
- 适用于机器学习、图像科学等领域的对称矩阵分解任务。
本文研究一种非凸、非光滑且非利普希茨的广义对称矩阵分解模型,该模型统一了机器学习、图像科学、工程等领域中广泛出现的矩阵分解形式。首先建立了两个精确性性质:在建模层面,证明了当惩罚参数足够大但有限时,对称性诱导的二次惩罚能精确强制对称性,从而完全恢复对应的对称形式;在算法层面,引入辅助变量分裂形式,并建立严格联系原目标函数与松弛势函数驻点的关系。基于这些精确性性质,提出一种基于松弛势函数的平均型非单调交替更新方法(A-NAUM)。每次迭代中,交替近似最小化势函数以更新两个因子块,而辅助块则闭式更新。为确保收敛并提升实际性能,进一步结合平均型非单调线搜索,证明其在弱条件下定义良好。此外,基于Kurdyka-Łojasiewicz性质及其指数,证明整个序列全局收敛至驻点,并给出收敛速率结果。最后,真实数据集上的数值实验验证了A-NAUM的高效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。