Dlaczego domyślną normą macierzową jest norma widmowa, a nie norma Frobeniusa?

17

W przypadku normy wektorowej powszechnie stosowaną i intuicyjną definicją jest norma L2 lub „odległość euklidesowa”. Ale dlaczego „najczęściej stosowana” lub „domyślna” definicja normy dla macierzy jest normą spektralną , a nie normą Frobeniusa (która jest podobna do normy L2 dla wektorów)?

Czy ma to coś wspólnego z iteracyjnymi algorytmami / mocami macierzy (jeśli promień widmowy jest mniejszy niż 1, algorytm się zbiegnie)?

  1. Zawsze można spierać się o słowa takie jak „najczęściej używane”, „domyślne”. Słowo „domyślne” wspomniane powyżej pochodzi od domyślnego typu zwracanego w Matlabfunkcji norm. W Rdomyślnej normą dla macierzy jest normą L1. Oba są „nienaturalne” do mnie (na matrycy wydaje się bardziej „naturalne”, aby zrobić ∑i,jai,j2 jak w wektorze). (Dzięki za komentarze @ usεr11852 i @ whuber i przepraszam za zamieszanie.)

  2. Czy można rozszerzyć użycie normy macierzowej , pomogłoby mi to zrozumieć więcej?

matrix linear-algebra Haitao Du
źródło
4
Nie jestem pewien, czy norma spektralna jest najczęściej stosowana. Na przykład norma Frobeniusa jest stosowana dla NNMF i zwykle podczas przybliżania rozwiązania do macierzy korelacji / kowariancji, które nie są Pos.Def. i są uregulowani, aby stać się Poz. Def. Ogólnie rzecz biorąc, norma Forbeniusa jest normą „elementarną” per se, podczas gdy norma widmowa oparta jest na wartościach własnych, więc jest nieco bardziej „uniwersalna”, ale jest to kwestia opinii. Na przykład „ Matryca algebry ” firmy Gentle ma dosłownie rozdział o nazwie: „ Norma Frobeniusa - norma„ Zwykła ”. Tak więc norma widmowa nie jest dla wszystkich normą domyślną .
usεr11852 mówi: Przywróć Monic
2
@ hxd1011 W MATLAB przynajmniej Dzieje się tak dlatego widmowa normą jest rzeczywiście normą macierzy. L 2 normą matryca jest normą euklidesową typu, ponieważ indukowane jest normą euklidesową wektora, w którym | | A | | 2 = maks. | | x | | 2 = 1 | | A x | | 2 . Że haczyk związany z indukowaniem norm dla macierzy jest indukowany przez normę wektorowąL2L2||A||2=max||x||2=1||Ax||2 . Wydaje mi się, że to też jest idea R. Rozsądne jest, aby polecenie „default” normzawsze zwracało tę samą normę.
usεr11852 mówi: Przywróć Monic
3
Nie zgadzam się, że domyślnie jest to euklidesowy, a najczęściej stosowanym jest Spectral.
Aksakal,
5
Zaskakuje mnie to pytanie, ponieważ nie widzę, w jaki sposób normy matrycowe są kwestią preferencji lub zastosowania. Jeśli jedna konkretna norma jest istotna dla problemu, wówczas jest stosowana; jeśli inny jest istotny, to jest on używany. Bez wyraźnego problemu lub zastosowania nie widzę więc, w jaki sposób można odpowiedzieć na to pytanie.
whuber
5
@ usεr11852 Dziękujemy za zwrócenie na to uwagi. Ważne jest, aby tekst pytania zawierał wszystkie takie informacje. Nie polegaj na ludziach czytających komentarze, zwłaszcza gdy jest ich wiele. Nawiasem mówiąc, strona pomocy dla „normy {base}” w mojej kopii Rlist wymienia normę jako domyślną, a nie normę spektralną. L1
whuber

Odpowiedzi:

13

