An Extrapolated and Provably Convergent Algorithm for Nonlinear Matrix Decomposition with the ReLU Function

ReLU matrix decomposition (RMD) is the following problem: given a sparse, nonnegative matrix 𝑋 and a factorization rank 𝑟, identify a rank-𝑟 matrix Θ such that 𝑋 ≈max⁡(0,Θ). RMD is a particular instance of nonlinear matrix decomposition 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, ‖𝑋−max⁡(0,Θ)‖^2_𝐹. The corresponding optimization problem, least squares RMD, is nondifferentiable and highly nonconvex. This motivated Saul to propose an alternative model, dubbed Latent-RMD, where a latent variable 𝑍 is introduced and satisfies max⁡(0,𝑍) =𝑋 while minimizing ‖𝑍−Θ‖^2_𝐹 [SIAM J. Math. Data Sci., 4 (2022), pp. 431–463]. 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 𝑊⁢𝐻, where 𝑊 has 𝑟 columns and 𝐻 has 𝑟 rows. Our second contribution is to prove the convergence of a block coordinate descent approach applied to 3B-RMD.