Por que as matrizes simétricas positivas definidas (SPD) são tão importantes?

20

Conheço a definição de matriz simétrica positiva definida (SPD), mas quero entender mais.

Por que eles são tão importantes, intuitivamente?

Aqui está o que eu sei. O quê mais?

Para um dado dado, a matriz de co-variância é SPD. Matriz de co-variância é uma métrica importante; consulte este excelente post para obter uma explicação intuitiva.
A forma quadrática é convexa, se for SPD. A convexidade é uma propriedade interessante para uma função que pode garantir que a solução local seja global. Para problemas convexos, existem muitos bons algoritmos a serem resolvidos, mas não para problemas que não sejam de covex. $\frac 1 2 x^\top Ax-b^\top x +c$ $A$
Quando é SPD, a solução de otimização para a forma quadrática solução para o sistema linear são as mesmas. Para que possamos executar conversões entre dois problemas clássicos. Isso é importante porque nos permite usar truques descobertos em um domínio no outro. Por exemplo, podemos usar o método do gradiente conjugado para resolver um sistema linear. $A$
$minimize \frac{1}{2} x^{⊤} A x - b^{⊤} x + c$ $\text{minimize}~~~ \frac 1 2 x^\top Ax-b^\top x +c$ $A x = b$ $Ax=b$
Existem muitos bons algoritmos (rápidos, estáveis numéricos) que funcionam melhor para uma matriz SPD, como a decomposição de Cholesky.

EDIT: Não estou tentando perguntar as identidades da matriz SPD, mas a intuição por trás da propriedade para mostrar a importância. Por exemplo, como mencionado por Matthew Drury, se uma matriz é SPD, os autovalores são todos números reais positivos, mas por que todos são positivos. @ Matthew Drury teve uma ótima resposta para fluir e era isso que eu estava procurando.

mathematical-statistics optimization covariance-matrix intuition linear-algebra Haitao Du
fonte

7

Os autovalores são todos números reais positivos. Este fato está subjacente a muitos dos outros.

Matthew Drury

4

Para ir um pouco além do @ Matthew: Se você escolher uma base adequada, todas essas matrizes são iguais e iguais à matriz de identidade. Em outras palavras, existe exatamente uma forma quadrática definida positiva em cada dimensão (para espaços vetoriais reais) e é igual à distância euclidiana.

whuber

2

Você encontrará alguma intuição nas muitas maneiras elementares de mostrar que os autovalores de uma matriz simétrica real são reais: mathoverflow.net/questions/118626/… Em particular, a forma quadrática

ocorre naturalmente no quociente de Rayleigh, e matrizes simétricas fornecem uma maneira natural de exibir uma grande família de matrizes cujos autovalores são reais. Veja o teorema de Courant minimax, por exemplo: en.wikipedia.org/wiki/Courant_minimax_principle

x^{T} A x

$x^TAx$

Alex R.

4

Isso parece excessivamente amplo; se ainda não tivesse três respostas, eu provavelmente o teria fechado nessa base. Por favor, oferecer mais orientação sobre o que você quer especificamente saber (pedindo a intuição é demasiado pessoal / individual para as pessoas a adivinhar em um caso como este)

Glen_b -Reinstate Monica

1

Estou tendo dificuldade em apresentar uma situação nas estatísticas que daria origem a uma matriz que não é psd (a menos que você estragasse o cálculo de uma matriz de correlação, por exemplo, preenchendo-a com correlação pareada, calculada em dados com valores ausentes) . Qualquer matriz quadrada simétrica que eu possa pensar é uma covariância, uma informação ou uma matriz de projeção. (Em outra parte em matemática aplicada, as matrizes não-PSD pode ser uma norma cultural, por exemplo, as matrizes de elementos finitos em PDE, dizem.)

Stask

15

Uma matriz simétrica (real) possui um conjunto completo de vetores próprios ortogonais para os quais os valores próprios correspondentes são todos números reais. Para matrizes não simétricas, isso pode falhar. Por exemplo, uma rotação no espaço bidimensional não possui vetor próprio ou valores próprios nos números reais; você deve passar para um espaço vetorial sobre os números complexos para encontrá-los.

