Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
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 𝔼|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≤ k≤ c√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.
Related
- Invertibility of structured perturbations of singular matrices over unital rings
- A sharp weighted commutator inequality for rank-one matrices
- Quantitative spectral stability and sharp Fourier estimates for periodic CMV matrices with decaying perturbations
- Sharp singularity asymptotics for discrete random matrices
- Estimating Hierarchically Rank Structured Covariance Matrices
BibTeX
@misc{xu2026sharp,
title = {{Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses}},
author = {Huibo Xu and Shi Fu and Youming Qiao and Dacheng Tao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14266},
eprint = {2609.14266},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14266},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
AU - Huibo Xu
AU - Shi Fu
AU - Youming Qiao
AU - Dacheng Tao
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14266
UR - https://arxiv.org/abs/2609.14266
AB - 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 𝔼|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≤ k≤ c√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.
ER -