Por que a norma padrão da matriz é a norma espectral e não a norma de Frobenius?

Para a norma vetorial, a norma L2 ou "distância euclidiana" é a definição amplamente usada e intuitiva. Mas por que a definição de norma "mais usada" ou "padrão" para uma matriz é a norma espectral , mas não a norma de Frobenius (que é semelhante à norma L2 para vetores)?

Isso tem algo a ver com algoritmos iterativos / potências matriciais (se o raio espectral for menor que 1, o algoritmo convergirá)?

É sempre discutível para as palavras como "mais usado", "padrão". A palavra "default" mencionado acima é proveniente do tipo padrão de retorno em Matlabfunção norm. A Rnorma padrão para matriz é a norma L1. Ambos são "não naturais" para mim (para uma matriz, parece mais "natural" fazer como no vetor). (Obrigado pelos comentários @ usεr11852 e @ whuber e desculpe-me pela confusão.) $\sqrt{\sum_{i,j}a^{2}_{i,j}}$
Pode ser expandir o uso da norma matriz me ajudaria a entender mais?

matrix linear-algebra Haitao Du
fonte

Não tenho certeza de que a norma espectral seja a mais usada. Por exemplo, a norma Frobenius é usada para NNMF e geralmente ao aproximar a solução de matrizes de corr / covariância que não são Pos.Def. e são regularizados para se tornar Pos. Def. Em geral, a norma de Forbenius é uma norma "em termos de elementos", enquanto a norma espectral é baseada nos valores próprios, por isso é um pouco mais "universal", mas isso é uma questão de opinião. Por exemplo, " Álgebra de matriz " de Gentle literalmente tem um capítulo chamado: " A norma de Frobenius - a norma" usual " ". Então, claramente, a norma espectral não é a norma padrão para todos.

usεr11852 diz Reinstate Monic

@ hxd1011: No MATLAB, pelo menos, isso é feito porque a norma espectral é realmente a norma da matriz . A norma da matriz é uma norma do tipo euclidiano, pois é induzida pela norma do vetor euclidiano, onde . Que o problema de ter normas induzidas para matrizes, elas são induzidas por uma norma vetorial . Eu acho que essa é a ideia por trás do R também. Faz sentido que o comando "padrão" retorne sempre a mesma norma.

L_{2}

$L_2$

L_{2}

$L_2$

| | A | |_{2} = max_{| | x | |_{2} = 1} | | A x | |_{2}

$||A||_2 = \max\limits_{||x||_2 =1} || Ax||_2$ norm

usεr11852 diz Reinstate Monic

Eu discordo que o padrão é euclidiano e que o mais comumente usado é o espectral.

Aksakal

Estou perplexo com esta pergunta porque não consigo ver como as normas matriciais são matéria de preferência ou uso. Se uma norma específica é relevante para um problema, ela é usada; se outro for relevante, ele será usado. Sem nenhum problema ou aplicação clara em mente, não consigo ver como essa pergunta é respondida.

whuber

@ usεr11852 Obrigado por apontar isso. É importante que o texto da pergunta inclua todas essas informações. Não confie nas pessoas que estão lendo os comentários, especialmente quando houver muitos deles. Aliás, a página de ajuda para "norma {base}" na minha cópia de Rlista a norma como padrão, não a norma espectral.

L^{1}

$L^1$

whuber

Respostas:

Em geral, não tenho certeza de que a norma espectral seja a mais amplamente usada. Por exemplo, a norma de Frobenius é usada para aproximar soluções em fatoração de matriz não negativa ou regularização de matriz de correlação / covariância . Penso que parte desta questão decorre da contravenção terminológica que algumas pessoas fazem (inclusive eu) quando se referem à norma de Frobenius como a norma da matriz euclidiana . Não devemos, porque, na verdade, a norma da matriz (ou seja, a norma espectral) é aquela que é induzida às matrizes ao usar a norma do vetor . A norma de Frobenius é a de elementos: , enquanto o $L_2$ $L_2$ $||A||_F = \sqrt{\sum_{i,j}a_{i,j}^2}$ $L_2$ A norma da matriz ( ) é baseada em valores singulares, portanto, é mais "universal". (para sorte de um termo melhor?) A norma da matriz é do tipo euclidiano, pois é induzida pela norma do vetor euclidiano, onde . Portanto, é uma norma induzida para matrizes porque é induzida por uma norma vetorial , a norma vetorial nesse caso. $||A||_2 = \sqrt{\lambda_{max}(A^T A)})$ $L_2$ $||A||_2 = \max\limits_{||x||_2 =1} || Ax||_2$ $L_2$

