¿Por qué son tan importantes el simétricos matrices de (SPD) definidas positivas?

Question

Sé que la definición de simétrica positiva definida (SPD) de la matriz, pero quiere entender más.

Por qué son tan importantes, intuitivamente?

Aquí es lo que yo sé. ¿Y qué más?

• Para un dado de datos, Co-varianza de la matriz es el SPD. Co-varianza de la matriz es una medida importante, de ver este excelente post de explicación intuitiva.

• La forma cuadrática $\frac 1 2 x^\top Ax-b^\top x +c$ es convexo, si $A$ es SPD. Convexo es un buen hotel para una función que puede asegurarse de que la solución local es la solución global. Para problemas Convexos, hay muchos buenos algoritmos para resolver, pero no para no convexos problemas.

• Al $A$ es SPD, la solución de optimización de la forma cuadrática $$\text{minimize}~~~ \frac 1 2 x^\top Ax-b^\top x +c$$ and the solution for linear system $$Ax=b$$ son los mismos. Así que se pueden ejecutar conversiones entre los dos problemas clásicos. Esto es importante porque nos permite utilizar los trucos descubiertos en un dominio a otro. Por ejemplo, podemos utilizar el método del gradiente conjugado para resolver un sistema lineal.

• Hay muchos buenos algoritmos (rápido, numérico estable) funciona mejor para el SPD de la matriz, tales como la descomposición de cholesky.

EDIT: no estoy tratando de pedir las identidades para el SPD de la matriz, pero la intuición detrás de la propiedad para mostrar la importancia. Por ejemplo, como menciona @Mateo Drury, si una matriz es el SPD, los Autovalores son todos los números reales positivos, pero ¿por qué todos positiva de la materia. @Mateo Drury tenido una gran respuesta a fluir y que es lo que estaba buscando.

Answer 1

Un (verdadero) matriz simétrica tiene un completo conjunto ortogonal de vectores propios para que los correspondientes autovalores son todos los números reales. Para los no-simétrica matrices pueden fracasar. Por ejemplo, una rotación en el espacio de dos dimensiones no tiene vector propio o autovalores de los números reales, se debe pasar a un espacio vectorial sobre el de los números complejos para encontrarlos.

Si la matriz es, además, positiva definida, entonces estos autovalores son todos los números reales positivos. Este hecho es mucho más fácil que la primera, porque si $v$ es un autovector con unidad de longitud, y $\lambda$ el correspondiente autovalor, entonces

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

donde la última igualdad se utiliza la definición positiva de la certeza.

La importancia de la intuición es que los vectores propios y valores propios de una transformación lineal que describa el sistema de coordenadas en el que la transformación es más fácil de comprender. Una transformación lineal puede ser muy difícil de entender en una forma "natural" como el estándar de sistema de coordenadas, pero cada uno viene con un "preferidas" de la base de vectores propios en los que la transformación actúa como una escala en todas las direcciones. Esto hace que la geometría de la transformación mucho más fácil de entender.

Por ejemplo, la prueba de la segunda derivada para extremos locales de una función de $R^2 \rightarrow R$ a menudo se administra como una serie de misteriosos condiciones que impliquen una entrada en la segunda derivada de la matriz y de algunos determinantes. De hecho, estas condiciones simplemente codificar el siguiente geométrica de observación:

• Si la matriz de las segundas derivadas es positiva definida, usted está en un mínimo local.
• Si la matriz de las segundas derivadas es negativo definitiva, estás en un máximo local.
• De lo contrario, en ninguno de los dos, un punto de silla.

Usted puede entender esto con el geométrico razonamiento anteriormente en un eigenbasis. La primera derivada en un punto crítico que se desvanece, por lo que las tasas de cambio de la función aquí están controlados por la segunda derivada. Ahora podemos razón geométricamente

• En el primer caso hay dos eigen-las direcciones, y si se mueven a lo largo de la función aumenta.
• En la segunda, dos eigen-las direcciones, y si se mueven, ya sea en la función disminuye.
• En la última, hay dos eigen-las direcciones, pero en uno de ellos la función aumenta y en otras disminuye.

Puesto que los vectores propios ocupar la totalidad del espacio, cualquier otra dirección es una combinación lineal de eigen-las direcciones, por lo que las tasas de cambio en esas direcciones son combinaciones lineales de las tasas de cambio en el eigen direcciones. Así que, de hecho, esto se aplica en todas las direcciones (esto es más o menos lo que significa para una función definida en un espacio de dimensiones superiores para ser diferenciable). Ahora bien, si se dibuja un poco la imagen en tu cabeza, esto hace un montón de sentido de algo que es muy misteriosa en principiante cálculo de los textos.

Esto se aplica directamente a uno de los puntos de bala

La forma cuadrática $\frac 1 2 x^\top Ax-b^\top x +c$ es convexo, si $A$ es SPD. Convexo es una agradable propiedad que puede asegurarse de que la solución local es la solución global

La matriz de las segundas derivadas es $A$ en todas partes, que es simétrica positiva definida. Geométricamente, esto significa que si nos alejamos en cualquier eigen-dirección (y por lo tanto cualquier dirección, porque cualquier otro es una combinación lineal de eigen-direcciones) de la propia función se doble de distancia por encima de lo plano tangente. Esto significa que toda la superficie es convexa.

