Pourquoi les matrices symétriques positives définies (SPD) sont-elles si importantes?

20

Je connais la définition de la matrice définie positive symétrique (SPD), mais je veux en savoir plus.

Pourquoi sont-ils si importants, intuitivement?

Voici ce que je sais. Quoi d'autre?

  • Pour une donnée donnée, la matrice de co-variance est SPD. La matrice de co-variance est une métrique importante, voir cet excellent article pour une explication intuitive.

  • La forme quadratique est convexe, si est SPD. La convexité est une belle propriété pour une fonction qui peut s'assurer que la solution locale est une solution globale. Pour les problèmes convexes, il existe de nombreux bons algorithmes à résoudre, mais pas pour les problèmes non covex.12xAxbx+cA

  • Lorsque est SPD, la solution d'optimisation pour la forme quadratique et la solution pour le système linéaire sont les mêmes. Nous pouvons donc exécuter des conversions entre deux problèmes classiques. C'est important car cela nous permet d'utiliser des astuces découvertes dans un domaine dans l'autre. Par exemple, nous pouvons utiliser la méthode du gradient conjugué pour résoudre un système linéaire.A

    minimize   12xAxbx+c
    Ax=b
  • Il existe de nombreux bons algorithmes (rapides, stables numériquement) qui fonctionnent mieux pour une matrice SPD, comme la décomposition de Cholesky.

EDIT: Je n'essaie pas de demander les identités pour la matrice SPD, mais l'intuition derrière la propriété pour montrer l'importance. Par exemple, comme mentionné par @Matthew Drury, si une matrice est SPD, les valeurs propres sont toutes des nombres réels positifs, mais pourquoi tout positif est important. @Matthew Drury avait une excellente réponse à donner et c'est ce que je cherchais.

