Positive Bidiagonal Diffusion Layer
Implementation & benchmark of arXiv:2608.00788 — Positive Bidiagonal Factorizations for Banded Markov Processes
Source paper: Positive Bidiagonal Factorizations for Banded Markov Processes arXiv:2608.00788 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a learned nonnegative banded transition matrix by an ordered product of learnable stochastic bidiagonal factors. Each factor performs one local left or right transport step, so a product of p lower and q upper factors creates an effective bandwidth of p+q while retaining nonnegative entries, row sums equal to one, and a highly structured propagation kernel.
Formulas
Mathematical statement
The central construction is the ordered positive bidiagonal factorization $$T=L_{1}\cdots L_{p}U_{q}\cdots U_{1},$$ where T is a semi-infinite matrix with p subdiagonals and q superdiagonals, and every L_k and U_k is bidiagonal with positive nontrivial entries. The paper states that a product of totally nonnegative bidiagonal factors is totally nonnegative; under strict band assumptions it is totally positive. For a finite neural layer with states indexed by i=0,\ldots,n-1, use a lower stochastic bidiagonal factor L_k and upper stochastic bidiagonal factor U_k defined by $$ (L_k)_{i,i}=1-a_{k,i},\quad (L_k)_{i,i-1}=a_{k,i},\qquad (U_k)_{i,i}=1-b_{k,i},\quad (U_k)_{i,i+1}=b_{k,i}, $$ with a_{k,i},b_{k,i}\in[0,1]. Boundary moves are removed or reflected so each row sums to one. Thus L_k\mathbf{1}=U_k\mathbf{1}=\mathbf{1}, and consequently T\mathbf{1}=\mathbf{1}; all entries of T are nonnegative. The parameters a_{k,i}, b_{k,i} are local transition probabilities, \mathbf{1} is the all-ones vector, and p,q determine the maximum propagation radius. This transfers the paper's positivity and factor-level Markov interpretation without requiring reversibility or block symmetrization.
Implementation notes
Integrate this as a structured transition layer inside an SSM, graph-neural-network propagation block, or residual diffusion module. The input is a feature matrix X in R^{n x d}, where n is the ordered spatial/state dimension and d is the channel dimension; apply the same transition to every channel. Store unconstrained logits alpha[k,i] and beta[k,i], and set a[k,i]=sigmoid(alpha[k,i]) and b[k,i]=sigmoid(beta[k,i]). For each forward pass, execute the factors sequentially rather than forming T: initialize H=X; for k=1,...,p, compute H_i <- (1-a[k,i])H_i + a[k,i]H_{i-1}; then for k=1,...,q in the prescribed reverse product order, compute H_i <- (1-b[k,i])H_i + b[k,i]H_{i+1}. Use zero, reflecting, or periodic boundary handling, but keep boundary rows normalized. Optionally add a residual gate y=(1-g)X+gH with g=sigmoid(gamma). Each factor costs O(nd), so the full layer costs O((p+q)nd), versus O(n(p+q) d) for explicitly applying a band matrix and O(n^2d) for an unrestricted matrix. The mathematical quantities computed exactly are the bidiagonal updates, nonnegativity, row-stochasticity, and effective bandwidth; no spectral estimator is required. Initialize alpha and beta near logit(0.25) so propagation is initially local and stable. First test on length-256 copy/reconstruction and sequential-MNIST tasks using a linear SSM or 1D residual baseline with an unconstrained banded transition of the same nominal bandwidth. Compare validation accuracy, gradient norm growth, parameter count, and wall-clock time. Success means no exploding activations over 100+ recurrent steps, lower memory than the dense baseline, and equal or better accuracy at matched parameter count; a stronger result is faster loss descent at equal FLOPs.
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.