17
$\begingroup$

For vector norm, the L2 norm or "Euclidean distance" is the widely used and intuitive definition. But why "most used" or "default" norm definition for a matrix is spectral norm, but not Frobenius norm (which is similar to L2 norm for vectors)?

Does that have something to do with iterative algorithms / matrix powers (if the spectral radius is smaller than 1, then the algorithm will converge)?


  1. It is always arguable for the words like "most used" ,"default". The word "default" mentioned above is coming from the default return type in Matlab function norm. In R the default norm for matrix is L1 norm. Both of the are "unnatural" to me (for a matrix, it seems more "natural" to do $\sqrt{\sum_{i,j}a^{2}_{i,j}}$ like in vector). (Thanks for @usεr11852 and @whuber's comments and sorry for the confusion.)

  2. May be expand the usage of the matrix norm would help me to understand more?

$\endgroup$
  • 4
    $\begingroup$ I am not sure that the spectral norm is the most widely used. For example the Frobenius norm is used for NNMF and usually when approximating the solution to corr/covariance matrices that are not Pos.Def. and are regularised to become Pos. Def. In general Forbenius norm is an "element-wise" norm per se while the spectral norm is based on the eigenvalues so it is a bit more "universal" but this is a matter of opinion. For example Gentle's "Matrix Algebra" literally has a chapter named: "The Frobenius Norm - The “Usual” Norm". So clearly the spectral norm is not the default norm for all. $\endgroup$ – usεr11852 says Reinstate Monic Aug 11 '16 at 14:13
  • 2
    $\begingroup$ @hxd1011: In MATLAB at least this is done because the spectral norm is actually the $L_2$ matrix norm. The $L_2$ matrix norm is a Euclidean-type norm since it is induced by the Euclidean vector norm, where $||A||_2 = \max\limits_{||x||_2 =1} || Ax||_2$. That the catch about having induced norms for matrices, they are induced by a vector norm. I guess this the idea behind R too. It makes sense for the "default" norm command to always return the same norm. $\endgroup$ – usεr11852 says Reinstate Monic Aug 11 '16 at 14:42
  • 3
    $\begingroup$ I disagree that the default is Euclidian, and that the most commonly used is Spectral. $\endgroup$ – Aksakal Aug 11 '16 at 17:54
  • 5
    $\begingroup$ I am baffled by this question because I cannot see how matrix norms are matter of preference or usage. If one particular norm is relevant to a problem, then it is used; if another one is relevant, then it is used. Without any clear problem or application in mind, then, I cannot see how this question is answerable. $\endgroup$ – whuber Aug 11 '16 at 19:04
  • 5
    $\begingroup$ @usεr11852 Thank you for pointing that out. It is important that the text of the question include all such information. Don't rely on people reading the comments, especially when there are many of them. Incidentally, the help page for "norm {base}" in my copy of R lists the $L^1$ norm as the default, not the spectral norm. $\endgroup$ – whuber Aug 11 '16 at 20:37
13
$\begingroup$

In general, I am unsure that the spectral norm is the most widely used. For example the Frobenius norm is used for to approximate solution on non-negative matrix factorisation or correlation/covariance matrix regularisation. I think that part of this question stems from the terminology misdemeanour some people do (myself included) when referring to the Frobenius norm as the Euclidean matrix norm. We should not because actually the $L_2$ matrix norm (ie. the spectral norm) is the one that is induced to matrices when using the $L_2$ vector norm. The Frobenius norm is that is element-wise: $||A||_F = \sqrt{\sum_{i,j}a_{i,j}^2}$, while the $L_2$ matrix norm ($||A||_2 = \sqrt{\lambda_{max}(A^T A)})$) is based on singular values so it is therefore more "univeral". (for luck of a better term?) The $L_2$ matrix norm is a Euclidean-type norm since it is induced by the Euclidean vector norm, where $||A||_2 = \max\limits_{||x||_2 =1} || Ax||_2$. It therefore an induced norm for matrices because it is induced by a vector norm, the $L_2$ vector norm in this case.

Probably MATLAB aims to provide the $L_2$ norm by default when using the command norm; as a consequence it provides the Euclidean vector norm but also the $L_2$ matrix norm, ie. the spectral matrix norm (rather than the wrongly quoted "Frobenius/Euclidean matrix norm"). Finally let me note that what is the default norm is a matter of opinion to some extend: For example J.E. Gentle's "Matrix Algebra - Theory, Computations, and Applications in Statistics" literally has a chapter (3.9.2) named: "The Frobenius Norm - The “Usual” Norm"; so clearly the spectral norm is not the default norm for all parties considered! :) As commented by @amoeba, different communities might have different terminology conventions. It goes without saying that I think Gentle's book is an invaluable resource on the matter of Lin. Algebra application in Statistics and I would prompt you to look it further!

$\endgroup$
  • 1
    $\begingroup$ great answer!! $\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2$ helped me a lot! $\endgroup$ – Haitao Du Aug 11 '16 at 19:53
  • $\begingroup$ I am glad I could help. Please take note of the other answers provided too. They are quite insightful. $\endgroup$ – usεr11852 says Reinstate Monic Aug 11 '16 at 19:56
8
$\begingroup$

A part of the answer may be related to numeric computing.