Se a matriz é adicionalmente positiva, então esses valores próprios são todos números reais positivos. Esse fato é muito mais fácil que o primeiro, pois se é um vetor próprio com comprimento unitário e o valor próprio correspondente, $v$ $\lambda$

λ = λ v^{t} v = v^{t} A v > 0

$\lambda = \lambda v^t v = v^t A v > 0$

onde a última igualdade usa a definição de definição positiva.

A importância aqui para a intuição é que os autovetores e autovalores de uma transformação linear descrevem o sistema de coordenadas em que a transformação é mais facilmente compreendida. Uma transformação linear pode ser muito difícil de entender em uma base "natural", como o sistema de coordenadas padrão, mas cada um vem com uma base "preferida" de vetores próprios, nos quais a transformação atua como uma escala em todas as direções. Isso facilita muito a compreensão da geometria da transformação.

Por exemplo, o segundo teste derivado para o extremo local de uma função é frequentemente administrada como uma série de condições que envolvem uma entrada misteriosa na segunda matriz derivado e alguns determinantes. De fato, essas condições simplesmente codificam a seguinte observação geométrica: $R^2 \rightarrow R$

Se a matriz das segundas derivadas for definida positivamente, você estará no mínimo local.
Se a matriz das segundas derivadas for negativa definida, você estará no máximo local.
Caso contrário, você não estará em um ponto de sela.

Você pode entender isso com o raciocínio geométrico acima em uma base própria. A primeira derivada em um ponto crítico desaparece, portanto as taxas de mudança da função aqui são controladas pela segunda derivada. Agora podemos raciocinar geometricamente

No primeiro caso, existem duas direções próprias e, se você se mover, a função aumenta.
No segundo, duas direções próprias, e se você se mover, a função diminuirá.
No último, existem duas direções próprias, mas em uma delas a função aumenta e na outra diminui.

Como os vetores próprios abrangem todo o espaço, qualquer outra direção é uma combinação linear de direções próprias, de modo que as taxas de mudança nessas direções são combinações lineares das taxas de mudança nas direções próprias. Portanto, de fato, isso vale para todas as direções (isso é mais ou menos o que significa para uma função definida em um espaço dimensional mais alto ser diferenciável). Agora, se você desenhar uma pequena figura na sua cabeça, isso faz muito sentido com algo que é bastante misterioso nos textos de cálculo para iniciantes.

Isso se aplica diretamente a um dos seus marcadores

A forma quadrática é convexo, sefor SPD. Convex é uma propriedade agradável que pode garantir que a solução local seja uma solução global $\frac 1 2 x^\top Ax-b^\top x +c$ $A$

A matriz das segundas derivadas é toda parte, que é simétrica positiva definida. Geometricamente, isso significa que, se nos afastarmos em qualquer direção eigen (e, portanto, em qualquer direção, porque qualquer outra é uma combinação linear de direções eigen), a própria função se dobrará acima do plano tangente. Isso significa que toda a superfície é convexa. $A$

Matthew Drury
fonte

5

Uma maneira gráfica de ver: se

é SPD, os contornos da forma quadrática associada são elipsoidais.

A

$\mathbf A$

JM não é estatístico

7

Essa caracterização por @JM é muito perspicaz. Caso alguém esteja se perguntando o que pode ser especial sobre contornos elipsoidais, observe que elas são apenas esferas perfeitas disfarçadas: as unidades de medida podem diferir ao longo de seus eixos principais e os elipsóides podem ser rotacionados em relação às coordenadas nas quais os dados são descritos , mas para muitas finalidades - especialmente conceituais - essas diferenças são irrelevantes.

whuber

Isso está relacionado à minha maneira de entender o método de Newton geometricamente. Melhor aproximar o nível atual definido com um elipsóide e, em seguida, usar um sistema de coordenadas em que o elipsóide é um círculo, mova-se ortogonal ao círculo nesse sistema de coordenadas.

Matthew Drury

1

Se houver restrições (ativas), você precisará projetar no jacobiano as restrições ativas antes de executar o autovalor e o intervalo de seleção automática. Se o hessiano é psd, a (qualquer) projeção será psd, mas o inverso não é necessariamente verdadeiro, e geralmente não é. Veja minha resposta.

Mark L. Stone

10

Você encontrará alguma intuição nas várias maneiras elementares de mostrar que os autovalores de uma matriz simétrica real são reais: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- prova / 118640 # 118640

