Sharp Bounds on Spectral Norm of a Random Matrix

Singular values of matrices show up in many different places, and studying them has significant importance in math. As per usual, it has a fairly simple definition but requires quite diffficult tools to analyze comprehensively. In this article I aim to demonstrate how would norm of a Gaussian random matrix behave and answer questions such as “How does it’s mean behave?” or “Is it concentrated around it’s mean?”. A crucial assumption employed on the entries of \(A\) is independence. Indeed, the results can be extended easily to subgaussians as well, however stating theorems with gaussians evaporates the annoying constants! Let’s set up some notations, shall we?

Definition. For any matrix \(A \in \mathbb{R}^{n \times m}\) we define spectral norm (i.e. largest singular value) as: \[||A||_{op} = \max_{\substack{u \in S^{n-1} \\ v \in S^{m-1}}}{\langle u,Av \rangle} \]

It is worth mentioning, the reason that I exchanged maximum instead of suprema is merely because suprema of a continuous function will be achieved on a compact set. This norm is a measure of how much a vector can be dialated through the linear transform \(x \mapsto Ax\) in the worst case.

Definition. An unbiased random variable \(X\) is called \(\sigma^2\)-subgaussian if one of the following holds.¹ Moreover, all the statements are equivalent with different constants:

• (Moment Generating Bound) \(\mathbb{E}[e^{tX}] \le e^{\frac{t^2 \sigma^2}{2}}\) for all \(t \in \mathbb{R}\).
• (Tail Bound) \(\mathbf{P}[|X| \ge t] \le 2 e^{-\frac{t^2}{2 \sigma^2}}\) for all \(t \ge 0\).
• (Moment Bound) \(||X||_{L^{p}} = (\mathbb{E}[X^{p}])^{\frac{1}{p}} \le \sigma \sqrt{p}\) for all \(p \ge 1\).
• (Another MGF Bound) \(\mathbb{E}[e^{\frac{X^2}{2 \sigma^2}}] \le 2\)

In a nutshell, this property is roughly saying that the random variable behaves like a normal and it is desirable since it’s basically equivalent to concentration around mean (or median). For fixed vectors \(u \in \mathbf{S}^{n-1}, v \in \mathbf{S}^{m-1}\) one can easily check that \(X_{u,v} = \langle u,Av \rangle\) is also sub-gaussian with the same parameter of entries of \(A\), thus concentrated around it’s mean. However, it’s not clear what can be said about suprema of this collection of random variables which is the quantity of interest.² Note that these random variables are locally correlated, i.e. for a pair \((u^{'},v^{'})\) close to \((u,v)\) we expect \(X_{u,v}\) to be close to \(X_{u^{'},v^{'}}\). More precisely, one can write: \[ |X_{u,v} - X_{u^{'}, v^{'}}| \le |X_{u,v} - X_{u^{'}, v}| + |X_{u^{'},v} - X_{u^{'}, v^{'}}| \le ||A||_{op}(||u-u^{'}|| + ||v-v^{'}||) \] Surprisingly, the inverse is also true meaning if one take two pairs far apart from each other the corrseponding random variables will also be uncorrelated, thus behave as though they were independent since uncorrelatedness is equivalent to independence in gaussian fields. This sort of argument motivated proofs based on \(\epsilon\)-net methods which I do not intend to go through here, however the intuition is very insightful. In order to make this statement more precise one may use the following comparison inequality for gaussian random variables.

Theorem (Sudakov-Fernique Inequality). Suppose \(X,Y \in \mathbb{R}^n\) are two independent centered Gaussian vectors such that \(\mathbb{E}[|X_{i} - X_{j}|^2] \le \mathbb{E}[|Y_{i}-Y_{j}|^{2}]\) for \(\forall i,j \in [n]\). Then: \[ \mathbb{E}[\max_{i \le n}{X_{i}}] \le \mathbb{E}[\max_{i \le n}{Y_{i}}] \] As a special case if we assume that \(X,Y\) has the same variance coordinatewise, then the condition in the theorem verbally translates into \(X\) is more correlated than \(Y\), thus should possess a lower maximum which aligns with intuition.³ In addition, it is easy to extend this to infinite case using a simple truncation and then applying monotone convergence theorem provided that the index set is seperable. I am not going to provide a proof for this theorem here since the ideas overlap with the theorems mentioned below but this theorem has an direct application to upper bounding spectral norm of a matrix. Take \(X_{u,v}\) as defined above and assume entries of matrix \(A\) has standard normal distribution: \[\begin{aligned} \mathbb{E}[|X_{u,v} - X_{u^{'},v^{'}}|^2] &= \mathbb{E}[|\sum_{\substack{i \in [n] \\ j \in [m]}}{(u_{i}v_{j} - u^{'}_{i}v^{'}_{j})A_{i,j}}|^2] = \sum_{\substack{i \in [n] \\ j \in [m]}}{(u_{i}v_{j} - u^{'}_{i}v^{'}_{j})^2} \\ &= \sum_{\substack{i \in [n] \\ j \in [m]}}{(u_{i}v_{j} - u^{'}_{i}v_{j})^2 + (u_{i}^{'}v_{j} - u^{'}_{i}v^{'}_{j})^2 + 2u^{'}_{i}v_{j}(u_{i} - u^{'}_{i})(v_{j} - v^{'}_{j})} \\ &= \sum_{i \in [n]}{ (u_{i} - u^{'}_{i})^2} + \sum_{j \in [m]}{(v_{j} - v^{'}_{j})^2 } + 2\underbrace{\sum_{i \in [n]}{u^{'}_{i}(u_{i} - u^{'}_{i})}}_{\le 0} \underbrace{\sum_{j \in [m]}{v_{j}(v_{j} - v^{'}_{j})}}_{\ge 0} \\ &\le \sum_{i \in [n]}{ (u_{i} - u^{'}_{i})^2} + \sum_{j \in [m]}{(v_{j} - v^{'}_{j})^2 } \end{aligned}\] Now, one can define the following process for independent random variables \(G \sim \mathcal{N}(0,\mathbf{I}_{n \times n})\) and \(G^{'} \sim \mathcal{N}(0,\mathbf{I}_{m \times m})\) as: \[Y_{u,v} = \langle u,G \rangle + \langle v, G^{'} \rangle \quad \forall u \in \mathbf{S}^{n-1},v \in \mathbf{S}^{m-1}\] Therefore, by Fernique’s inequality we obtain: \[ \mathbb{E}[||A||_{op}] = \mathbb{E}[\sup_{\substack{u \in S^{n-1} \\ v \in S^{m-1}}}{X_{u,v}}] \le \mathbb{E}[\sup_{\substack{u \in S^{n-1} \\ v \in S^{m-1}}}{Y_{u,v}}] = \mathbb{E}[||G||] + \mathbb{E}[||G^{'}||] \le \sqrt{m} + \sqrt{n}\] This is a sharp upper bound when \(m=\Omega(n)\) since we can lower bound spectral norm by the norm of its first column: \[\mathbb{E}[||A||_{op}] \ge \mathbb{E}[\sup_{u \in S^{n-1}}{X_{u,e_1}}] = \mathbb{E}[||A_{:,1}||] \gtrsim \sqrt{n}\] Now that we established a sharp behaviour of largest singular value in expectation we move onto the next question on the list which is how well this quantity is conentrated around its mean?