Provavelmente o MATLAB visa fornecer a norma por padrão ao usar o comando ; como conseqüência, fornece a norma do vetor euclidiano, mas também a norma da matriz , ie. a norma da matriz espectral (em vez da norma da matriz de Frobenius / Euclidiana citada incorretamente ). Finalmente, deixe-me notar que qual é a norma padrão é uma questão de opinião até certo ponto: por exemplo, " Álgebra de matriz - teoria, computações e aplicações em estatística ", de JE Gentle, literalmente tem um capítulo (3.9.2) chamado: " O Frobenius Norma - A norma "usual" $L_2$ norm $L_2$ "; tão claramente a norma espectral não é a norma para todas as partes consideradas! :) Como comentado por @amoeba, diferentes comunidades podem ter convenções terminológicas diferentes. Não é preciso dizer que acho que o livro de Gentle é um recurso inestimável em matéria de Lin. Álgebra aplicação em Estatística e gostaria de pedir-lhe para olhar mais!

usεr11852 diz Reinstate Monic
fonte

Ótima resposta!! me ajudou muito!

‖ A ‖_{2} = max_{‖ x ‖_{2} = 1} ‖ A x ‖_{2}

$\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2$

Haitao Du

Estou feliz por poder ajudar. Observe também as outras respostas fornecidas. Eles são bastante perspicazes.

usεr11852 diz Reinstate Monic

Uma parte da resposta pode estar relacionada à computação numérica.

Quando você resolve o sistema com precisão finita, não obtém a resposta exata para esse problema. Você obtém uma aproximação devido às restrições da aritmética finita, de modo que , em algum sentido adequado. O que sua solução representa então? Bem, pode ser uma solução exata para outro sistema como Para que o tenha utilidade, o sistema til deve estar próximo ao sistema original: Se o seu algoritmo

A x = b

$Ax=b$

\tilde{x}

$\tilde x$

A \tilde{x} \approx b

$A\tilde x \approx b$

\tilde{A} \tilde{x} = \tilde{b}

$\tilde A \tilde x = \tilde b$

\tilde{x}

$\tilde x$

\tilde{A} \approx A, \tilde{b} \approx b

$\tilde A \approx A, \quad \tilde b \approx b$

de resolver o sistema original satisfaz essa propriedade, é chamado de estável para trás . Agora, a análise precisa de quão grandes são as discrepâncias , leva a erros nos limites expressos como,. Para algumas análises, a norma (soma máxima da coluna) é a mais fácil de ; para outras, a norma (soma máxima de linhas) é a mais fácil de executar (para componentes da solução no caso de sistema linear) , por exemplo), e para outros ainda, a norma espectral é a mais apropriada (induzida pela tradicional

\tilde{A} - A

$\tilde A-A$

\tilde{b} - b

$\tilde b-b$

‖ \tilde{A} - A ‖

$\| \tilde A-A \|$

‖ \tilde{b} - b ‖

$\| \tilde b-b\|$

l_{1}

$l_1$

l_{\infty}

$l_\infty$

l_{2}

$l_2$

l_{2}

$l_2$ norma do vetor, como apontado em outra resposta ). Para o cavalo de trabalho da computação estatística na inversão simétrica da matriz psd, a decomposição de Cholesky (trivialidade: o primeiro som é um [x] como na letra grega "chi", não [tʃ] como em "chase"), a norma mais conveniente para acompanhar os limites de erro é a norma ... embora a norma Frobenius também apareça em alguns resultados, por exemplo, na inversão matricial particionada.

l_{2}

$l_2$

StasK
fonte

+1, em particular para as trivialidades. Eu sempre pensei que começa com [k]. Pesquisei agora e, aparentemente, André-Louis Cholesky era de decente polonês (nascido na França). Não deveria ser um som "sh", como em Chopin? No entanto, em russo, Cholesky é realmente tradicionalmente escrito como Холецкий.

Ameba diz Reinstate Monica

