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

Abstract. ReLU matrix decomposition (RMD) is the following problem: given a sparse, nonnegative matrix [Formula: see text] and a factorization rank [Formula: see text], identify a rank-[Formula: see text] matrix [Formula: see text] such that [Formula: see text]. 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, [Formula: see text]. 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 [Formula: see text] is introduced and satisfies [Formula: see text] while minimizing [Formula: see text] [ 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 [Formula: see text]. We then consider a reparametrization of the Latent-RMD, called 3B-RMD, in which [Formula: see text] is substituted by a low-rank product [Formula: see text], where [Formula: see text] has [Formula: see text] columns and [Formula: see text] has [Formula: see text] rows. Our second contribution is to prove the convergence of a block coordinate descent approach applied to 3B-RMD.