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.


1 Answer 1


[Edit: Now I answer all questions.]

The answer to the first question is yes, the answer to the second question is no, and the answer to the third question is if and only if $p \geq 2$ (only a guess in the case $p<2$).

  • First question

The inequality $$ \mathbb E \|A G B\|_* \leq \min( \|A\|_* \|B\|_F,\|A\|_F \|B\|_*)$$ always holds. By symmetry, it is enough to prove the inequality $\mathbb E \|A G B\|_* \leq \|A\|_* \|B\|_F$. And by writing $A$ as a sum of rank one operators ("the unit ball of the trace class is the convex hull of the norm $1$ rank $1$ matrices"), we can assume that $A$ has rank one.

In that case, $A G B$ has rank one for every $G$. Using (1) that for a rank $1$ matrix, the trace norm and Frobenius norm coincide, and (2) that the $L^1$ norm is less than the $L^2$ norm, we get $$ \mathbb E \|A G B\|_* = \mathbb E \|A G B\|_F \leq (\mathbb E \|A G B\|_F^{2})^{\frac 1 2} = \|A\|_F \|B\|_F=\|A\|_* \|B\|_F.$$ The second equality is a straighforward computation, at least when $A$ and $B$ are diagonal.

  • Second question, and third question when $p \geq 2$.

It follows from the non-commutative Khintchine inequalities of Françoise Lust-Picard that, for every $2 \leq p < \infty$, $$ \mathbb E \|A G B\|_p \simeq \max( \|A\|_p \|B\|_2,\|A\|_2 \|B\|_p)\ if\ p \geq 2$$ (up to constants depending on $p$, whose growth rate is known as $p \to \infty$).

Indeed, the non-commutative Khintchine inequalities states that if $(C_k)$ is a family of matrices and $g_k$ are iid $N(0,1)$ random variables, $$ \mathbb E \| \sum_k g_k C_k\|_p \simeq \max ( \|(\sum C_k C_k^*)^{\frac 1 2}\|_p, \|(\sum C_k^* C_k)^{\frac 1 2}\|_p).$$ (the inequality is sometimes stated in terms of Bernoulli random variables instead of gaussians, and with $L^p$-norm, of $L^2$ norm instead of $L^1$-norm on the left-hand side, but all versions are equivalent by Kahane's inequalities and standard probabilistic arguments). Applying this to $C_{i,j}$, the product of the $i$-th column of $A$ and and $j$-th row of $B$, one gets the answer because $\sum_{i,j} C_{i,j} C_{i,j}^* = \|B\|_2^2 A A^*$ and $\sum_{i,j} C_{i,j}^* C_{i,j}=\|A\|_2^2 B^*B$.

  • Third question if $p \leq 2$.

Here also, the non-commutative Khintchine inequalities (due to Lust-Picard and Pisier when $p=1$) allow, in principle, to give an explicit equivalent of $\mathbb E\|A G B\|_p$. Indeed, when $p \leq 2$, the inequality reads $$ \mathbb E \| \sum_k g_k C_k\|_p \simeq \inf \|(\sum D_k D_k^*)^{\frac 1 2}\|_p+ \|(\sum E_k^* E_k)^{\frac 1 2}\|_p),$$ (up to universal constants) where the infimum is over all families $(D_k,E_k)$ such that $C_k=D_k+E_k$ for all $k$.

This gives a very involved proof of the inequality of the first question. I believe that it can be deduced from this inequality that the inequality $$ \mathbb E \|A G B\|_p \geq \min( \|A\|_p \|B\|_2,\|A\|_2 \|B\|_p)$$ does not hold if $p<2$, but this deserves to be checked.

  • $\begingroup$ Is there anything similar to "the unit ball of the trace class is the convex hull of the norm 1 rank 1 matrices" for Schatten-p class? That is, if I look at the Schatten p-norm of $AGB$ instead of the trace norm (which is Schatten 1-norm)? $\endgroup$
    – user58955
    Commented Jan 14, 2017 at 4:08
  • $\begingroup$ No, there is no useful description of the extreme points of the unit ball for the Schatten classes if $p \neq 1,\infty$. However, you can use interpolation to get $(\mathbb E \|A G B\|_p^2)^{\frac 1 2} \leq \min(\|A\|_p \|B\|_2, \|A\|_2 \|B\|_p)$ for every $1\leq p\leq 2$ (the case $p=2$ being an equality, as shown above). $\endgroup$ Commented Jan 14, 2017 at 6:18
  • $\begingroup$ Ah, non-commutative Khintchine -- I didn't think of that -- thanks! $\endgroup$
    – user58955
    Commented Jan 16, 2017 at 8:54
  • $\begingroup$ For non-commutative Khintchine, it's just the lower bound for which you need $p\geq 2$, isn't it? The upper bound holds for all $p\geq 1$. (The classical Khintchine does hold for $p<2$ though). $\endgroup$
    – user58955
    Commented Jan 16, 2017 at 11:31
  • $\begingroup$ Non-commutative Khintchine inequalities hold for every $0<p<\infty$, it is just that the formula are different for $p>2$ and $p<2$. But you are right, the inequality $\mathbb E \| \sum_k g_k C_k\|_p \lesssim \max ( \|(\sum C_k C_k^*)^{\frac 1 2}\|_p, \|(\sum C_k^* C_k)^{\frac 1 2}\|_p)$ is true for all $p$ (and trivial if $1 \leq p<2$). $\endgroup$ Commented Jan 16, 2017 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.