The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank
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),…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.22255
curl -X POST /api/v1/records/arxiv/2610.22255/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22255/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'