Em particular, a forma quadrática ocorre naturalmente no quociente de Rayleigh e as matrizes simétricas fornecem a maneira mais natural de exibir uma grande família de matrizes cujos valores próprios são reais. Veja o teorema de Courant minimax, por exemplo: https://en.wikipedia.org/wiki/Courant_minimax_principle $x^TAx$

Além disso, as matrizes simétricas definidos estritamente positivos são o único conjunto de matrizes, que podem definir um produto interno não-trivial, juntamente com uma norma induzida: . Isso ocorre porque, por definição, para vetores reais para todos os e $d(x,y)=\langle x,Ay\rangle=x^TAy$ $x,y$ $d(x,y)=d(y,x)$ $x,y$ para . Dessa maneira, matrizes definidas positivas simétricas podem ser vistas como candidatas ideais para transformações de coordenadas. $\|x\|^2=x^TAx>0$ $x\neq 0$

Essa última propriedade é absolutamente essencial na área de máquinas de vetores de suporte, especificamente métodos do kernel e o truque do kernel , onde o kernel deve ser positivo simétrico para induzir o produto interno correto. De fato, o teorema de Mercer generaliza as propriedades intuitivas de matrizes simétricas para espaços funcionais.

Alex R.
fonte

9

Com relação à otimização (porque você marcou sua pergunta com a tag de otimização), as matrizes SPD são extremamente importantes por um motivo simples - um SPD Hessian garante que a direção da pesquisa é uma direção descendente. Considere a derivação do método de Newton para otimização irrestrita. Primeiro, formamos a expansão de Taylor de : $f(x + \Delta x)$

f (x + Δ x) \approx f (x) + Δ x^{T} \nabla f (x) + \frac{1}{2} Δ x^{T} \nabla^{2} f (x) Δ x

$f(x + \Delta x)\approx f(x) + \Delta x^T \nabla f(x)+ \frac{1}{2} \Delta x^T \nabla^2 f(x) \Delta x$

Em seguida, tomamos a derivada em relação a : $\Delta x$

f^{'} (x + Δ x) \approx \nabla f (x) + \nabla^{2} f (x) Δ x

$f'(x + \Delta x)\approx \nabla f(x) + \nabla^2 f(x) \Delta x$

Finalmente, defina a derivada igual a 0 e resolva para : $\Delta x$

Δ x = - \nabla^{2} f (x)^{- 1} \nabla f (x)

$\Delta x = -\nabla^2 f(x)^{-1} \nabla f(x)$

Supondo que é SPD, é fácil ver que é uma direção de descida porque: $\nabla^2 f(x)$ $\Delta x$

\nabla f (x)^{T} Δ x = - \nabla f (x)^{T} \nabla^{2} f (x)^{- 1} \nabla f (x) < 0

$\nabla f(x)^T \Delta x = -\nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) < 0$

Ao usar o método de Newton, as matrizes não-SPD Hessian são tipicamente "empurradas" para serem SPD. Existe um algoritmo interessante chamado Cholesky modificado que detecta um Hessian não-SPD, "cutuca" adequadamente na direção certa e fatora o resultado, tudo por (essencialmente) o mesmo custo que uma fatoração de Cholesky. Os métodos quase-Newton evitam esse problema forçando o Hessiano aproximado a ser SPD.

Como um aparte, sistemas simétricos indefinidos estão recebendo muita atenção nos dias de hoje. Eles surgem no contexto de métodos de pontos interiores para otimização restrita.

Bill Woessner
fonte

Muito obrigado pela ótima resposta. Entendo que uma direção decente é importante no método de pesquisa de linha. Nos métodos da região de confiança, uma direção decente também é importante?

Haitao Du

1

Ainda é importante para os métodos da região de confiança. Os métodos da região de confiança basicamente funcionam limitando o tamanho da etapa PRIMEIRO e depois resolvendo a direção da etapa. Se a etapa não atingir a diminuição desejada no valor da função objetiva, você reduz o limite no tamanho da etapa e inicia novamente. Imagine que seu algoritmo para gerar a direção da etapa não garante que a direção da etapa seja uma direção de descida. Mesmo que o raio da região de confiança vá para 0, você nunca poderá gerar uma etapa aceitável (mesmo que exista), porque nenhuma das direções da sua etapa é de descida.