When you solve the system $$ Ax=b $$ in finite precision, you don't get the exact answer to that problem. You get an approximation $\tilde x$ due to the constraints of finite arithmetics, so that $A\tilde x \approx b$, in some suitable sense. What is it that your solution represents, then? Well, it may well be an exact solution to some other system like $$ \tilde A \tilde x = \tilde b $$ So for $\tilde x$ to have utility, the tilde-system must be close to the original system: $$ \tilde A \approx A, \quad \tilde b \approx b $$ If your algorithm of solving the original system satisfies that property, then it is referred to as backward stable. Now, the accurate analysis of how big the discrepancies $\tilde A-A$, $\tilde b-b$ are eventually leads to errors on bounds which are expressed as $\| \tilde A-A \|$, $\| \tilde b-b\|$. For some analyses, the $l_1$ norm (max column sum) is the easiest one to push through, for others, the $l_\infty$ norm (max row sum) is the easiest to push through (for components of the solution in the linear system case, for instance), and for yet others, the $l_2$ spectral norm is the most appropriate one (induced by the traditional $l_2$ vector norm, as pointed out in another answer). For the work horse of statistical computing in symmetric p.s.d. matrix inversion, Cholesky decomposition (trivia: the first sound is a [x] as in Greek letter "chi", not [tʃ] as in "chase"), the most convenient norm to keep track of the error bounds is the $l_2$ norm... although the Frobenius norm also pops up in some results e.g. on partitioned matrix inversion.

$\endgroup$
  • 3
    $\begingroup$ +1, in particular for the trivia. I have always thought it starts with [k]. I looked it up now and apparently André-Louis Cholesky was of Polish decent (born in France though). Shouldn't it be "sh" sound then, like in Chopin? However, in Russian Cholesky is indeed traditionally written as Холецкий. $\endgroup$ – amoeba says Reinstate Monica Aug 11 '16 at 19:37
  • 3
    $\begingroup$ I take it back. Turns out Chopin's father was French, hence the French pronunciation of the surname. But Cholesky's parents were Polish and in Polish it should have been pronounced with [$\chi$]. Cheers. $\endgroup$ – amoeba says Reinstate Monica Aug 11 '16 at 19:46
  • $\begingroup$ Yeah... I'd thought that as a Russian with a Polish first name, and having first read that Russian spelling a decade or so before first seeing it spelled in Latin letters, I'd have some idea how to pronounce it ;) $\endgroup$ – StasK Aug 11 '16 at 19:53
  • 2
    $\begingroup$ Who cares how to pronounce it, just use the damn thing. $\endgroup$ – Mark L. Stone Aug 11 '16 at 20:19
7
$\begingroup$

The answer to this depends on the field you're in. If you're a mathematician, then all norms in finite dimensions are equivalent: for any two norms $\|\cdot\|_a$ and $\|\cdot\|_b$, there exist constants $C_1,C_2$, which depend only on dimension (and a,b) such that:

$$C_1\|x\|_b\leq \|x\|_a\leq C_2\|x\|_b.$$

This implies that norms in finite dimensions are quite boring and there is essentially no difference between them except in how they scale. This usually means that you can choose the most convenient norm for the problem you're trying to solve. Usually you want to answer questions like "is this operator or procedure bounded" or "does this numerical process converge." With boundedness, you only usually care that something is finite. With convergence, by sacrificing the rate at which you have convergence, you can opt to use a more convenient norm.

For example, in numerical linear algebra, the Frobenius norm is sometimes preferred because it's a lot easier to calculate than the euclidean norm, and also that it naturally connects with a wider class of Hilbert Schmidt operators. Also, like the Euclidean norm, it's submultiplictive: $\|AB\|_F\leq \|A\|_F\|B\|_F$, unlike say, the max norm, so it allows you to easily talk about operator multiplication in whatever space you're working in. People tend to really like both the $p=2$ norm and the Frobenius norm because they have natural relations to both the eigenvalues and singular values of matrices, along with being submultiplictive.

For practical purposes, the differences between norms become more pronounced because we live in a world of dimensions and it usually matters how big a certain quantity is, and how it's measured. Those constants $C_1,C_2$ above are not exactly tight, so it becomes important just how much more or less a certain norm $\|x\|_a$ is compared to $\|x\|_b$.

$\endgroup$
  • 7
    $\begingroup$ Unfortunately, the term "equivalence", as in norms, can and has been misinterpreted, including by people with Ph.D.s in Computer Science. I needed to implement a certain non-trivial calculation using a 2-norm, and this guy produced a solution using a 1-norm, because that was much easier, and after all, he had heard that all norms are equivalent. Well, being off by a factor of (up to) $\sqrt{n}$ was not adequate for me. In that application, I could only afford to be off by a factor of 1. $\endgroup$ – Mark L. Stone Aug 11 '16 at 19:00
  • $\begingroup$ @MarkL.Stone: Right, hence the distinction between theoretical (really: topological) and practical. $\endgroup$ – Alex R. Aug 11 '16 at 19:26
  • $\begingroup$ @MarkL.Stone: +1 Clearly he was not unit-testing his code. :) (Nice anecdote! I will definitely use it when talking about miscommunications in technical computing!) $\endgroup$ – usεr11852 says Reinstate Monic Aug 11 '16 at 20:08
  • $\begingroup$ @usεr11852 ha ha, no, it's worse than that. He did "unit-test" the code as correctly implementing the calculation based on the 1-norm. It failed my system-level examination because it used the wrong norm. $\endgroup$ – Mark L. Stone Aug 11 '16 at 20:16
  • $\begingroup$ @MarkL.Stone: Oh... that's a pity! Having said that, I don't know if you were using an particular hardware configuration or something but to begin with coding a norm calculation from scratch is no-no; there are mathematics libraries one should use to avoid such issues altogether. $\endgroup$ – usεr11852 says Reinstate Monic Aug 11 '16 at 20:25

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.