{
  "id": "2006.06505",
  "version": "v1",
  "published": "2020-06-11T15:21:06.000Z",
  "updated": "2020-06-11T15:21:06.000Z",
  "title": "The Spectral Norm of Random Lifts of Matrices",
  "authors": [
    "Afonso S. Bandeira",
    "Yunzi Ding"
  ],
  "comment": "11 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study the spectral norm of matrix random lifts $A^{\\otimes (k,\\pi)}$ for a given $n\\times n$ matrix $A$ and $k\\ge 2$, which is a random symmetric $kn\\times kn$ matrix whose $k\\times k$ blocks are obtained by multiplying $A_{ij}$ by a $k\\times k$ matrix drawn independently from a distribution $\\pi$ supported on $k\\times k$ matrices with spectral norm at most $1$. Assuming that $\\mathbb{E}_\\pi X = 0$, we prove that \\[\\mathbb{E} \\|A^{\\otimes (k,\\pi)}\\|\\lesssim \\max_{i}\\sqrt{\\sum_j A_{ij}^2}+\\max_{ij}|A_{ij}|\\sqrt{\\log (kn)}.\\] 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. We also show an application on random $k$-lifts of graphs (each vertex of the graph is replaced with $k$ vertices, and each edge is replaced with a random bipartite matching between the two sets of $k$ vertices each). We prove an upper bound of $O(\\sqrt{\\Delta}+\\sqrt{\\log(kn)})$ on the new eigenvalues for random $k$-lifts of a fixed $G = (V,E)$ with $|V| = n$ and maximum degree $\\Delta$, which improves the previous result of $O(\\sqrt{\\Delta\\log(kn)})$ by Oliveira in [Oli09].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-06-11T15:21:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spectral norm",
      "matrix random lifts",
      "matrix drawn",
      "existing spectral bounds",
      "random matrices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}