Haitao Du
la source
7
Les valeurs propres sont toutes des nombres réels positifs. Ce fait sous-tend de nombreux autres.
Matthew Drury
4
Pour aller un peu plus loin que @Matthew: Si vous choisissez une base appropriée, toutes ces matrices sont les mêmes et sont égales à la matrice d'identité. En d'autres termes, il y a exactement une forme quadratique définie positive dans chaque dimension (pour les espaces vectoriels réels) et c'est la même chose que la distance euclidienne.
whuber
2
Vous trouverez une certaine intuition dans les nombreuses façons élémentaires de montrer que les valeurs propres d'une matrice symétrique réelle sont toutes réelles: mathoverflow.net/questions/118626/… En particulier, la forme quadratique se produit naturellement dans le quotient de Rayleigh, et les matrices symétriques offrent un moyen naturel d'exposer une grande famille de matrices dont les valeurs propres sont réelles. Voir le théorème de Courant minimax par exemple: en.wikipedia.org/wiki/Courant_minimax_principlexTAx
Alex R.
4
Cela semble trop large; s'il n'avait pas déjà trois réponses, je l'aurais probablement fermé sur cette base. Veuillez offrir plus de conseils sur ce que vous voulez spécifiquement savoir (demander l'intuition est beaucoup trop personnel / individuel pour que les gens le devinent dans un cas comme celui-ci)
Glen_b -Reinstate Monica
1
J'ai du mal à trouver une situation dans les statistiques qui donnerait lieu à une matrice qui n'est pas psd (sauf si vous avez foiré dans le calcul d'une matrice de corrélation, par exemple en la remplissant avec une corrélation par paire calculée sur des données avec des valeurs manquantes) . N'importe quelle matrice symétrique carrée à laquelle je peux penser est soit une covariance, une information ou une matrice de projection. (Ailleurs en mathématiques appliquées, les matrices non psd peuvent être une norme culturelle, par exemple les matrices d'éléments finis en PDE, par exemple.)
StasK

Réponses:

15

Une matrice symétrique (réelle) possède un ensemble complet de vecteurs propres orthogonaux pour lesquels les valeurs propres correspondantes sont toutes des nombres réels. Pour les matrices non symétriques, cela peut échouer. Par exemple, une rotation dans un espace bidimensionnel n'a pas de vecteur propre ou de valeurs propres dans les nombres réels, vous devez passer à un espace vectoriel sur les nombres complexes pour les trouver.

Si la matrice est en outre définie positive, ces valeurs propres sont toutes des nombres réels positifs. Ce fait est beaucoup plus facile que le premier, car si est un vecteur propre avec une longueur unitaire, et la valeur propre correspondante, alorsvλ

λ=λvtv=vtAv>0

où la dernière égalité utilise la définition du caractère définitif positif.

L'importance ici pour l'intuition est que les vecteurs propres et les valeurs propres d'une transformation linéaire décrivent le système de coordonnées dans lequel la transformation est la plus facilement comprise. Une transformation linéaire peut être très difficile à comprendre dans une base «naturelle» comme le système de coordonnées standard, mais chacune est accompagnée d'une base «préférée» de vecteurs propres dans laquelle la transformation agit comme une mise à l'échelle dans toutes les directions. Cela rend la géométrie de la transformation beaucoup plus facile à comprendre.

Par exemple, le test de dérivée seconde pour les extrema locaux d'une fonction est souvent donné comme une série de conditions mystérieuses impliquant une entrée dans la matrice de dérivée seconde et certains déterminants. En fait, ces conditions codent simplement l'observation géométrique suivante:R2R

  • Si la matrice des dérivées secondes est définie positive, vous êtes au minimum local.
  • Si la matrice des dérivées secondes est définie négative, vous êtes à un maximum local.
  • Sinon, vous n'êtes ni l'un ni l'autre, un point de selle.

Vous pouvez comprendre cela avec le raisonnement géométrique ci-dessus dans une base propre. La dérivée première à un point critique disparaît, donc les taux de changement de la fonction ici sont contrôlés par la dérivée seconde. Maintenant, nous pouvons raisonner géométriquement

  • Dans le premier cas, il y a deux directions propres, et si vous vous déplacez, la fonction augmente.
  • Dans le second, deux directions propres, et si vous vous déplacez dans l'une ou l'autre, la fonction diminue.
  • Dans la dernière, il y a deux directions propres, mais dans l'une d'elles la fonction augmente et dans l'autre elle diminue.

Puisque les vecteurs propres couvrent tout l'espace, toute autre direction est une combinaison linéaire de directions propres, donc les taux de changement dans ces directions sont des combinaisons linéaires des taux de changement dans les directions propres. Donc, en fait, cela vaut dans toutes les directions (c'est plus ou moins ce que cela signifie pour une fonction définie sur un espace de dimension supérieure pour être différenciable). Maintenant, si vous dessinez une petite image dans votre tête, cela a beaucoup de sens de quelque chose qui est assez mystérieux dans les textes de calcul débutant.

Cela s'applique directement à l'un de vos puces

La forme quadratique est convexe, siAest SPD. Convex est une belle propriété qui peut garantir que la solution locale est une solution globale12xAxbx+cA

La matrice des dérivées secondes est partout, qui est définie positive symétrique. Géométriquement, cela signifie que si nous nous éloignons dans n'importe quelle direction propre (et donc dans n'importe quelle direction, car toute autre est une combinaison linéaire de directions propres), la fonction elle-même se pliera au- dessus de son plan tangent. Cela signifie que toute la surface est convexe.A

Matthew Drury
la source
5
Une façon graphique de voir les choses: si est SPD, les contours de la forme quadratique associée sont ellipsoïdaux. A
JM n'est pas statisticien le
7
Cette caractérisation par @JM est très perspicace. Au cas où quelqu'un se demanderait ce qui pourrait être spécial au sujet des contours ellipsoïdaux, notez que ce ne sont que des sphères parfaites déguisées: les unités de mesure peuvent différer le long de leurs axes principaux et les ellipsoïdes peuvent être tournés par rapport aux coordonnées dans lesquelles les données sont décrites , mais pour un grand nombre d'objectifs - notamment conceptuels - ces différences sont sans conséquence.
whuber
Cela est lié à ma façon de comprendre géométriquement la méthode de Newton. Optimisez au mieux le niveau actuel défini avec un ellipsoïde, puis prenez un système de coordonnées où l'ellipsoïde est un cercle, déplacez-vous orthogonalement au cercle dans ce système de coordonnées.
Matthew Drury
1
S'il y a des contraintes (actives), vous devez projeter dans le jacobien des contraintes actives avant de faire le spiel de valeurs propres et d'eigendirection. Si la toile de jute est psd, la (toute) projection sera psd, mais l'inverse n'est pas nécessairement vrai, et ce n'est souvent pas le cas. Voir ma réponse.
Mark L. Stone du
10