Bill Woessner

Os métodos de pesquisa de linha exibem basicamente o mesmo comportamento. Se a direção da pesquisa não for uma direção descendente, o algoritmo de pesquisa de linha poderá nunca encontrar um comprimento aceitável de etapa - porque não existe. :-)

Bill Woessner

Ótima resposta, obrigado por me ajudar a conectar as peças.

Haitao Du

9

Geometricamente, uma matriz definida positiva define uma métrica , por exemplo, uma métrica Riemanniana, para que possamos usar imediatamente conceitos geométricos.

$x$ $y$ $A$

d (x, y) = \sqrt{(x - y)^{T} A (x - y)}

$d(x,y) = \sqrt{(x-y)^T A (x-y)}$

$\mathbb{R}^n$

⟨ x, y ⟩ = x^{T} A y

$\langle x,y \rangle = x^T A y$

A

$A$

R^{n}

$\mathbb{R}^n$

kjetil b halvorsen
fonte

1

A = I

$\mathbf A=\mathbf I$

6

Já existem várias respostas que explicam por que matrizes definidas positivas simétricas são tão importantes, portanto, fornecerei uma resposta explicando por que elas não são tão importantes quanto algumas pessoas, incluindo os autores de algumas dessas respostas, pensam. Por uma questão de simplicidade, limitarei o foco às matrizes simétricas e me concentrarei nos hessianos e na otimização.

Se Deus tivesse tornado o mundo convexo, não haveria otimização convexa, apenas haveria otimização. Da mesma forma, não haveria matrizes definidas positivas (simétricas), apenas matrizes (simétricas). Mas não é esse o caso, então lide com isso.

Se um problema de programação quadrática for convexo, ele poderá ser resolvido "facilmente". Se não for convexo, ainda é possível encontrar um ótimo global usando métodos branch e bound (mas pode demorar mais e mais memória).

Se um método de Newton é usado para otimização e o Hessian em alguma iteração é indefinido, não é necessário "finagle" para uma definição positiva. Se estiver usando uma pesquisa de linha, as direções de curvatura negativa podem ser encontradas e a pesquisa de linha executada ao longo delas, e se estiver usando uma região de confiança, haverá uma região de confiança pequena o suficiente para que a solução do problema da região de confiança atinja a descida.

Quanto aos métodos Quasi-Newton, o BFGS (amortecido se o problema for restrito) e o DFP mantêm uma definição positiva da aproximação Hessiana ou inversa Hessiana. Outros métodos quase-Newton, como SR1 (classificação simétrica um), não necessariamente mantêm uma definição positiva. Antes de você ficar completamente deformado com isso, essa é uma boa razão para escolher SR1 para muitos problemas - se o Hessian realmente não for definido positivamente ao longo do caminho para o ideal, forçando a aproximação Quasi-Newton a ser definida positivamente. pode resultar em uma péssima aproximação quadrática da função objetivo. Por outro lado, o método de atualização SR1 é "solto como um ganso" e pode transformar sua definição com firmeza à medida que avança.

Para problemas de otimização não-linearmente restritos, o que realmente importa não é o hessiano da função objetivo, mas o hessiano do lagrangiano. O Hessiano do Lagrangiano pode ser indefinido, mesmo no ideal (e), e de fato é apenas a projeção do Hessiano do Lagrangiano no espaço nulo do Jacobiano das restrições ativas (lineares e não-lineares) que precisam ser semi-positivas -definido no melhor. Se você modelar o Hessiano do Lagrangiano via BFGS e, assim, restringi-lo a uma definição positiva, pode ser um ajuste terrível em todos os lugares, e não funcionar bem. Por outro lado, o SR1 pode adaptar seus valores próprios ao que realmente "vê".

Há muito mais que eu poderia dizer sobre tudo isso, mas isso é suficiente para lhe dar um sabor.

Edit : O que eu escrevi 2 parágrafos acima está correto. No entanto, esqueci de salientar que isso também se aplica a problemas com restrições lineares. No caso de problemas linearmente limitados, o hessiano do lagrangiano é apenas (reduz a) o hessiano da função objetivo. Portanto, a condição de otimização de 2ª ordem para um mínimo local é que a projeção do Hessiano da função objetiva no espaço nulo do Jacobiano das restrições ativas seja semi-definida positiva. Mais notavelmente, o hessiano da função objetivo não precisa (necessariamente) ser psd no ideal, e muitas vezes não é, mesmo em problemas linearmente restritos.

