Sharp nonasymptotic bounds on the norm of random matrices with independent entries (Q317469)

The authors present precise bounds for the spectral norms \(\|X\|\) of random matrices \(X\) with independent entries. The results improve earlier work considerably and are, in particular in the case of \(n\times n\) symmetric matrices \(X\) with i.i.d. \(N(0,1)\)-distributed entries \(X_{i,j}\) for \(i\geq j\), close to the limit behavior known from the classical semicircle law of Wigner. The proofs of these bounds are based on the observation that \(\|X\|\) is comparable with \(\operatorname{tr}(X^p)^{1/p}\) for \(p\equiv \log n\) for \(n\) large. The authors then derive a comparison theorem which compares \({\mathbf E} \operatorname{tr}(X^p)\) with \({\mathbf E} \operatorname{tr}(Y^{2p}_{r})\) where \(Y_r\) is a \(r\times r\) symmetric matrix with i.i.d. \(N(0,1)\)-distributed entries \(X_{i,j}\) for \(i\geq j\), where the dimension \(r\) depends on \(p\) and data of \(X\) in some way. This approach finally leads to bounds for \(\|X\|\) even in the non-Gaussian case. In the Gaussian case, the main result is as follows: If \(X\) is a \(n\times n\) symmetric matrix with independent \(N(0,b_{i,j})\)-distributed entries \(X_{i,j}\) for \(i\geq j\), then \[ {\mathbf E} \|X\| \leq \max_i\sqrt{ \sum_j b_{i,j}^2} + \max_{i,j} |b_{i,j}|\cdot \sqrt{\log n}. \] In several special cases, this bound is asymptotically optimal.