Pivot-safe discrete LU initialization
Implementation & benchmark of arXiv:2608.08998 — LU Factorization of Discrete Random Matrices
Source paper: LU Factorization of Discrete Random Matrices arXiv:2608.08998 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Initialize an invertible neural linear layer from a bounded discrete random matrix only after checking that every leading principal submatrix is nonsingular and that its LU growth factor is below a prescribed threshold. This replaces blind random initialization with a cheap resampling rule designed to prevent zero pivots and excessive finite-precision amplification in reversible or flow-based networks.
Formulas
Mathematical statement
The paper defines a matrix A as strongly non-singular when every leading principal submatrix A_{1:k,1:k}, for k=1,...,n, is nonsingular; this is equivalent to the existence of an LU factorization A=LU without row or column permutations, where L is lower unitriangular and U is upper triangular. Its stability measure is the growth factor \mathrm{growth}(A)=\max\{\|L\|_{\max},\|U\|_{\max}/\|A\|_{\max}\}, with \|B\|_{\max}=\max_{i,j}|B_{ij}|. For an iid discrete random matrix M_n(\xi), the entries \xi are sampled from a finite-support random variable with \|\xi\|_\infty<1, and the paper establishes a constant-probability event of strong nonsingularity together with growth bounded by n^{5/2+\delta} for any fixed \delta>0. The transfer uses the constructive event test directly: sample a bounded discrete matrix, compute its unpivoted LU factorization, reject it if any pivot is zero or if the measured growth exceeds a threshold. The theorem supplies the rationale for expecting non-negligible acceptance probability; the exact acceptance rate and finite-precision behavior must be measured empirically.
Implementation notes
Integrate this at initialization of an invertible linear layer, coupling layer, reversible MLP block, or normalizing-flow transformation whose weight is represented as an LU factorization. Use matrix dimension n small enough for an exact startup check; for larger blocks, apply the procedure independently to block-diagonal or grouped channel matrices. Pseudocode: (1) choose a finite support S, for example S={-1,0,+1} or S={-a,+a}, with a<1, and a sampling distribution p over S; (2) repeat up to R times: sample A[i,j] independently from p, compute unpivoted LU(A) in float64, record each pivot U[k,k], and reject if any pivot is exactly zero or |U[k,k]| is below a numerical threshold epsilon_pivot; (3) compute g=max(max_abs(L), max_abs(U)/max_abs(A)); reject if g>g_max, such as n^(5/2+delta) or a tighter engineering limit; (4) accept A and store L and U using the network's usual parameterization, often storing log|diag(U)| separately and optionally renormalizing A by a scalar; (5) train the layer normally, but log the same growth metric every K optimizer steps. At each step, the zero-pivot condition is computed by the LU routine, while growth is estimated from the current factors; the probability lower bound and n^(5/2+delta) scaling come from the paper, but the constants c_{xi,delta}, epsilon_pivot, and useful g_max are empirical. Start with a 4-layer RealNVP or reversible MLP on CIFAR-10, using 32- or 64-dimensional channel blocks. Compare Gaussian LU initialization, standard random orthogonal initialization, and discrete-resampled LU at equal parameter count. Measure failed initializations, log-determinant variance, forward/inverse reconstruction error, gradient norm spikes, and validation likelihood. The expected signal is fewer unstable or unusable initializations, lower early-training gradient amplification, and reduced inverse reconstruction error at equal training compute.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.