PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Giovanni Seraghiti, Arnaud Vandaele, Nicolas Gillis

arXiv:2610.22255v1math.NAcs.NA

TL;DR

Fro-RMD’s complexity and well-posedness had not been studied, while exact RMD also lacked a developed geometric interpretation. The paper proves hardness and ill-posedness results, develops ReLU-rank bounds, and proposes feasibility formulations for exact RMD. It establishes local convergence for Naive-RMD under an exact-decomposition assumption.

  • Problem

    Fro-RMD’s computational complexity and well-posedness had not been studied, and exact RMD had received comparatively little interpretive attention.

    Source: §1 · p. 2

  • Method

    The paper interprets exact RMD geometrically, derives ReLU-rank bounds, and formulates exact RMD as two feasibility problems, one addressed by Naive-RMD.

    Source: §1 · pp. 2–3

  • Results

    The paper proves Fro-RMD is NP-hard and ill-posed, derives ReLU-rank bounds for structured matrices, and establishes local convergence for Naive-RMD when an exact decomposition exists.

    Source: §5 · p. 25

  • Takeaways & Limitations

    The work provides rank bounds for special matrix classes and a local convergence guarantee for Naive-RMD applied to exact RMD.

    Source: §5 · p. 25

    Unbounded algorithm iterates appear to arise only in degenerate cases, and norm penalties or bounded entries can address the issue.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames ReLU Matrix Decomposition (RMD) as a model for sparse, nonnegative data and identifies open questions about Fro-RMD's complexity and well-posedness. It introduces exact RMD's ReLU-rank and geometric viewpoint, then previews rank bounds and feasibility formulations.

1 Introduction

  • The paper addresses the previously unstudied complexity and well-posedness of Fro-RMD, a nonsmooth, nonconvex approximation formulation.Its difficulty motivates the paper's focus on both approximate and exact RMD.Source: §1 · p. 2
  • ReLU-rank(X) is the smallest rank r for which X = max(0, Θ) for some rank-r matrix Θ.The paper considers the smallest rank giving an exact RMD for a nonnegative, sparse matrix.Source: §1 · p. 2
  • A geometric representation of exact RMD supports improved ReLU-rank bounds for block-diagonal matrices and explicit upper bounds for general block-structured sparse matrices.The introduction positions this as extending bounds previously studied by Saul et al. [21].Source: §1 · p. 2
  • The paper reformulates exact RMD as a ReLU-QCP and as a feasibility problem addressed by Naive-RMD, establishing local convergence for the latter when an exact decomposition exists.The authors also compare the two approaches on numerical examples.Source: §1 · p. 3

2 Ill-posedness and complexity of Fro-RMD

This section establishes ill-posedness for Fro-RMD and proves NP-hardness for rank-1 Fro-RMD, even on binary input matrices.

2.1 Ill-posedness

  • For a 3×3 example, ReLU-rank(X)=3 while the rank-2 Fro-RMD infimum is zero and is not attained.Attainment would imply an exact RMD of rank at most 2, which the example rules out.Source: §2.1 · pp. 3–4
  • Fro-RMD sublevel sets are noncompact, so iterates can become unbounded while the objective values converge.The authors say this appears to arise only in degenerate cases and note that norm penalties or bounded entries can address it.Source: §2.1 · p. 4

2.2 Complexity

  • Rank-1 Fro-RMD is NP-hard even when the input matrix is binary, by a polynomial-time reduction from CUT-NORM.The constructed instance is a yes-instance of R1-RMD exactly when the original CUT-NORM instance is a yes-instance.Source: §2.2 · p. 4

3 Exact RMD: Geometry and ReLU-rank

This section studies exact RMD through its minimum-rank factorization, ReLU-rank, and geometric sign decompositions. It derives ReLU-rank upper bounds for diagonal, block-diagonal, Kronecker-product, and block-sparse matrices, including shared factors for blocks in a block-diagonal grouping.

3.1 Sign decomposition: geometric interpretation and bounds

  • In affine sign decomposition, a sign vector is realizable exactly when the convex hulls of its positive and negative point sets are disjoint.For a sign matrix, rows of W represent points and columns of H identify separating hyperplanes.Source: §3.1 · pp. 10–11
  • For block-diagonal sign matrices with equal-sized blocks, affine sign decompositions of rank at most k per block yield a whole-matrix rank bound of k + 1, independent of block count.The paper uses this sign-decomposition result as motivation for extending the theory to ReLU.Source: §3.1 · p. 11

