Finite graph shapes determine sharp growth of random matrix norms
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Data Structures and Algorithms
Summary
Predicting the size of certain large random matrices is hard because their entries depend on shared random values linked by graphs. This paper shows exactly how the shape of these graphs controls the expected size of the largest value in these matrices. The authors provide a precise formula that accounts for both polynomial and logarithmic factors based on the graph’s structure, resolving previous uncertainties. They also extend their results to more general settings and apply them to problems in statistics and tensor networks.
What this means in practice
- •For statistical machine learning engineers: Determine precise feasibility thresholds in degree-four clique sum-of-squares algorithms for community detection in networks.
- •For data scientists working with tensor methods: Estimate sharp deviation thresholds and expected largest eigenvalues in large Gaussian random tensor networks for improved dimensionality reduction.
A theory result. No direct application yet.
Authors
Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao
Abstract
Graph matrices encode dependencies in random matrices built from shared random variables and arise in spectral algorithms, sum-of-squares (SoS), and high-dimensional statistics. We determine how finite graph structure controls their sharp spectral growth. For every fixed simple graph shape in the dense Rademacher model, including overlapping or empty matrix boundaries, we prove $\mathbb E\|M_α\|=Θ_α(n^{(v+h-s)/2}(\log n)^{a_*/2})$, where $v$ counts vertices, $h$ isolated summation vertices, $s$ the minimum boundary-separator size, and $a_*$ maximizes an active-component count over minimum separators. Thus two finite cut optimizations determine both the polynomial and logarithmic exponents. The formula closes the polylogarithmic gap in separator bounds, and an infinite family with identical coarse parameters but different norms shows that the logarithmic exponent records genuinely new structure. The proof controls all defect layers in growing trace moments by converting label loss into separator excess; conditional flattening and synchronized fluctuations yield matching lower bounds. We extend the analysis to specified independent-factor chaoses, local weights, unequal dimensions, bounded asymmetric noise, Gaussian inputs, and fixed-degree Hermite inputs. Applications include degree-four clique SoS feasibility for $9\le k\le c\sqrt n$ without an asymptotic logarithmic loss, and Gaussian random tensor networks: deviation thresholds, sharp expected scales, entropy estimates, and, for connected loopless equal-dimensional networks, convergence of the rescaled largest output eigenvalue to the exact right edge of the limiting law. These results connect finite structure to sharp growth scales, and additional algebraic and spectral structure to full feasibility and exact limiting constants.