提出新型矩阵复杂度度量spiky rank，连接组合与代数问题。
Spiky Rank and Its Applications to Rigidity and Circuits
- 用对角块为秩一矩阵的分块结构定义新秩
- 大spiky rank蕴含高刚性，可推导神经网络下界
- 适用于随机矩阵、汉明距离等具体构造
我们引入spiky rank这一新的矩阵参数，通过结合块状结构的组合特性与线性代数的灵活性，拓展了blocky rank。spiky矩阵是分块结构，其对角块为任意秩一矩阵，spiky rank是将其表示为若干此类矩阵之和所需的最少数量。该度量将blocky rank推广至实数矩阵，对兼具组合与代数特征的问题更具鲁棒性。我们提出spiky rank作为良态的矩阵复杂度度量，并通过应用展示其潜力：大spiky rank蕴含高矩阵刚性，且其下界可导出深度2 ReLU电路的下界（神经网络基本单元）。技术上，我们建立了随机矩阵的紧界，并发展了显式下界框架，应用于汉明距离矩阵与谱膨胀图。最后，我们将spiky rank与blocky rank、稀疏性及γ₂-范数等其他矩阵参数关联。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。