10
$\begingroup$

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

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 claims 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$
  • submultiplicativity: $\|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 all other norms are Frobenius norms. Does $\|XY\|_F\leq \|X\|_2\|Y\|_F$ always hold?

$\endgroup$
1
  • 1
    $\begingroup$ I don't know. Have you tried it with, say, some $2\times2$ examples? $\endgroup$ Mar 29, 2011 at 3:00

3 Answers 3

29
$\begingroup$

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; 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.$$

$\endgroup$
7
  • $\begingroup$ By singular value decomposition, $A=U\Sigma V^T$ and $B=Z\Lambda W^T$ where $U,V,Z,W$ are orthonormal and $\Sigma=diag(a_1,...,a_n),\Lambda=diag(b_1,...,b_n)$ are diagonal. Then $||A||=||\Sigma||$ and $||B||=||\Lambda||$ as you pointed out. Your argument is based on the claim that $||AB||=||\Sigma\Lambda||$, but $||AB||=|||U\Sigma VZ\Lambda W||=||\Sigma VZ\Lambda||$. I'm afraid we cannot guarantee that $\Sigma VZ\Lambda$ is unitarily similar to $\Sigma\Lambda=diag(a_1b_1, ...,a_n b_n)$. $\endgroup$ Mar 30, 2011 at 6:11
  • 2
    $\begingroup$ @Federico. I only use $$\|AB\|_F=\|U\Sigma V^TB\|_F=\|\Sigma V^TB\|_F\le\|\Sigma\|_2\|V^TB\|_F=\|A\|_2\|B\|_F.$$ $\endgroup$ Mar 30, 2011 at 7:56
  • $\begingroup$ Oops. Now I understand. The last equation in your answer is not correctly converted by MathJax, so I misunderstood your explanation. Sorry about that. $\endgroup$ Mar 30, 2011 at 23:20
  • $\begingroup$ @DenisSerre I would like to use this inequality in my research, but I couldn't find any name or reference for it. Does it have a specific name or do you know any reference for it? Thanks in advance. $\endgroup$
    – Mah
    Jan 29, 2018 at 19:41
  • $\begingroup$ @Mah. No I am not aware of a reference. But this must be a classical fact. $\endgroup$ Jan 30, 2018 at 6:44
11
$\begingroup$

A simpler, more direct proof that requires no SVD: let $Y_j$ be the $j$th column of $Y$ and $Z_j$ that of $Z=XY$. Then, $$\|Z\|_F^2 = \sum_j \|Z_j\|_2^2 = \sum_j \|XY_j\|_2^2 \leq \sum_j \|X\|_2^2\|Y_j\|_2^2 = \|X\|_2^2\|Y\|_F^2.$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.