Return to Question

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. I can show the inequality with an additional $\sqrt{\log n}$ factor on the right-hand side but I do not think the $\sqrt{\log n}$ factor is necessary...

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

[Update] As answered by Mikael de la Salle below, it is possible to replace $\max$ with $\min$ for $p\in [1,2]$, to obtain that $$ \mathbb{E}\|AGB\|_p \leq \min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$

For $p>2$, it is necessary to have $\max$. Take $A$ to be identity matrix and $B = e_1e_1^T$ (zero matrix except the top-left entry being $1$), then $\|AGB\|_p \sim \sqrt{n}$ while $\|A\|_p \|B\|_F = n^{1/p} < \sqrt{n}$.

Second question: Does the following hold for $p>2$? $$ \mathbb{E}\|AGB\|_p \leq C\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$ for some constant $C$ (which can depend on $p$)? I could get the inequality with an extra $\sqrt{\log n}$ factor on the right-hand side, but I am not sure if it is necessary. For $p=\infty$, it is too easy to get $\sqrt{n}\|A\|_{op}\|B\|_{op}$, which is bigger than the bound I want.

Third question: How about the lower bound on $\mathbb{E}\|AGB\|_p$? Do we have $$ \mathbb{E}\|AGB\|_{p} \geq c\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for some constant $c$?

I can show that $$ \mathbb{E}\|AGB\|_{op} \geq \max\{\|A\|_{op} \|B\|_F, \|A\|_F \|B\|_{op}\} $$ So I think the lower bound inequality holds for $p\geq 2$. For $p = 1$, if we take $A$ to be identity matrix and $B=e_1e_1^T$ then $\mathbb{E}\|AGB\|_{p}\approx \sqrt{n}$, so the inequality cannot hold with $\max$. So the question is, will it hold $$ \mathbb{E}\|AGB\|_{p} \geq c\min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for $p\in [1,2)$? Again I can show it with an extra $1/\log n$ factor on the right but I am not sure if it is necessary.

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. I can show the inequality with an additional $\log n$ factor on the right-hand side but I do not think the $\log n$ factor is necessary...

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

[Update] As answered by Mikael de la Salle below, it is possible to replace $\max$ with $\min$ for $p\in [1,2]$, to obtain that $$ \mathbb{E}\|AGB\|_p \leq \min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$

For $p>2$, it is necessary to have $\max$. Take $A$ to be identity matrix and $B = e_1e_1^T$ (zero matrix except the top-left entry being $1$), then $\|AGB\|_p \sim \sqrt{n}$ while $\|A\|_p \|B\|_F = n^{1/p} < \sqrt{n}$.

Second question: Does the following hold for $p>2$? $$ \mathbb{E}\|AGB\|_p \leq C\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$ for some constant $C$ (which can depend on $p$)? I could get the inequality with an extra $\log n$ factor on the right-hand side, but I am not sure if it is necessary. For $p=\infty$, it is too easy to get $\sqrt{n}\|A\|_{op}\|B\|_{op}$, which is bigger than the bound I want.

Third question: How about the lower bound on $\mathbb{E}\|AGB\|_p$? Do we have $$ \mathbb{E}\|AGB\|_{p} \geq c\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for some constant $c$?

I can show that $$ \mathbb{E}\|AGB\|_{op} \geq \max\{\|A\|_{op} \|B\|_F, \|A\|_F \|B\|_{op}\} $$ So I think the lower bound inequality holds for $p\geq 2$. For $p = 1$, if we take $A$ to be identity matrix and $B=e_1e_1^T$ then $\mathbb{E}\|AGB\|_{p}\approx \sqrt{n}$, so the inequality cannot hold with $\max$. So the question is, will it hold $$ \mathbb{E}\|AGB\|_{p} \geq c\min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for $p\in [1,2)$? Again I can show it with an extra $1/\log n$ factor on the right but I am not sure if it is necessary.

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. I can show the inequality with an additional $\sqrt{\log n}$ factor on the right-hand side but I do not think the $\sqrt{\log n}$ factor is necessary...

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

[Update] As answered by Mikael de la Salle below, it is possible to replace $\max$ with $\min$ for $p\in [1,2]$, to obtain that $$ \mathbb{E}\|AGB\|_p \leq \min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$

For $p>2$, it is necessary to have $\max$. Take $A$ to be identity matrix and $B = e_1e_1^T$ (zero matrix except the top-left entry being $1$), then $\|AGB\|_p \sim \sqrt{n}$ while $\|A\|_p \|B\|_F = n^{1/p} < \sqrt{n}$.

