Spiky Rank and Its Applications to Rigidity and Circuits

Lianna Hambardzumyan; Konstantin Myasnikov; Artur Riazanov; Morgan Shirley; Adi Shraibman

cs.CCFeb 26, 2026

Spiky Rank and Its Applications to Rigidity and Circuits

Authors: Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman

Organizations: The University of Copenhagen, Denmark. · EPFL, Switzerland. · Lund University, Sweden. · School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel

Abstract

We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix is block-structured with diagonal blocks that are arbitrary rank-one matrices, and the spiky rank of a matrix is the minimum number of such matrices required to express it as a sum. This measure extends blocky rank to real matrices and is more robust for problems with both combinatorial and algebraic character. Our conceptual contribution is as follows: we propose spiky rank as a well-behaved candidate matrix complexity measure and demonstrate its potential through applications. We show that large spiky rank implies high matrix rigidity, and that spiky rank lower bounds yield lower bounds for depth-2 ReLU circuits, the basic building blocks of neural networks. On the technical side, we establish tight bounds for random matrices and develop a framework for explicit lower bounds, applying it to Hamming distance matrices and spectral expanders. Finally, we relate spiky rank to other matrix parameters, including blocky rank, sparsity, and the $γ_2$ -norm.

Figures & tables

Panel of Figure 1 — Figure 1: A spiky matrix is the entrywise product of a blocky matrix and a rank-one matrix.

I_{n}=\begin{bmatrix}1&0&0&\cdots&0\\ 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1\end{bmatrix}\qquad D_{n}=\begin{bmatrix}1&0&0&\cdots&0\\ 0&2&0&\cdots&0\\ 0&0&3&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&n\end{bmatrix}

Figure 2: The identity matrix

I_{n}

(left) and the diagonal matrix

D_{n}

(right).

Panel of Figure 3 — Figure 3: The picture illustrates the upper and lower bounds for spiky rank: above the scale there are known lower bounds and upper bounds . Below the scale are consequences of the corresponding lower bounds. The dashed part of the scale represents the state of the art of explicit lower bounds. Here $N$ is always the size of the matrix, so for $\mathrm{HD}_{1}^{n}$ , $\textsc{Disj}_{n}$ , and $\mathrm{IP}_{n}$ , $N=2^{n}$ .

Panel of Figure 5 — Figure 5: The picture illustrates the process for $v=(1100)$ , so $P=\{1,2\}$ and $Z=\{3,4\}$ . Here the green matrices illustrate $R_{1}$ and $R_{2}$ , the red matrices are $R_{3}$ and $R_{4}$ , the hatched area in the right square is the support of the matrix $M{\uparrow}v$ .

N_{j}\;=\;\begin{pmatrix}1_{k\times\ell}&*\\ *&N_{j+1}\end{pmatrix}

Algorithm 1 Extracting a Sequence of Submatrices

Circuit Complexity

See all 13 papers

Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness
Mar 5, 2026Baekrok Shin, Chulhee YunImplicit Bias Neural Network Training Dynamics
Kim Jaechul Graduate School of AI, KAIST
Dimension-Free Rank Lifting from Random Hyperplane Arrangements
Sep 30, 2026Luca Becchetti, Matteo Russo, Ruben SkorupinskiNeural Network Initialization
Sapienza University of Rome, Italy · EPFL, Switzerland
Neural Learning of Fast Matrix Multiplication Algorithms: A StrassenNet Approach
Feb 25, 2026Paolo Andreini, Alessandra Bernardi, Monica Bianchini +4Tensor Decomposition Automated Algorithm Discovery

Mar 5, 2026J/K move · Enter open · S save

Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness

Baekrok Shin, Chulhee Yun

Kim Jaechul Graduate School of AI, KAIST

Implicit Bias Neural Network Training Dynamics Matrix Completion Deep Linear Networks Low-Rank Matrix Decomposition Loss of Plasticity

Open paper AskPDF arXiv

We study matrix completion via deep matrix factorization (a.k.a. deep linear neural networks) as a simplified testbed to examine how network depth influences training dynamics. Despite the simplicity and importance of the problem, prior theory largely focuses on shallow (depth-2) models and does not fully explain the implicit low-rank bias observed in deeper networks. We identify coupled dynamics as a key mechanism behind this bias and show that it intensifies with increasing depth. Focusing on gradient flow under block-diagonal observations, we prove: (a) networks of depth

\geq 3

exhibit coupling unless initialized diagonally, and (b) convergence to rank-1 occurs if and only if the dynamics is coupled -- resolving an open question by Menon (2024) for a family of initializations. We also revisit the loss of plasticity phenomenon in matrix completion (Kleinman et al., 2024), where pre-training on few observations and resuming with more degrades performance. We show that deep models avoid plasticity loss due to their low-rank bias, whereas depth-2 networks pre-trained under decoupled dynamics fail to converge to low-rank, even when resumed training (with additional data) satisfies the coupling condition -- shedding light on the mechanism behind this phenomenon.

Abstract

Circuit Complexity

Explore similar work

Implicit Bias and Loss of Plasticity in Matrix Completion: Depth Promotes Low-Rankness

Dimension-Free Rank Lifting from Random Hyperplane Arrangements

Neural Learning of Fast Matrix Multiplication Algorithms: A StrassenNet Approach