The Spectral Norm of Random Lifts of Matrices

We study the spectral norm of random lifts of matrices. Given an $n\times n$ symmetric matrix $A$, and a centered distribution $\pi$ on $k\times k\ (k\ge 2)$symmetricmatriceswithspectralnormatmost$1$, let the matrix random lift $A^{(k,\pi )}$ be the random symmetric $kn\times kn$ matrix $(A_{ij}{X}_{ij}{)}_{1\le i<j\le n}$, where $X_{ij}$ are independent samples from $\pi$. We prove that $$\mathbb{E}\mathrm{\parallel }{A}^{(k,\pi )}\mathrm{\parallel }\lesssim \underset{i}{\max }\sqrt{\sum _j{A}_{ij}^2}+\underset{ij}{\max }\mathrm{\mid }{A}_{ij}\mathrm{\mid }\sqrt{\log (kn)}\mathrm{.}$$ This result can be viewed as an extension of existing spectral bounds on random matrices with independent entries, providing further instances where the multiplicative $\sqrt{\log n}$ factor in the Non-Commutative Khintchine inequality can be removed. As a direct application of our result, we prove an upper bound of $2(1+ϵ)\sqrt{\mathrm{\Delta }}+O(\sqrt{\log (kn)})$ on the new eigenvalues for random $k$-lifts of a fixed $G=(V,E)$ with $\mathrm{\mid }V\mathrm{\mid }=n$ and maximum degree $\mathrm{\Delta }$, compared to the previous result of $O(\sqrt{\mathrm{\Delta }\log (kn)})$ by Oliveira and the recent breakthrough by Bordenave and Collins which gives $2\sqrt{\mathrm{\Delta }-1}+o(1)$ as $k\to \mathrm{\infty }$ for $\mathrm{\Delta }$-regular graph $G$.