Spiky Rank and Its Applications to Rigidity and Circuits
This work introduces a new matrix complexity measure that could be foundational for understanding the rigidity of matrices and the complexity of neural networks.
This paper introduces 'spiky rank', a new matrix parameter that extends blocky rank to real matrices, combining combinatorial structure with linear-algebraic flexibility. The authors demonstrate its utility by showing that high spiky rank implies high matrix rigidity and provides lower bounds for depth-2 ReLU circuits.
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.