{"id":"arxiv/2610.22255","url":"https://arxiv.org/abs/2610.22255","tags":["math.NA"],"score":0,"title":"The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank","domain":"math.NA","source":"arxiv","authors":["Giovanni Seraghiti","Arnaud Vandaele","Nicolas Gillis"],"reviews":0,"subject":"math.NA","summary":"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 decomposition. The most common formulation, referred to as Fro-RMD, minimizes the Frobenius norm of X - max(0, WH) over W and H. We prove that Fro-RMD is NP-hard, even for binary matrices and r = 1; to the best of our knowledge, this is the first complexity result for RMD. We also show that Fro-RMD is ill-posed, in the sense that its infimum may not be attained. We then turn to exact RMD, that is, X = max(0, WH),…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}