Vous trouverez une certaine intuition dans les nombreuses façons élémentaires de montrer que les valeurs propres d'une matrice symétrique réelle sont toutes réelles: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- épreuve / 118640 # 118640

En particulier, la forme quadratique se produit naturellement dans le quotient de Rayleigh, et les matrices symétriques fournissent ce qui est sans doute le moyen le plus naturel d'exposer une grande famille de matrices dont les valeurs propres sont réelles. Voir le théorème de Courant minimax par exemple: https://en.wikipedia.org/wiki/Courant_minimax_principlexTAx

En outre, les matrices symétriques définies positives sont strictement le seul ensemble de matrices qui peuvent définir un produit scalaire non négligeable, avec une norme induite: . En effet, par définition pour les vecteurs réels x , y d ( x , y ) = d ( y , x ) pour tous les x , y et x 2 =d(x,y)=x,Ay=xTAyx,y d(x,y)=d(y,x)x,y pour x 0 . De cette façon, les matrices définies positives symétriques peuvent être considérées comme des candidats idéaux pour les transformations de coordonnées.x2=xTAx>0x0

Cette dernière propriété est absolument essentielle dans le domaine des machines à vecteurs de support, en particulier les méthodes du noyau et l'astuce du noyau , où le noyau doit être symétrique positif pour induire le bon produit interne. En effet, le théorème de Mercer généralise les propriétés intuitives des matrices symétriques aux espaces fonctionnels.

Alex R.
la source
9

En ce qui concerne l'optimisation (parce que vous avez marqué votre question avec la balise d'optimisation), les matrices SPD sont extrêmement importantes pour une raison simple - un SPD Hessian garantit que la direction de recherche est une direction de descente. Considérons la dérivation de la méthode de Newton pour une optimisation sans contrainte. Tout d'abord, nous formons l'expansion de Taylor de :f(x+Δx)

f(x+Δx)f(x)+ΔxTf(x)+12ΔxT2f(x)Δx

Ensuite, nous prenons la dérivée par rapport à :Δx

f(x+Δx)f(x)+2f(x)Δx

Δx

Δx=2f(x)1f(x)

2f(x)Δx

f(x)TΔx=f(x)T2f(x)1f(x)<0

Lorsque vous utilisez la méthode de Newton, les matrices de Hesse non SPD sont généralement "poussées" pour être SPD. Il existe un algorithme soigneux appelé Cholesky modifié qui détectera une toile de jute non SPD, la "poussera" de manière appropriée dans la bonne direction et factorisera le résultat, le tout (essentiellement) pour le même coût qu'une factorisation Cholesky. Les méthodes Quasi-Newton évitent ce problème en forçant le Hessian approximatif à être SPD.

Soit dit en passant, les systèmes indéfinis symétriques reçoivent beaucoup d'attention ces jours-ci. Ils apparaissent dans le contexte des méthodes de point intérieur pour l'optimisation contrainte.

Bill Woessner
la source
Merci beaucoup pour cette excellente réponse. Je comprends qu'une direction décente est importante dans la méthode de recherche en ligne. Dans les méthodes de région de confiance, une direction décente est également importante?
Haitao Du
1
Il est toujours important pour les méthodes de région de confiance. Les méthodes de région de confiance fonctionnent essentiellement en délimitant la taille du pas en premier puis en résolvant la direction du pas. Si l'étape n'atteint pas la diminution souhaitée de la valeur de la fonction objectif, vous réduisez la limite de la taille de l'étape et recommencez. Imaginez que votre algorithme de génération de la direction du pas ne garantit pas que la direction du pas est une direction de descente. Même lorsque le rayon de la région de confiance passe à 0, vous ne pouvez jamais générer de pas acceptable (même s'il en existe un) car aucune de vos directions de pas n'est une direction de descente.
Bill Woessner
Les méthodes de recherche de ligne présentent essentiellement le même comportement. Si votre direction de recherche n'est pas une direction de descente, l'algorithme de recherche de ligne peut ne jamais trouver une longueur de pas acceptable - car il n'y en a pas. :-)
Bill Woessner
Excellente réponse, merci de m'aider à connecter les pièces.
Haitao Du
9

