Bounded symmetric matrix expectation at the variance scale

Let $I=\{(i,j):1\le j\le i\le n\}$. For $e\in I$ let $T_e$ be the finite set of values of $X_e$ with positive probability, and put ${\mu }_e(t)=\mathbb{P}(X_e=t)$. The value events form a finite partition up to events of probability zero, so the probability-measure axioms give ${\sum }_{t\in T_e}{\mu }_e(t)=1$. Thus $(T_e,{\mu }_e)$ is a finite probability space. On the product $T={\prod }_{e\in I}{T}_e$, let $Y_e(t)=t_e$ and fill the upper triangle by symmetry. By the product theorem these entries are mutually independent. Independence of the original entries gives $\mathbb{P}(X_e=t_e\text{ for all }e\in I)={\prod }_{e\in I}{\mu }_e(t_e)$, exactly the product weight of $t$. All other value arrays have probability zero. Hence $Y$ has the same finite joint law as $X$, including each marginal's symmetry and bound.

For every nonnegative real-valued function $g$ of the finitely many possible matrix values, the simple-function expectation formula gives $\mathbb{E}g(X)={\sum }_{t\in T}g(t){\prod }_{e\in I}{\mu }_e(t_e)=\mathbb{E}g(Y)$. In particular $\mathbb{E}\mathrm{\parallel }X\mathrm{\parallel }=\mathbb{E}\mathrm{\parallel }Y\mathrm{\parallel }$, and all entry second moments are preserved. Here the finitely many value fibres are measurable intersections of entry value events, so $g(X)$ is a nonnegative simple measurable function; this includes the operator norm. We may therefore prove the estimate on this finite product space without restricting the original sample space.

Set $b_{ij}=(\mathbb{E}{Y}_{ij}^2{)}^{1\mathrm{/}2}=b_{ji}$ and $Z=\{(i,j)\in I:b_{ij}=0\}$. For $b_{ij}>0$ set ${\xi }_{ij}=Y_{ij}\mathrm{/}{b}_{ij}$. Symmetry pairs each value with its negative, so its finite mean is zero and $\mathbb{E}{\xi }_{ij}^2=1$. If $b_{ij}=0$, the nonnegative weighted sum $\mathbb{E}{Y}_{ij}^2=0$ forces $Y_{ij}=0$ at every outcome of positive weight. Enlarge $T$ by one factor $\{-1,1\}$ with weights $1\mathrm{/}2,1\mathrm{/}2$ for each index in $Z$, using the product theorem; the empty $Z$ requires no extra factor. For these indices take ${\xi }_{ij}$ to be the corresponding sign. The enlarged space has total weight one and preserves the law of $Y$; the signs are mutually independent and independent of all original coordinates. Every ${\xi }_{ij}$ depends on its own distinct product coordinate, so its value events are coordinate events and the whole lower-triangular family is independent. All ${\xi }_{ij}$ are symmetric with mean zero and unit variance, and $Y_{ij}=b_{ij}{\xi }_{ij}$ almost surely, including the diagonal and zero-variance entries.

The external estimate applies to this factorization of $Y$. Its parameter is $\sigma ={\max }_i({\sum }_j{b}_{ij}^2{)}^{1\mathrm{/}2}=s$, and $\mathrm{\mid }{Y}_{ij}\mathrm{\mid }\le 1$ gives $\mathrm{\parallel }{Y}_{ij}{\mathrm{\parallel }}_{2\lceil 3\log n\rceil }\le 1$ by summing the bounded nonnegative moments against normalized weights. Substitution yields $\mathbb{E}\mathrm{\parallel }Y\mathrm{\parallel }\le e^{2\mathrm{/}3}(2s+42\sqrt{\log n})$. Transfer back by step 2.1 proves the claim for the original $X$.