Metraipolis › archive › dc_4383086211e5
The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank — arXiv:2610.22255
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.22255
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:33:06.196Z
- SHA-256 of the archived text
d13864b93775ec413dcb5afc44ac3d1008610941d4d49d65634dce79998936e2- Stable URL of this page
https://metraipolis.com/documento/dc_4383086211e5
How to cite
The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank — arXiv:2610.22255 — arXiv (en), https://arxiv.org/abs/2610.22255 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4383086211e5 (Metraipolis archive dc_4383086211e5, sha256 d13864b93775ec413dcb5afc44ac3d1008610941d4d49d65634dce79998936e2)
BibTeX
@misc{dc4383086211e5,
title = {The ReLU Matrix Decomposition: NP-Hardness, Ill-Posedness, and ReLU-Rank — arXiv:2610.22255},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.22255},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4383086211e5; sha256 d13864b93775ec413dcb5afc44ac3d1008610941d4d49d65634dce79998936e2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22255. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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), and define the ReLU-rank of X as the smallest r for which such a decomposition exists. We interpret exact RMDs geometrically as configurations of points and hyperplanes in an r-dimensional space, associated with the rows of W and the columns of H, respectively. Building on this interpretation, we derive upper bounds on the ReLU-rank of diagonal, block-diagonal, and block-sparse matrices and, under an additional structural assumption, improve the best known bound for block-diagonal matrices. Finally, we propose two formulations of exact RMD as feasibility problems: a nonconvex quadratically constrained program, which can be tackled by global solvers such as Gurobi, and a formulation based on the latent model of Saul, (``A nonlinear matrix decomposition for mining the zeros of sparse data', SIMODS, 2022), which we tackle using alternating projections for which we establish local convergence together with asymptotic convergence rates. We compare these two approaches on some numerical examples. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.NA, nuovi lavori del giorno). Categorie arXiv: Numerical Analysis (math.NA). Pagina del lavoro: https://arxiv.org/abs/2610.22255 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T08:50:32.714Z dalla pagina https://arxiv.org/list/math.NA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).