1
$\begingroup$

I found a thread that solved the problem I need to turn in (or confirmed that I had done it correctly) but doesn't really resolve some confusion I have regarding norms and inner products.

I need to show that the Frobenius norm obeys the general definition of a matrix norm, and only the triangle inequality is giving me any trouble, but that's been worked to death : Frobenius Norm Triangle Inequality

But I went about it somewhat differently and it's highlighted a few concepts I'm shaky on. Here is my approach:

Starting from the defintion $$ ||A||_F = \left( \sum^m_{i=1} \sum^n_{j=1} |A_{ij}|^2 \right)^{1/2}. $$

Now consider

$$ ||A+B||_F = \left( \sum^m_{i=1} \sum^n_{j=1} |A_{ij}+B_{ij}|^2 \right)^{1/2}. $$

Noting that each element $A_{ij}, B_{ij}$ can be thought of as vectors in $\Re^2$, I can apply the good old fashioned triangle inequality to the square root of each summand

such that $|A_{ij}+B_{ij}|\leq |A_{ij}|+|B_{ij}|$

Squaring both sides gives me

$|A_{ij}+B_{ij}|^2\leq |A_{ij}|^2+|B_{ij}|^2 +2|A_{ij}||B_{ij}|$

I see that I'm on the right track, but I'm afraid I'm a bit stuck here.

If I sum over all elements, I get back

$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2\sum^m_{i=1} \sum^n_{j=1}|A_{ij}||B_{ij}|$

Is my approach hopelessly flawed, or is there some way I can salvage this?

$\endgroup$
  • $\begingroup$ I think this sort of reasoning will eventually work (you will need to use the Cauchy schwarz inequality at some point), but what you are basically doing is reproving the triangle inequality for vectors, except with a single index replaced by a double index. The frobenius norm of a matrix is exactly equal to the euclidean norm of the vectorized version of the matrix where you take the matrix and "unwrap" it into a very long vector. $\endgroup$ – Nick Alger Nov 21 '16 at 18:13
  • $\begingroup$ In every other proof I've seen, the Cauchy Schwarz inequality is used to reach the last line I have. I'm not allowed to use any notion of a matrix product, because we haven't been provided such machinery. I have no idea where to go from here; if I can prove that $\sum^m_{i=1} \sum^n_{j=1} |(A_{ij}||B_{ij}| \leq \sum^m_{i=1} \sum^n_{j=1} |A_{ij}|\sum^m_{i=1} \sum^n_{j=1} ||B_{ij}|$ then I'm done, but I can't find a way to do so. $\endgroup$ – BenL Nov 21 '16 at 18:17
1
$\begingroup$

The Frobenius norm of a matrix is identical to the standard Euclidean norm of the vectorized version of the matrix. So, the triangle inequality for vectors directly implies the triangle inequality for the Frobenius norm for matrices.

Let $\text{vec}(\cdot)$ be the vectorization operator that takes a $n$-by-$m$ matrix and unfolds it into a long length $n \cdot m$ vector, stacking each column below the previous one. For example,

$$\text{vec}\left(\begin{bmatrix}1 & 3 \\ 2 & 4\end{bmatrix}\right) = \begin{bmatrix}1 \\ 2 \\ 3 \\ 4\end{bmatrix}.$$

Incidentally, this is how the matrix is actually stored in a computer's memory in many programing languages.

Then from the definitions one can see that $$||M||_\text{Fro} = ||\text{vec}(M)||,$$ where the second norm is the standard euclidean on vectors. In each case we sum the squares of all the entries and take the square root. Additionally, one can notice that $$\text{vec}(A + B) = \text{vec}(A) + \text{vec}(B)$$ because in each case you just add each entry in one object to the corresponding entry in the other.

Hence, \begin{align} ||A + B||_\text{Fro} &= ||\text{vec}(A+B)||\\ &= ||\text{vec}(A) + \text{vec}(B)|| \\ & \le ||\text{vec}(A)|| + ||\text{vec}(B)|| \\ & = ||A||_\text{Fro} + ||B||_\text{Fro}. \end{align} Going from the second line to the third, we used the triangle inequality for vectors.


Edit:

As requested, you can finish your proof (not involving vectorization) as follows. You're really close. So far in the unvectorized proof from the original question question, the proof has progressed to the following statement: $$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2\sum_{ij}|A_{ij}||B_{ij}|$$

Applying the Cauchy-Schwarz inequality to the last term yields: $$\sum_{ij}|A_{ij}||B_{ij}| \le \left(\sum_{ij}|A_{ij}|^2\right)^{1/2}\left(\sum_{ij}|B_{ij}|^2\right)^{1/2} = ||A||_F ||B||_F.$$

Hence, $$||A+B||_F^2 \leq ||A||_F^2 + ||B||_F^2 + 2||A||_F ||B||_F.$$

Using the fact that $a^2 + b^2 + 2ab = (a + b)^2$, we get: $$||A+B||_F^2 \leq (||A||_F + ||B||_F)^2$$ which yields the desired triangle inequality after taking the square root of each side.

$\endgroup$
  • $\begingroup$ That's very interesting, but could you please address the work I've actually done? There is an enormous body of info on this, including what you've provided; I need feedback on method. $\endgroup$ – BenL Nov 21 '16 at 22:20
  • $\begingroup$ I think you are almost there; Use the Cauchy Schwarz inequality and then notice that $|x|^2 + |y|^2 + 2|x|~ |y| = (|x|+|y|)^2$. $\endgroup$ – Nick Alger Nov 22 '16 at 7:09
  • $\begingroup$ I guess the issue is that the Cauchy-Schwarz inequality I'm aware of is $<a,b> \leq |a||b|$. It seems like you're applying it to the product of two vector norms and then using that to say they're less than the product of two matrix norms. I don't see how this follows from definitions. $\endgroup$ – BenL Nov 22 '16 at 12:09
  • $\begingroup$ You may be interested in the first chapter of the excellent book "The Cauchy Schwarz Master Class", where they talk about this inequality a great deal. This first chapter is legally available for free online: www-stat.wharton.upenn.edu/~steele/Publications/Books/CSMC/… $\endgroup$ – Nick Alger Nov 22 '16 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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