Eu retiro. Acontece que o pai de Chopin era francês, daí a pronúncia francesa do sobrenome. Mas os pais de Cholesky eram poloneses e, em polonês, deveria ter sido pronunciado com [ ]. Felicidades.

χ

$\chi$

Ameba diz Reinstate Monica

Sim ... eu pensei que, como um russo com um nome polonês, e depois de ler o alfabeto ortográfico por mais ou menos uma década antes de vê-lo grafado em letras latinas, eu teria alguma idéia de como pronunciá-lo;)

Stask

Quem se importa com a pronúncia, basta usar a maldita coisa.

Mark L. Stone

A resposta para isso depende do campo em que você está. Se você é matemático, todas as normas em dimensões finitas são equivalentes : para quaisquer duas normas e , existem existem constantes , que dependem apenas da dimensão (e a, b), de modo que: $\|\cdot\|_a$ $\|\cdot\|_b$ $C_1,C_2$

C_{1} ‖ x ‖_{b} \leq ‖ x ‖_{a} \leq C_{2} ‖ x ‖_{b} .

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

Isso implica que as normas em dimensões finitas são bastante entediantes e não há essencialmente nenhuma diferença entre elas, exceto na forma como elas são dimensionadas. Isso geralmente significa que você pode escolher a norma mais conveniente para o problema que está tentando resolver . Normalmente, você deseja responder perguntas como "este operador ou procedimento é limitado" ou "esse processo numérico converge". Com a limitação, você normalmente só se importa que algo seja finito. Com a convergência, sacrificando a taxa na qual você tem convergência, você pode optar por usar uma norma mais conveniente.

Por exemplo, na álgebra linear numérica, a norma Frobenius às vezes é preferida porque é muito mais fácil de calcular do que a norma euclidiana, e também que ela se conecta naturalmente a uma classe mais ampla de operadores de Hilbert Schmidt . Além disso, como a norma euclidiana, é submultiplicativa: , ao contrário da norma max, por isso permite que você fale facilmente sobre a multiplicação de operadores em qualquer local o espaço em que você está trabalhando. As pessoas tendem a gostar muito da norma e da norma Frobenius porque têm relações naturais com os valores próprios e com os valores singulares das matrizes, além de serem sub-multiplicadoras. $\|AB\|_F\leq \|A\|_F\|B\|_F$ $p=2$

Para fins práticos , as diferenças entre normas se tornam mais acentuadas porque vivemos em um mundo de dimensões e, geralmente, importa quão grande é uma certa quantidade e como é medida. Essas constantes acima não são exatamente justas, portanto, torna-se importante quanto mais ou menos uma determinada norma é comparada a . $C_1,C_2$ $\|x\|_a$ $\|x\|_b$

Alex R.
fonte

Infelizmente, o termo "equivalência", como nas normas, pode e foi mal interpretado, inclusive por pessoas com Ph.Ds em Ciência da Computação. Eu precisava implementar um certo cálculo não trivial usando uma norma 2, e esse cara produziu uma solução usando uma norma 1, porque isso era muito mais fácil e, afinal, ele ouviu que todas as normas são equivalentes. Bem, estar desabilitado por um fator de (até) não era adequado para mim. Nessa aplicação, eu só podia me dar ao luxo de estar fora de um fator a 1. #

\sqrt{n}

$\sqrt{n}$

Mark L. Stone

@ MarkL.Stone: Certo, daí a distinção entre teórico (realmente: topológico) e prático.

Alex R.

@ MarkL.Stone: +1 Claramente ele não estava testando seu código de unidade. :) (Bela anedota! Definitivamente vou usá-lo quando falamos de falhas de comunicação na computação técnica!)

usεr11852 diz Reinstate Monic

@ usεr11852 ha ha, não, é pior que isso. Ele fez o "teste unitário" do código, implementando corretamente o cálculo com base na norma 1. Falhou no meu exame no nível do sistema porque usava a norma errada.

22716 Mark-Stone Stone

@ MarkL.Stone: Oh ... que pena! Dito isto, não sei se você estava usando uma configuração de hardware específica ou algo assim, mas começar com a codificação de um cálculo de norma do zero é não-não; existem bibliotecas de matemática que se deve usar para evitar esses problemas completamente.

usεr11852 diz Reinstate Monic