Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I don't know. Have you tried it with, say, some $2\times2$ examples? –  Gerry Myerson Mar 29 '11 at 3:00
add comment

2 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
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)$. –  Federico Magallanez Mar 30 '11 at 6:11
2  
@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.$$ –  Denis Serre Mar 30 '11 at 7:56
    
Oops. Now I understand. The last equation in your answer is not correctly converted by MathJax, so I misunderstood your explanation. Sorry about that. –  Federico Magallanez Mar 30 '11 at 23:20
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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