Ogólnie nie jestem pewien, czy norma spektralna jest najczęściej stosowana. Na przykład normę Frobeniusa stosuje się w celu przybliżenia rozwiązania nieujemnego rozkładania na czynniki pierwsze macierzy lub regulowania macierzy korelacji / kowariancji . Myślę, że część tego pytania wynika z wykroczenia terminologicznego, które niektórzy ludzie (łącznie ze mną) odnoszą się do normy Frobeniusa jako normy matrycy euklidesowej . Dlatego, że nie należy w rzeczywistości normą macierz (tj. Widmowa normą) to taka, która jest skłonna do matryc przy użyciu L 2 wektor normy. Normą Frobeniusa jest to, że jest elementarne: | | A | |L2L2 , aL2normą macierzy (||||2=√||A||F=∑i,jai,j2L2) opiera się na wartościach osobliwych, dlatego jest bardziej „uniwersalny”. (na szczęście lepszego terminu?)Norma macierzyL2jest normą typu euklidesowego, ponieważ jest indukowana przez normę wektora euklidesowego, gdzie| | A| | 2=maks. | | x | | 2 = 1 | | Ax| | 2. Jest to zatemindukowana normadla macierzy, ponieważ jestindukowanaprzez||A||2=λmax(ATA))L2||A||2=max||x||2=1||Ax||2 norma wektorowa ,L2 w tym przypadku norma wektorowa .

Prawdopodobnie MATLAB dąży do domyślnego zapewnienia normy podczas używania polecenia ; co w konsekwencji zapewnia euklidesową normy wektorowej ale także L 2 normę matrycy, tj. widmowa normą matrycy (niesłusznie zamiast cytowane „ Frobeniusa / norma euklidesowa macierz ”). Na koniec zauważę, że to, co jest domyślną normą, jest w pewnym stopniu kwestią opinii: na przykład „ Algebra macierzy - teoria, obliczenia i zastosowania w statystyce ” JE Gentle'a dosłownie ma rozdział (3.9.2) o nazwie: „ Frobenius” Norma - „Zwykła” normaL2normL2"; więc wyraźnie widmowa norma nie jest domyślną normą dla wszystkich rozważanych stron! :) Jak komentuje @amoeba, różne społeczności mogą mieć różne konwencje terminologiczne. Nie trzeba dodawać, że uważam, że książka Gentle'a jest nieocenionym źródłem informacji na temat Aplikacja Lin. Algebra w statystykach i zachęcam do dalszych poszukiwań!

usεr11852 mówi Reinstate Monic
źródło
1
świetna odpowiedź!! mi pomogło! ‖A‖2=max‖x‖2=1‖Ax‖2
Haitao Du
Cieszę się, że mogłem pomóc. Zwróć także uwagę na inne udzielone odpowiedzi. Są dość wnikliwi.
usεr11852 mówi: Przywróć Monic
8

Część odpowiedzi może być związana z obliczeniami numerycznymi.

Ax=b
x~Ax~≈b
A~x~=b~
x~
A~≈A,b~≈b
A~−Ab~−b‖A~−A‖‖b~−b‖l1l∞ 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 l2 spectral norm is the most appropriate one (induced by the traditional l2 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 l2 norm... although the Frobenius norm also pops up in some results e.g. on partitioned matrix inversion.

StasK
źródło
3
+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 Холецкий.
amoeba says Reinstate Monica
3
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 [χ]. Cheers.
amoeba says Reinstate Monica
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 ;)
StasK
2
Who cares how to pronounce it, just use the damn thing.
Mark L. Stone
7

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 ‖⋅‖a and ‖⋅‖b, there exist constants C1,C2, which depend only on dimension (and a,b) such that:

C1‖x‖b≤‖x‖a≤C2‖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≤‖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 C1,C2 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.

Alex R.
źródło
7
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) n was not adequate for me. In that application, I could only afford to be off by a factor of 1.
Mark L. Stone
@MarkL.Stone: Right, hence the distinction between theoretical (really: topological) and practical.
Alex R.
@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!)
usεr11852 says Reinstate Monic
@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.
Mark L. Stone
@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.
usεr11852 says Reinstate Monic