12
$\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?

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

3 Answers 3

Reset to default
31
$\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.$$

Improve this answer
$\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$
    – Federico Magallanez
    Commented Mar 30, 2011 at 6:11
  • 3
    $\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$
    – Denis Serre
    Commented 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$
    – Federico Magallanez
    Commented 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
    Commented Jan 29, 2018 at 19:41
  • $\begingroup$ @Mah. No I am not aware of a reference. But this must be a classical fact. $\endgroup$
    – Denis Serre
    Commented 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.$$

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .