Accelerated Algorithms For Nonlinear Matrix Decomposition With The Relu Function

In this paper, we study the following nonlinear matrix decomposition (NMD) problem: given a sparse nonnegative matrix X, find a low-rank matrix $\Theta$ such that $X\approx f(\Theta)$, where f is an element-wise nonlinear function. We focus on the case where $f(\cdot)=\max(0,\cdot)$, the rectified linear unit (ReLU) nonlinear activation. We refer to the corresponding problem as ReLU-NMD. We first provide a brief overview of the existing approaches that were developed to tackle ReLU-NMD. Then we introduce two new algorithms: (1) aggressive accelerated NMD (A-NMD) which uses an adaptive Nesterov extrapolation to accelerate an existing algorithm, and (2) three-block NMD (3B-NMD) which parametrizes $\Theta=WH$ and leads to a significant reduction in the computational cost. We also propose an effective initialization strategy based on the nuclear norm as a proxy for the rank function. We illustrate the effectiveness of the proposed algorithms on synthetic and real-world data sets.