Question:
Calcul de $ (X ^ TX) ^ {- 1} X ^ Ty $ dans OLS
NPE
2011-04-14 10:58:16 UTC
view on stackexchange narkive permalink

Soit $ A \ in \ mathbb {R} ^ {n \ times n} $ une matrice dense symétrique définie positive (le $ X ^ TX $ de ici) et $ b $ un vecteur dans $ \ mathbb {R} ^ n $.

J'ai besoin de calculer $ A ^ {- 1} b $.

Deux questions:

  1. Pourriez-vous recommander un algorithme efficace et numériquement stable pour calculer $ A ^ {- 1} b $ pour $ n \ environ 1000 $?

  2. Soit $ \ tilde {A_i} $ désigne la matrice obtenue à partir de $ A $ en supprimant sa $ i $ -th ligne et $ i $ -th colonne. Y a-t-il un algorithme qui, ayant été autorisé à pré-traiter $ A $ d'une manière ou d'une autre, me permettrait de calculer rapidement $ \ tilde {A_i} ^ {- 1} \ tilde b $ pour tout $ i \ in \ {1 , 2, \ ldots, n \} $ et tout $ \ tilde b \ in \ mathbb {R} ^ {n-1} $?

Trois réponses:
#1
+6
mpiktas
2011-04-14 15:57:10 UTC
view on stackexchange narkive permalink

Pour compléter la réponse de @ onestop, un autre moyen efficace consiste à utiliser la décomposition QR. L'avantage supplémentaire est que la décomposition QR peut être appliquée directement à $ X $, et non à $ X ^ TX $.

Je pense que la décomposition QR peut être adaptée à votre deuxième question, c'est vraiment simple pour la suppression de colonne.

Cependant, la question est de savoir pourquoi en avez-vous besoin? Il existe des bibliothèques facilement disponibles qui effectuent ces opérations de manière très efficace. Voulez-vous les réimplémenter? Pour autant que je sache, il y a beaucoup d'ajustements de code non triviaux, même si l'algorithme est fondamentalement le meilleur pour le travail, il y a donc de fortes chances que vous n'obteniez pas tous les avantages en implémentant un algorithme qui est censé être théoriquement supérieur .

Voici le lien vers le chapitre d'un livre, qui traite des modifications nécessaires pour résoudre la deuxième question en cas de décomposition QR. Bien qu'elle stipule que les méthodes s'appliquent aux problèmes des moindres carrés, elle peut être appliquée au système d'équations linéaires.

Je suis à peu près sûr que cela devrait être un problème standard, alors peut-être que quelqu'un donnera une référence plus appropriée.

@mpiktas: Merci pour cela. Juste pour clarifier, je n'ai pas $ X $. Je n'ai que $ X ^ TX $ - voir http://stats.stackexchange.com/questions/9341/regularized-fit-from-summarized-data
La décomposition QR d'@aix, peut toujours être appliquée, bien que Cholesky puisse être plus approprié.
@mpiktas: Pour répondre à votre deuxième point, je ne dis pas que je vais coder mon propre SVD / QR / Cholesky / peu importe (à moins que j'aie vraiment à le faire).
@aix, Je sais que vous ne dites pas, c'est pourquoi je demandais :)
@aix, J'ai mis à jour la réponse avec le lien vers le livre, que vous pourriez trouver intéressant. Puisque votre problème est assez spécifique, je soupçonne que tôt ou tard vous serez obligé de lire un livre sur les méthodes numériques pour les problèmes des moindres carrés, alors pourquoi ne pas commencer plus tôt :)
@mpiktas: Vous ne le croiriez pas, mais j'ai en fait commandé ce livre même ce matin!
@aix, "les grands esprits pensent pareil" :) Je ne sais pas où j'ai entendu ou lu ceci (le contexte était humoristique), mais je pense que cela s'applique ici: D
Outre Björck, l'autre référence intéressante pour résoudre les problèmes des moindres carrés est le livre (classique) [Lawson / Hanson] (http://books.google.com/books?id=ROw4hU85nz8C&pg=PA174).
@J. M., merci! C'était le premier livre que j'ai lu sur ce sujet, mais j'ai oublié les auteurs et le titre exact. Très bon livre. Il contient également des exemples de code Fortran, ce qui m'a également été très utile.
#2
+5
onestop
2011-04-14 15:32:32 UTC
view on stackexchange narkive permalink

La réponse standard à votre première question est Décomposition de Cholesky . Pour citer l'article Wikipedia:

Si $ A $ est symétrique et défini positif, alors nous pouvons résoudre $ Ax = b $ [pour $ x $] par calculer la décomposition de Cholesky $ A = LL ^ \ mathrm {T} $, puis résoudre $ Ly = b $ pour $ y $, et enfin résoudre $ L ^ \ mathrm {T} x = y $ pour $ x $.

Je ne sais pas vraiment ce que vous recherchez dans votre deuxième question. Une solution à la première question n'apporte-t-elle pas également une solution à la seconde? Il n'est sûrement pas difficile de supprimer une ligne et une colonne d'une matrice, et c'est sûrement tout le «pré-traitement» requis ??

#3
+5
Hans Engler
2011-04-14 19:34:06 UTC
view on stackexchange narkive permalink

En ce qui concerne votre deuxième question, voici un moyen de le faire pour $ n = i $, pour simplifier la notation. Soit $ \ alpha = A_ {nn}, \, a = (A_ {1n}, \ dots, A_ {n-1, n}) ^ T $ et donc $$ A = \ begin {pmatrix} \ tilde A & a \\ a ^ T & \ alpha \ end {pmatrix} $$ Laissez également $ A ^ {- 1} $ être partitionné de la même manière, $$ A ^ {- 1} = \ begin {pmatrix} \ tilde C & c \\ c ^ T & \ gamma \ end {pmatrix} $$ Je comprends que vous voulez $ \ tilde A ^ {- 1} $ et que vous avez déjà calculé $ A ^ {- 1} $. Définissez $ d = \ tilde A ^ {- 1} a $ et $ \ delta = c ^ Ta $. Ces quantités apparaissent déjà dans $ A ^ {- 1} $, puisque $$ A ^ {- 1} = \ begin {pmatrix} \ tilde A ^ {- 1} + \ frac {1} {\ alpha - \ delta} dd ^ T & - \ frac {1} {\ alpha - \ delta} d \\ - \ frac {1} {\ alpha - \ delta} d ^ T & \ frac {1} {\ alpha - \ delta} \ end {pmatrix} $$ comme le montre un calcul direct. Par conséquent, $$ \ tilde A ^ {- 1} = \ tilde C - \ frac {1} {\ alpha - \ delta} dd ^ T = \ tilde C - \ frac {1} {\ gamma} cc ^ T $ $ qui est une mise à jour $ O (n ^ 2) $ de $ A ^ {- 1} $.

Cependant, en règle générale, les mises à jour sont plus sujettes à une instabilité numérique que les mises à jour.


Ce Q&R a été automatiquement traduit de la langue anglaise.Le contenu original est disponible sur stackexchange, que nous remercions pour la licence cc by-sa 3.0 sous laquelle il est distribué.
Loading...