3.2 ReLU nonlinearity: geometric interpretation and bounds on the ReLU-rank

  • The sign-rank and positive-submatrix lower bounds are incomparable: positive full-rank matrices can have sign-rank 1, while binary matrices can have large sign-rank despite rank-one positive submatrices.For positive full-rank X, ReLU-rank(X) = min(m, n); for binary X, every positive submatrix has rank one.Source: §3.2 · pp. 11–12
  • For a nonconstant nonnegative vector, affine ReLU-realizability requires a hyperplane separating points for positive and zero entries, with signed distances matching positive values.This extends the points-hyperplanes interpretation of sign decomposition, but imposes a relationship between positive entries and distances.Source: §3.2 · pp. 12–13
  • Nonnegative diagonal matrices admit an exact rank-3 RMD in affine form.The bound is derived by extending the sign-rank result for diagonal sign matrices.Source: §3.2 · p. 13
  • Block-diagonal matrices with blocks admitting affine RMDs of ranks r_k ≥ 2 have an exact affine RMD of rank at most 1 + max_k r_k, improving the known bound.The stated bound is at most 1 + min(m̄, n̄), compared with the prior bound 3 min(m̄, n̄).Source: §3.2 · p. 14
  • ReLU-rank(B⊗A) admits an affine RMD of rank at most rA + rB + 1 when B is binary and A and B have ReLU-ranks rA and rB.The bound is additive in the two ReLU-ranks, unlike the general rank bound for a Kronecker product, which is multiplicative.Source: §3.2 · p. 16
  • The passage establishes that ReLU-rank(X) = ReLU-rank(A), because the matrix on the right-hand side has the same ReLU-rank as A, even though X has twice A’s dimensions.A separate bound stated for X is ReLU-rank(X) ≤ ReLU-rank(A) + 1.Source: §3.2 · pp. 17–18
  • For a block-sparse matrix X partitioned into T block-diagonal submatrices, ReLU-rank(X) is at most 1 + ReLU-rank(G) + the sum over groups of the maximum block ReLU-rank in each group.Blocks in each block-diagonal group can share block columns and rows in the decomposition.Source: §3.2 · pp. 18–19

4 Exact RMD as a feasibility problem

The section formulates exact RMD as two feasibility problems: a bounded nonconvex QCP for global solvers and a latent-RMD formulation addressed by alternating projections. It establishes local convergence for Naive-RMD under stated assumptions and compares both approaches numerically.

4.1 First formulation: exact RMD as a QCP

  • The bounded ReLU-QCP encodes exact RMD as a feasibility problem with bounded factors, enabling global solvers such as Gurobi and addressing ill-posedness.The factor bounds make the search space bounded, as required by the solver.Source: §4.1 · p. 20

4.2 Second formulation based on Latent-RMD

  • In the exact case, Fro-RMD and Latent-RMD are equivalent, reducing the latter to finding a matrix in the intersection of the ReLU-consistent set and the rank-at-most-r set.The set enforcing max(0, Z) = X is closed and convex, while the rank-constrained set is closed but nonconvex.Source: §4.2 · p. 21

4.2.1 Naive-RMD and its convergence

  • Naive-RMD is an alternating projection method: its updates project onto the ReLU-consistent set and the set of matrices with rank at most r.The first projection enforces X on positive entries and nonpositive values elsewhere; the second uses a truncated SVD.Source: §4.2.1 · p. 21
  • If the exact feasible intersection contains a matrix of rank exactly r, Naive-RMD converges locally from a neighborhood of that matrix, though its limit need not be the assumed matrix.The theorem states asymptotic convergence rates; the rank condition ensures the projection onto the rank-constrained set is single-valued.Source: §4.2.1 · p. 22

4.3 Numerical experiments

  • The experiments compare Naive-RMD on the latent feasibility problem with Gurobi on the bounded QCP, using relative Frobenius error and solver feasibility tolerances.Naive-RMD stops at a fixed error tolerance or a maximum iteration count; Gurobi uses constraint violations.Source: §4.3 · p. 22

4.3.1 Random low-rank matrices

  • Naive-RMD is significantly faster than Gurobi in 14 of 15 random-instance cases; Gurobi fails eight times at rank 15, while Naive-RMD fails twice overall.The runs use a 300-second time limit; Table 1 reports average times on successful runs.Source: §4.3.1 · p. 23, Table 1 · p. 23

4.3.2 Identity matrix

  • Gurobi finds a rank-3 decomposition of I10 with relative error of order 10^-13, while 1,000 random Naive-RMD starts average 1.76 · 10^-1 and none reaches error below 10^-3.With three or more sign flips from the exact Gurobi solution, Naive-RMD does not converge to an exact solution and final relative error exceeds 10^-2.Source: §4.3.2 · pp. 24–25, Figure 2 · p. 24

5 Conclusion

The paper resolves open questions about approximate and exact ReLU matrix decomposition. It establishes limitations of Fro-RMD and develops ReLU-rank bounds and feasibility formulations for exact RMD.

5 Conclusion

  • The paper proves that Fro-RMD is NP-hard and ill-posed.Fro-RMD is a standard formulation for computing approximate RMDs.Source: §5 · p. 25
  • For exact RMD, the paper introduces ReLU-rank and a points-hyperplanes geometric interpretation, then uses it to bound ReLU-rank for special matrix classes.The bounds concern special classes of matrices.Source: §5 · p. 25
  • The paper proposes two exact-RMD feasibility formulations and establishes local convergence guarantees for Naive-RMD applied to exact RMD.Source: §5 · p. 25

Related papers

Loading 2610.22255v1…