Answer 2

Usted encontrará algunas de las de la intuición en las muchas formas elementales de mostrar los valores propios de una verdadera matriz simétrica son reales: http://mathoverflow.net/questions/118626/real-symmetric-matrix-has-real-eigenvalues-elementary-proof/118640#118640

En particular, la forma cuadrática $x^TAx$ se produce de forma natural en el cociente de Rayleigh, y simétrica matrices de proporcionar lo que es posiblemente la forma más natural de exhibir una gran familia de matrices cuyos autovalores son reales. Ver el Courant teorema minimax por ejemplo: https://en.wikipedia.org/wiki/Courant_minimax_principle

También simétrica, estrictamente positiva definida matrices son el único conjunto de matrices que pueden definir un no-trivial interior del producto, junto con un inducida por la norma: $d(x,y)=\langle x,Ay\rangle=x^TAy$. Esto es debido a que por definición real vectores $x,y$ $d(x,y)=d(y,x)$ para todos los $x,y$$\|x\|^2=x^TAx>0$$x\neq 0$. De esta manera, simétrica positiva definida matrices pueden ser vistos como candidatos ideales para coordinar transforma.

Esta última propiedad es absolutamente clave en el área de máquinas de soporte vectorial , específicamente métodos del núcleo y el núcleo truco, donde el núcleo debe ser simétrica positiva para inducir el derecho interno del producto. De hecho, Mercer teorema generaliza la intuitiva de las propiedades de las matrices simétricas a espacios funcionales.

Answer 3

Con respecto a la optimización (porque has etiquetado a su pregunta con la etiqueta de optimización), SPD matrices son extremadamente importantes para una simple razón - un SPD de Hess garantiza que la dirección de búsqueda es un descenso de la dirección. Considerar la derivación de Newton el método de optimización sin restricciones. Primero, se forma la expansión de Taylor de $f(x + \Delta 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$$

Siguiente, tomamos la derivada con respecto al $\Delta x$:

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

Finalmente, el conjunto de la derivada es igual a 0 y resolver para $\Delta x$:

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

Asumiendo $\nabla^2 f(x)$ es SPD, es fácil ver que $\Delta x$ es un descenso de la dirección debido a que:

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

Cuando se utiliza el método de Newton, no SPD de Hess matrices son típicamente "codazo" para ser SPD. Hay una casa algoritmo de Cholesky modificada de que se detecte una no-SPD Hesse, "empujón" de forma adecuada en la dirección correcta y factorizar el resultado, para todos (esencialmente) el mismo costo de una factorización de Cholesky. Cuasi-Newton métodos para evitar este problema, forzando al aproximada de Hess a ser SPD.

Como un aparte, simétrica indefinido sistemas están recibiendo mucha atención en estos días. Vienen en el contexto de punto interior métodos de optimización restringida.

Answer 4

Geométricamente, una positiva definida la matriz define una métrica, por ejemplo, una métrica de Riemann, por lo que inmediatamente puede usar conceptos geométricos.

Si $x$ $y$ son vectores y $A$ una matriz positiva definida, entonces $$ d(x,y) = (x-y)^T (x-y) $$ es una métrica (también llamada función de distancia).

Además, positiva definida matrices están relacionados con el iner producto: En $\mathbb{R}^n$, podemos definir un producto interior por $$ \langle x,y \rangle = x^T T T T T $$ donde $A$ como es arriba es positiva definida. Más, todos los interiores de los productos en $\mathbb{R}^n$ surge de esta manera.

Answer 5

A menudo subestimada truco es simétrica matrices fácilmente permitan calcular la matriz exponencial. Si bien es cierto que en general hay "19 Dudosa Maneras de Calcular la Matriz Exponencial" (Cleve Moler & Charles Van Loan), simétrica matrices, y por lo tanto el SPD matrices, tienen la propiedad de que la descomposición espectral puede ser utilizado para calcular la matriz exponencial precisa y en un numéricamente estable.* Considerar la factorización $A=PDP^{-1}$ donde $P$ es una matriz de vectores propios y $D$ es una matriz diagonal de valores propios. Debido a $A$ es simétrica, lo que significa $P$ es ortonormales: $P^T=P^{-1}$. La matriz exponencial puede ser computado como $\exp(A)=P\exp(D)P^T,$ donde $D$ puede ser barato calculada por exponentiating todos los elementos a lo largo de la diagonal. Las pruebas de este método puede ser convstructed por la definición de la función exponencial como una potencia de la serie.

De hecho, muchos otros cálculos puede ser calculada de la misma manera. Inversas y una cierta idea de una "matriz de la raíz cuadrada" puede ser calculada mediante la aplicación de la función deseada a la diagonal. En general, este método para calcular la inversa o "raíz cuadrada" no es tremendamente eficientes (dos multiplicación de la matriz de operaciones, la inversión de las operaciones, y la descomposición espectral de sí mismo), pero puede ser útil si usted ya tiene que calcular la descomposición espectral ya por alguna otra razón.

*Este truco no funciona tan bien cuando las matrices son defectuosos o casi defectuoso: el error se acumula a ser muchas veces mayor que la precisión de la máquina. Esto se discute en detalle en el Moler Y Van Loan artículo.