提出可证明收敛的算法，解决带ReLU的非线性矩阵分解难题
An extrapolated and provably convergent algorithm for nonlinear matrix decomposition with the ReLU function
- 用隐变量重构问题，将原问题转化为更易优化的3B-RMD形式
- 证明块坐标下降法在3B-RMD上的收敛性，且新算法加速明显
- 适用于数据压缩、缺失非随机矩阵补全等场景，适合研究者参考
ReLU矩阵分解（RMD）是给定一个稀疏非负矩阵X和分解秩r，寻找一个秩为r的矩阵Θ，使得X≈max(0,Θ)。该问题属于非线性矩阵分解（NMD）的一种，应用于数据压缩、缺失非随机的矩阵补全及流形学习。标准模型最小化最小二乘误差‖X−max(0,Θ)‖²_F，但该优化问题不可微且高度非凸。为此，Saul提出一种替代模型——隐变量RMD（Latent-RMD），引入隐变量Z满足max(0,Z)=X，同时最小化‖Z−Θ‖²_F。本文首先证明两种形式可能产生不同的低秩解Θ。随后对Latent-RMD进行重参数化，得到3B-RMD，其中Θ=WH，W有r列，H有r行。其次，证明了应用于3B-RMD的块坐标下降（BCD）方法的收敛性。第三，提出一种新型外推版BCD（eBCD），在温和假设下同样保证收敛。实验表明eBCD相比标准BCD有显著加速效果，并在合成与真实数据集上优于当前最优方法。
原文摘要 · Abstract (English)
ReLU matrix decomposition (RMD) is the following problem: given a sparse, nonnegative matrix $X$ and a factorization rank $r$, identify a rank-$r$ matrix $Θ$ such that $X\approx \max(0,Θ)$. RMD is a particular instance of nonlinear matrix decomposition (NMD) that finds application in data compression, matrix completion with entries missing not at random, and manifold learning. The standard RMD model minimizes the least squares error, that is, $\|X - \max(0,Θ)\|_F^2$. The corresponding optimization problem, Least-Squares RMD (LS-RMD), is nondifferentiable and highly nonconvex. This motivated Saul to propose an alternative model, \revise{dubbed Latent-RMD}, where a latent variable $Z$ is introduced and satisfies $\max(0,Z)=X$ while minimizing $\|Z - Θ\|_F^2$ (``A nonlinear matrix decomposition for mining the zeros of sparse data'', SIAM J.\ Math.\ Data Sci., 2022). Our first contribution is to show that the two formulations may yield different low-rank solutions $Θ$. We then consider a reparametrization of the Latent-RMD, called 3B-RMD, in which $Θ$ is substituted by a low-rank product $WH$, where $W$ has $r$ columns and $H$ has $r$ rows. Our second contribution is to prove the convergence of a block coordinate descent (BCD) approach applied to 3B-RMD. Our third contribution is a novel extrapolated variant of BCD, dubbed eBCD, which we prove is also convergent under mild assumptions. We illustrate the significant acceleration effect of eBCD compared to eBCD, and also show that eBCD performs well against the state of the art on synthetic and real-world data sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。