Géométriquement, une matrice définie positive définit une métrique , par exemple une métrique riemannienne, de sorte que nous pouvons immédiatement utiliser des concepts géométriques.

xyA

d(x,y)=(xy)TA(xy)

Rn

x,y=xTAy
ARn

kjetil b halvorsen
la source
1
A=I
6

Il existe déjà plusieurs réponses expliquant pourquoi les matrices définies positives symétriques sont si importantes, donc je fournirai une réponse expliquant pourquoi elles ne sont pas aussi importantes que le pensent certaines personnes, y compris les auteurs de certaines de ces réponses. Par souci de simplicité, je limiterai la focalisation aux matrices symétriques et me concentrerai sur les Hessois et l'optimisation.

Si Dieu avait rendu le monde convexe, il n'y aurait pas d'optimisation convexe, il y aurait juste une optimisation. De même, il n'y aurait pas de matrices définies positives (symétriques), il y aurait juste des matrices (symétriques). Mais ce n'est pas le cas, alors traitez-le.

Si un problème de programmation quadratique est convexe, il peut être résolu "facilement". S'il n'est pas convexe, un optimum global peut toujours être trouvé en utilisant des méthodes de branchement et liées (mais cela peut prendre plus de temps et plus de mémoire).

Si une méthode de Newton est utilisée pour l'optimisation et que la Hesse à une certaine itération est indéfinie, alors il n'est pas nécessaire de la "finagler" à une définition positive. Si vous utilisez une recherche de ligne, des directions de courbure négative peuvent être trouvées et la recherche de ligne exécutée le long d'elles, et si vous utilisez une région de confiance, alors il y a une région de confiance suffisamment petite pour que la solution du problème de la région de confiance atteigne la descente.

Comme pour les méthodes Quasi-Newton, BFGS (amorti si le problème est contraint) et DFP maintiennent une définition positive de l'approximation de la Hesse ou de la Hesse inverse. D'autres méthodes Quasi-Newton, telles que SR1 (Symmetric Rank One) ne maintiennent pas nécessairement une définition positive. Avant de vous déformer, c'est une bonne raison de choisir SR1 pour de nombreux problèmes - si la Hesse n'est vraiment pas définie positive le long du chemin vers l'optimum, alors forcer l'approximation de Quasi-Newton à être définie positive peut entraîner une approximation quadratique moche de la fonction objectif. En revanche, la méthode de mise à jour SR1 est "lâche comme une oie", et peut fausser sa définition à mesure qu'elle progresse.

