On $r$-to-$p$ norms of random matrices with nonnegative entries: Asymptotic normality and $\ell_\infty$-bounds for the maximizer

Souvik Dhara, Debankur Mukherjee, Kavita Ramanan

Introduction

In the study of random matrices, the spectral norm (the $2 \to 2$ operator norm) has long been a focal point due to its fundamental role in statistics, physics, and signal processing. However, many modern applications—ranging from data clustering and matrix condition number estimation to the design of oblivious routing schemes—require a broader understanding of how matrices act on different geometry spaces. This is captured by the $r$-to-$p$ operator norm, defined for an $n \times n$ matrix $A_n$ as: $$\|A_n\|_{r\to p}:= \sup_{\mathbf{x}\in\mathbb{R}^n:\|\mathbf{x} \|_r\leq 1 } \|A_n\mathbf{x} \|_p\quad\text{for}\quad r,p\geq 1.$$

While the behavior of the $2 \to 2$ norm is well-characterized by classical spectral theory, general $r \to p$ norms are notoriously difficult to analyze. In fact, computing these norms for arbitrary matrices is known to be NP-hard. This research extends the frontiers of random matrix theory (RMT) by establishing the asymptotic distribution and maximizer properties of these norms for a broad class of symmetric random matrices with nonnegative entries.

Theoretical Framework and Models

The study focuses on symmetric matrices $A_n$ where entries are nonnegative. This nonnegativity is a crucial structural property that allows for the application of Perron-Frobenius-like arguments. The authors evaluate their theorems across several key random matrix models:

  • Erdős-Rényi Graphs: Adjacency matrices where an edge exists between any two vertices with probability $\mu_n$.
  • Sub-Gaussian Matrices: Matrices with independent and identically distributed (i.i.d.) nonnegative entries characterized by "light tails."
  • Inhomogeneous Variance Profiles: Matrices where entries may have varying variances, providing a model for more complex, non-uniform network structures.

The analysis specifically targets the regime $1 < p \leq r < \infty$, where the norm behaves predictably relative to the matrix's mean structure.

Methodology: Beyond Eigenvalues

Because traditional spectral methods are inherently tied to the $p=r=2$ case, the authors developed a new analytical toolkit to handle the nonlinear nature of general $r \to p$ norms.

1. Nonlinear Power Method

The authors utilize a nonlinear generalization of the standard power iteration, known as Boyd’s power method. This approach allows for the approximation of the maximizing vector $\mathbf{v}_n$ even when the underlying geometry is non-Euclidean.

2. Perturbation and Taylor Expansion

By treating the random matrix $A_n$ as a perturbation of its expectation $\mathbb{E}[A_n]$, the authors perform a sophisticated Taylor expansion of the norm functional. A key discovery in this process is the "Hessian shift"—a non-trivial $O(1)$ correction to the mean of the norm, denoted as $\alpha_n(p,r)$, which arises from the second-order curvature of the norm functional.

3. $\ell_\infty$ Stability

A significant portion of the work is dedicated to proving the "rigidity" of the maximizing vector. The authors show that the vector $\mathbf{v}_n$ that achieves the supremum is remarkably stable, staying close to the uniform vector $n^{-1/r}\mathbf{1}$ in the $\ell_\infty$ (entry-wise) sense, even in the presence of random noise.

Key Results

The research yields three primary contributions to the field of random matrix theory:

Asymptotic Normality (CLT)

The paper generalizes the seminal 1981 result by Füredi and Komlós. They prove that for large $n$, the centered and scaled norm follows a Gaussian distribution: $$\frac{1}{\sigma_n}(\| A_n \|_{r\to p} - \alpha_n(p,r)) \xrightarrow{d} \mathcal{N}(0, 2)$$ Remarkably, the asymptotic variance of 2 is universal; it does not depend on the specific values of $r$ and $p$, provided the scaling is appropriate.

Maximizer Bounds

The authors establish tight bounds on the distance between the empirical maximizer $\mathbf{v}_n$ and the uniform vector. With high probability, this distance is bounded by: $$O\left(n^{-1/r} \sqrt{\frac{\log n}{n \mu_n}}\right)$$ This result confirms that for nonnegative random matrices, the "stretching" effect is distributed almost uniformly across all coordinates.

The Grothendieck Problem

The findings provide a direct corollary for the $\ell_p$ Grothendieck problem, a classic challenge in combinatorial optimization. The results show that for nonnegative matrices, the solution to this problem is asymptotically normal.

Discussion and Future Directions

While this work provides a comprehensive picture for the $p \leq r$ regime with nonnegative entries, several avenues remain open. The nonnegativity constraint is central to the current proof technique; matrices with negative entries would likely exhibit different behaviors and require new methods.

Furthermore, the "hypercontractive" regime where $p > r$ remains a frontier. In this case, the maximizing vector is expected to become "sparse"—concentrating its mass on a few entries rather than spreading it uniformly. Extending these asymptotic normality results to non-symmetric or rectangular matrices also represents a natural progression for this line of research.

Summary updated

Abstract

For an $n\times n$ matrix $A_n$, the $r\to p$ operator norm is defined as $$\|A_n\|_{r\to p}:= \sup_{\mathbf{x}\in\mathbb{R}^n:\|\mathbf{x} \|_r\leq 1 } \|A_n\mathbf{x} \|_p\quad\text{for}\quad r,p\geq 1.$$ For different choices of $r$ and $p$, this norm corresponds to key quantities that arise in diverse applications including matrix condition number estimation, clustering of data, and construction of oblivious routing schemes in transportation networks. This article considers $r\to p$ norms of symmetric random matrices with nonnegative entries, including adjacency matrices of Erdős-Rényi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For $1
BibTeX
@article{dhara2024r,
  author = {Souvik Dhara and Debankur Mukherjee and Kavita Ramanan},
  title = {{On $r$-to-$p$ norms of random matrices with nonnegative entries: Asymptotic normality and $\textbackslash\{\}ell\_\textbackslash\{\}infty$-bounds for the maximizer}},
  journal = {The Annals of Applied Probability},
  year = {2024},
  doi = {10.1214/24-aap2061},
}
Figure