Skip to main content
1 of 6
user58955
  • 640
  • 5
  • 17

trace norm of AGB, where G is Gaussian random matrix

Suppose that $A$, $B$ are deterministic $n\times n$ matrices and $G$ a Gaussian matrix of i.i.d. entries $N(0,1)$.

I'd like to establish an upper bound of the trace norm of $AGB$ as $$ \mathbb{E}\|AGB\|_\ast \leq \max\{\|A\|_\ast \|B\|_F, \|A\|_F\|B\|_\ast \}, $$ where $\|\cdot\|_\ast$ denotes the trace norm and $\|\cdot\|_F$ the Frobenius norm.

(First question: is it true to replace $\max$ with $\min$?)

By rotational invariance of Gaussian we may assume that $A$ and $B$ are diagonal. Suppose that $A = \operatorname{diag}(a_1,\dots,a_n)$ and $B=\operatorname{diag}(b_1,\dots,b_n)$. Also let $G=(g_{ij})$.

The following is a failed attempt using a net argument.

For a given $u\in \mathbb{R}^n$, consider $\|AGBu\|_2$. We have $$ \|AGBu\|_2^2 = \sum_i \left(\sum_j g_{ij} a_i b_j u_{j}\right)^2 $$ so $$ \mathbb{E}\|GDu\|_2^2 = \sum_i a_i^2 \sum_j b_j u_{j}^2 = \|A\|_F^2 \|Bu\|_2^2 $$ On the other hand, $G\mapsto \|AGBu\|$ is a Liptschiz function of Lipschitz constant $\|A\|_{op}\|Bu\|_2$, hence $\|AGBu\|_2$ should concentrate around $\|A\|_F\|Bu\|_2$. More specifically, $$ \Pr\{\|AGBu\|_2 > \|A\|_F\|Bu\|_2 + t \|A\|_{op}\|Bu\|_2\}\leq e^{-ct^2}. $$ The problem is that the failure probability is too large for constant $t$, so I cannot take a union bound over $u$ in an $\epsilon$-net on $\mathbb{R}^n$, unless $\|A\|_F/\|A\|_{op}\gtrsim n$.

If we had $\|AGBu\|_2\lesssim \|A\|_F\|Bu\|$ for all $u$ in the net, by min-max theorem for singular values (we need $n$ different nets, one for each of $n$ singular values of $AGB$), we would have $\sigma_i(AGB)\lesssim \|A\|_F \sigma_i(B)$ with high probability, or we would have a fast-decaying tail abound so that we can integrate and conclude that $\mathbb{E}\sigma_i(AGB) \lesssim \|A\|_F\sigma_i(B)$. The claimed inequality at the beginning of the post would follow.

Second question: Is it possible to mend this proof to make it work? Perhaps some Gaussian comparison theorems may help here? Any ideas?

user58955
  • 640
  • 5
  • 17