Pour les problèmes d'optimisation non linéairement contraints, ce qui importe vraiment n'est pas le Hessien de la fonction objectif, mais le Hessien du Lagrangien. Le Hessien du Lagrangien peut être indéfini même à un (l'opt) optimum, et en effet, ce n'est que la projection du Hessien du Lagrangien dans l'espace nul du Jacobien des contraintes actives (linéaires et non linéaires) qui doivent être semi positives -fini à l'optimum. Si vous modélisez la Hesse du Lagrangien via BFGS et ainsi la contraignez à être définie positive, cela pourrait être un ajustement terrible partout, et ne fonctionnera pas bien. En revanche, SR1 peut adapter ses valeurs propres à ce qu'il "voit" réellement.

Il y a beaucoup plus que je pourrais dire à propos de tout cela, mais cela suffit pour vous donner une saveur.

Edit : ce que j'ai écrit 2 paragraphes est correct. Cependant, j'ai oublié de souligner qu'il s'applique également aux problèmes à contraintes linéaires. Dans le cas de problèmes linéairement contraints, le Hessien du Lagrangien est juste (réduit à) le Hessien de la fonction objectif. Ainsi, la condition d'optimalité de second ordre pour un minimum local est que la projection du Hessien de la fonction objectif dans l'espace nul du Jacobien des contraintes actives est semi-définie positive. Plus particulièrement, la toile de jute de la fonction objectif n'a pas besoin (nécessairement) d'être psd à l'optimum, et ce n'est souvent pas le cas, même sur des problèmes à contraintes linéaires.

Mark L. Stone
la source
@ GeoMatt22 Vous pariez votre @ $$ Je ne le suis pas. D'un autre côté, si vous allez créer (choisir) une fonction de perte, il n'est pas nécessaire de la rendre non convexe lorsqu'elle ne sert à rien d'autre que le show-boating. La discrétion est la meilleure partie de la valeur.
Mark L. Stone
@Mark L. Stone: C'est intéressant! Pouvez-vous faire référence à une littérature où je peux lire de telles choses?
kjetil b halvorsen
@kjetil b halvorsen. Recherche de ligne avec les directions de courbure négative folk.uib.no/ssu029/Pdf_file/Curvilinear/More79.pdf . Les régions de confiance sont couvertes dans de nombreux livres et articles. Amazon.com/… .. Un livre bien connu avec une bonne introduction aux régions de confiance est amazon.com/… .. Le livre monstre, quelque peu dépassé maintenant, est epubs.siam.org/doi/book/10.1137/1.9780898719857 . En ce qui concerne mon dernier paragraphe sur les conditions d'optimalité, lisez les conditions KKT de second ordre
Mark L. Stone
@kjetil b halvorsen Je n'ai pas cherché à trouver l'optimum global du programme quadratique non convexe. Un logiciel largement disponible, tel que CPLEX, peut le faire, voir ibm.com/support/knowledgecenter/SS9UKU_12.6.1/… . Bien sûr, il n'est pas toujours rapide et peut avoir besoin de mémoire. J'ai résolu à l'optimalité globale certains problèmes de minimisation de QP avec des dizaines de milliers de variables qui avaient plusieurs centaines de valeurs propres négatives de magnitude significative.
Mark L. Stone du
5

Vous avez déjà cité un tas de raisons pour lesquelles le SPD est important, mais vous avez toujours posté la question. Il me semble donc que vous devez d'abord répondre à cette question: pourquoi les quantités positives sont-elles importantes?

Ma réponse est que certaines quantités doivent être positives afin de se réconcilier avec nos expériences ou modèles. Par exemple, les distances entre les éléments dans l'espace doivent être positives. Les coordonnées peuvent être négatives, mais les distances sont toujours non négatives. Par conséquent, si vous avez un ensemble de données et un algorithme qui le traite, vous risquez de vous retrouver avec un qui tombe en panne lorsque vous y insérez une distance négative. Donc, vous dites "mon algorithme nécessite des entrées de distance positives à tout moment", et cela ne ressemblerait pas à une demande déraisonnable.

i(xiμ)2/n
xi

Ainsi, les matrices de variance-covariance sont semi-définies positives, c'est-à-dire "non négatives" dans cette analogie. L'exemple d'un algorithme qui nécessite cette condition est la décomposition de Cholesky, c'est très pratique. On l'appelle souvent une "racine carrée de la matrice". Ainsi, comme la racine carrée d'un nombre réel qui nécessite la non-négativité, Cholesky veut des matrices non négatives. Nous ne trouvons pas cela contraignant lorsqu'il s'agit de matrices de covariance car elles le sont toujours.

Voilà ma réponse utilitaire. Les contraintes telles que la non-négativité ou SPD nous permettent de construire un algorithme de calcul plus efficace ou des outils de modélisation pratiques qui sont disponibles lorsque vos entrées satisfont à ces contraintes.

Aksakal
la source
3

Voici deux autres raisons qui n'ont pas été mentionnées pour lesquelles les matrices semi-définies positives sont importantes:

  1. La matrice graphique laplacienne est diagonalement dominante et donc PSD.

  2. La semi-infinité positive définit un ordre partiel sur l'ensemble des matrices symétriques (c'est le fondement de la programmation semi-infinie).

Thoth
la source