Second question: Does the following hold for $p>2$? $$ \mathbb{E}\|AGB\|_p \leq C\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$ for some constant $C$ (which can depend on $p$)? I could get the inequality with an extra $\sqrt{\log n}$ factor on the right-hand side, but I am not sure if it is necessary. For $p=\infty$, it is too easy to get $\sqrt{n}\|A\|_{op}\|B\|_{op}$, which is bigger than the bound I want.

Third question: How about the lower bound on $\mathbb{E}\|AGB\|_p$? Do we have $$ \mathbb{E}\|AGB\|_{p} \geq c\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for some constant $c$?

I can show that $$ \mathbb{E}\|AGB\|_{op} \geq \max\{\|A\|_{op} \|B\|_F, \|A\|_F \|B\|_{op}\} $$ So I think the lower bound inequality holds for $p\geq 2$. How about $p < 2$ then? If not, will it hold $$ \mathbb{E}\|AGB\|_{p} \geq c\min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}? $$

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. I can show the inequality with an additional $\sqrt{\log n}$ factor on the right-hand side but I do not think the $\sqrt{\log n}$ factor is necessary...

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

[Update] As answered by Mikael de la Salle below, it is possible to replace $\max$ with $\min$ for $p\in [1,2]$, to obtain that $$ \mathbb{E}\|AGB\|_p \leq \min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$

For $p>2$, it is necessary to have $\max$. Take $A$ to be identity matrix and $B = e_1e_1^T$ (zero matrix except the top-left entry being $1$), then $\|AGB\|_p \sim \sqrt{n}$ while $\|A\|_p \|B\|_F = n^{1/p} < \sqrt{n}$.

Second question: Does the following hold for $p>2$? $$ \mathbb{E}\|AGB\|_p \leq C\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$ for some constant $C$ (which can depend on $p$)? I could get the inequality with an extra $\sqrt{\log n}$ factor on the right-hand side, but I am not sure if it is necessary. For $p=\infty$, it is too easy to get $\sqrt{n}\|A\|_{op}\|B\|_{op}$, which is bigger than the bound I want.

Third question: How about the lower bound on $\mathbb{E}\|AGB\|_p$? Do we have $$ \mathbb{E}\|AGB\|_{p} \geq c\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for some constant $c$?

I can show that $$ \mathbb{E}\|AGB\|_{op} \geq \max\{\|A\|_{op} \|B\|_F, \|A\|_F \|B\|_{op}\} $$ So I think the lower bound inequality holds for $p\geq 2$. For $p = 1$, if we take $A$ to be identity matrix and $B=e_1e_1^T$ then $\mathbb{E}\|AGB\|_{p}\approx \sqrt{n}$, so the inequality cannot hold with $\max$. So the question is, will it hold $$ \mathbb{E}\|AGB\|_{p} \geq c\min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for $p\in [1,2)$? Again I can show it with an extra $1/\log n$ factor on the right but I am not sure if it is necessary.

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. I can show the inequality with an additional $\sqrt{\log n}$ factor on the right-hand side but I do not think the $\sqrt{\log n}$ factor is necessary...

(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 bound 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?

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. I can show the inequality with an additional $\sqrt{\log n}$ factor on the right-hand side but I do not think the $\sqrt{\log n}$ factor is necessary...

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

[Update] As answered by Mikael de la Salle below, it is possible to replace $\max$ with $\min$ for $p\in [1,2]$, to obtain that $$ \mathbb{E}\|AGB\|_p \leq \min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$

For $p>2$, it is necessary to have $\max$. Take $A$ to be identity matrix and $B = e_1e_1^T$ (zero matrix except the top-left entry being $1$), then $\|AGB\|_p \sim \sqrt{n}$ while $\|A\|_p \|B\|_F = n^{1/p} < \sqrt{n}$.

Second question: Does the following hold for $p>2$? $$ \mathbb{E}\|AGB\|_p \leq C\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}. $$ for some constant $C$ (which can depend on $p$)? I could get the inequality with an extra $\sqrt{\log n}$ factor on the right-hand side, but I am not sure if it is necessary. For $p=\infty$, it is too easy to get $\sqrt{n}\|A\|_{op}\|B\|_{op}$, which is bigger than the bound I want.

Third question: How about the lower bound on $\mathbb{E}\|AGB\|_p$? Do we have $$ \mathbb{E}\|AGB\|_{p} \geq c\max\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\} $$ for some constant $c$?

I can show that $$ \mathbb{E}\|AGB\|_{op} \geq \max\{\|A\|_{op} \|B\|_F, \|A\|_F \|B\|_{op}\} $$ So I think the lower bound inequality holds for $p\geq 2$. How about $p < 2$ then? If not, will it hold $$ \mathbb{E}\|AGB\|_{p} \geq c\min\{\|A\|_p \|B\|_F, \|A\|_F \|B\|_p\}? $$