Question

Let $||\cdot||_F$ and $||\cdot||_2$ be the Frobenius norm and the spectral norm.

I'm reading Ji-Guang Sun's paper 'Perturbation Bounds for the Cholesky and QR Factorizations' from BIT 31 in 1991. While deriving the perturbation bound on Cholesky factorization $A=LL^T$ with $A\in\mathbb{R}^{n\times k}$ of rank $k$, he begins with the perturbed matrix $A+E$ and its Cholesky factorization.

$A+E=(L+G)(L+G)^T$

Expanding the RHS and subtracting $A$ from both sides, we have $E = GL^T + LG^T + GG^T$. Then he claimed in (2.12) of his paper that

$||E||_F\leq 2||L||_2||G||_F + ||G||_F^2$.

If I read $||L||_F$ instead of $||L||_2$, everything seems perfectly normal to me by the following three properties of any matrix norm.

• $||X^T||=||X||$ for any matrix norm
• subadditivity: $||X+Y||_p\leq||X||_p + ||Y||_p$
• submultiplicity: $||XY||_p\leq ||X||_p\cdot||Y||_p$ for $p=2$ or $F$

But I'm not sure why $||L||$ is a spectral norm in this equation even though every other norms are Frobenius norms. Does $||XY||_F\leq ||X||_2||Y||_F$ always hold?

Answer 1

This inequality is true. But let me first make a comment. When you say that any matrix norm is submultiplicative ($\|XY\|\le\|X\|\cdot\|Y\|$), you understate that a matrix norm over $M_n(\mathbb C)$ is subordinated to a norm of $\mathbb C^n$: $$\|A\|:=\sup_{x\ne0}\frac{\|Ax\|}{\|x\|}.$$ But the Frobenius norm is not subordinated, for instance because $\|I_n\|_F=\sqrt{n}$, whereas $\|I_n\|=1$ for any matrix norm. The reason for which the Frobenius norm is submultiplicative is therefore specific to it; it is more or less a consequence of Cauchy--Schwarz inequality.

Now, back to your question. Both norms are unitarily invariant, in the sense that $\|UAV\|=\|A\|$ whenever $U$ and $V$ are unitary matrices. Therefore we may assume that $A$ is diagonal, with diagonal entries $a_1,\ldots,a_n$. Now, we have $\|A\|_2=\max_i|a_i|$ and therefore $$\|AB\|_F^2 = \sum |a_i b_{ij}|^2\le \|A\|2^2 \sum |b{ij}|^2 =\|A\|_2^2\|B\|_F^2.$$

Answer 2

The general result is equivalent to the result for diagonal matrices (with positive entries), since this is what maximizes the LHS, given specified singular values for $X, Y.$ I leave that case up to OP.