Mark L. Stone
fonte

"Quem tem medo de funções de perda não convexa?" ... não @ MarkL.Stone

GeoMatt22

@ GeoMatt22 Você apostou seu @ $$ eu não sou. Por outro lado, se você deseja criar (escolher) uma função de perda, não há necessidade de torná-la não convexa quando ela não serve a nenhum outro propósito que não seja o show-boating. Discrição é a melhor parte do valor.

Mark L. Stone

@ Mark L. Stone: Isso é interessante! Você pode fazer referência a alguma literatura onde eu posso ler sobre essas coisas?

Kjetil b halvorsen 01/10/16

@kjetil b halvorsen. Pesquisa de linha com direções de curvatura negativa folk.uib.no/ssu029/Pdf_file/Curvilinear/More79.pdf . As regiões de confiança são abordadas em muitos livros e documentos. Conhecido livro com boa introdução para as regiões de confiança é amazon.com/... .. livro monstro, um pouco fora de data agora, é epubs.siam.org/doi/book/10.1137/1.9780898719857 . Quanto ao meu último parágrafo sobre condições de otimização, leia sobre condições de 2ª ordem KKT

Mark L. Stone

@kjetil b halvorsen Não mencionei em encontrar o ideal global do programa quadrático não convexo. Software amplamente disponível, como o CPLEX, pode fazer isso, consulte ibm.com/support/knowledgecenter/SS9UKU_12.6.1/… . Obviamente, nem sempre é rápido e pode precisar de alguma memória. Resolvi para a otimização global alguns problemas de minimização do QP com dezenas de milhares de variáveis que tinham várias centenas de valores próprios de magnitude significativa.

Mark L. Stone

5

Você já citou várias razões pelas quais o SPD é importante, mas ainda assim postou a pergunta. Então, parece-me que você precisa responder a essa pergunta primeiro: por que quantidades positivas são importantes?

Minha resposta é que algumas quantidades devem ser positivas para se reconciliar com nossas experiências ou modelos. Por exemplo, as distâncias entre itens no espaço devem ser positivas. As coordenadas podem ser negativas, mas as distâncias são sempre não negativas. Portanto, se você tem um conjunto de dados e algum algoritmo que o processa, é possível que você acabe com um que quebra quando você alimenta uma distância negativa nele. Então, você diz "meu algoritmo exige entradas de distância positivas o tempo todo" e não soaria como uma demanda irracional.

\sum_{i} (x_{i} - μ)^{2} / n

$\sum_i (x_i-\mu)^2/n$ É óbvio a partir da definição que, se você alimentar os números reais

x_{i}

$x_i$ na equação a saída é sempre não-negativa. Portanto, você pode criar algoritmos que funcionem com números não negativos e eles podem ser mais eficientes que o algoritmo sem essa restrição. Essa é a razão pela qual os usamos.

Portanto, matrizes de variância-covariância são semidefinidas positivas, isto é, "não-negativas" nessa analogia. O exemplo de um algoritmo que requer essa condição é a decomposição de Cholesky, é muito útil. É freqüentemente chamada de "raiz quadrada da matriz". Assim, como a raiz quadrada de um número real que requer não-negatividade, Cholesky quer matrizes não-negativas. Não encontramos essa restrição ao lidar com matrizes de covariância, porque sempre são.

Então, essa é a minha resposta utilitária. As restrições, como não negatividade ou SPD, permitem criar algoritmos de cálculo mais eficientes ou ferramentas de modelagem convenientes, disponíveis quando suas entradas satisfazem essas restrições.

Aksakal
fonte

3

Aqui estão mais duas razões que não foram mencionadas pelas quais as matrizes semidefinidas positivas são importantes:

A matriz laplaciana gráfica é diagonalmente dominante e, portanto, PSD.
A semidefinitividade positiva define uma ordem parcial no conjunto de matrizes simétricas (essa é a base da programação semidefinida).

Thoth
fonte

Por que as matrizes simétricas positivas definidas (SPD) são tão importantes?

Respostas: