The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank

Giovanni Seraghiti, Arnaud Vandaele, Nicolas Gillis

The ReLU Matrix Decomposition (RMD) approximates a sparse, nonnegative m-by-n matrix X by max(0, WH), where W is an m-by-r matrix, H is an r-by-n matrix, and r is the rank of the d…