Espace nul d'une matrice dense rectangulaire

16

Étant donné une matrice dense quelle est la meilleure façon de trouver sa base d'espace nul dans une certaine tolérance ?

ARm×n,m>>n;max(m)100000
ϵ

Sur cette base, puis-je dire que certains cols dépendent linéairement de ? En d'autres termes, ayant une base d'espace nul calculée, quelles colonnes de doivent être supprimées afin d'obtenir une matrice non singulière?ϵA

Les références sont appréciées.

Alexandre
la source

Réponses:

12

Les méthodes standard pour déterminer l'espace nul d'une matrice sont d'utiliser une décomposition QR ou un SVD. Si la précision est primordiale, le SVD est préféré; la décomposition QR est plus rapide.

En utilisant le SVD, si , alors les colonnes de correspondant à de petites valeurs singulières (c'est-à-dire de petites entrées diagonales de ) constituent la base de l'espace nul. La tolérance pertinente ici est ce que l'on considère comme une "petite" valeur singulière. MATLAB, par exemple, prend petit pour être , où \ varepsilon est lié à la précision de la machine (voir ici dans la documentation de MATLAB ).A=UΣVHVΣmax(m,n)εε

En utilisant la décomposition QR, si , et le rang de est , alors les dernières colonnes de constituent l'espace nul de , en supposant que la décomposition QR révèle le rang. Pour déterminer , calculez le nombre d'entrées sur la diagonale principale de dont l'amplitude dépasse une tolérance (similaire à celle utilisée dans l'approche SVD).AT=QRArnrQArR

N'utilisez pas la décomposition LU. En arithmétique exacte, c'est une approche viable, mais avec l'arithmétique en virgule flottante, l'accumulation d'erreurs numériques la rend inexacte.

Wikipedia couvre ces sujets ici .

Geoff Oxberry
la source
Geoff, en termes de QR, suppose que j'ai la décomposition, comment puis-je relier la base d'espace nul et les colonnes dans la matrice d'origine? En d'autres termes, quelles colonnes dois-je supprimer de afin de se débarrasser de l'espace nul? Il s'agit ici de travailler avec lui-même et non avec sa décomposition. AAA
Alexander
Les routines qui calculent la décomposition QR incluent normalement une option pour renvoyer un vecteur de permutation indiquant comment les colonnes sont permutées pour obtenir la factorisation QR. Les entrées de ce vecteur de permutation correspondraient aux rangées de A (colonnes de A T ) qui se trouvent dans l 'espace nul. Les r premières entrées de ce vecteur correspondent aux colonnes de A T qui sont linéairement indépendantes. Je ne sais pas ce que vous entendez par "se débarrasser de l'espace nul". Voulez-vous dire que vous souhaitez supprimer les colonnes de A pour obtenir une matrice non singulière? nrAATrATA
Geoff Oxberry
Oui, je veux dire ça. Je vais regarder la permutation, merci.
Alexander
C'est une question différente. Qu'est - ce que vous voudriez faire à la place est de calculer la décomposition QR (ou SVD) de . Si vous calculez la décomposition QR de A , vous pouvez calculer le rang de A comme dans la réponse ci-dessus (pas besoin de transposer la matrice), puis les r premières entrées (où r est le rang de A ) du vecteur de permutation correspondent aux colonnes indépendantes de A . Le même type d'algorithme s'applique au SVD; si vous pouvez renvoyer un vecteur de permutation avec la décomposition, cela devrait fournir les informations nécessaires. AAArrAA
Geoff Oxberry
8

Si , que votre question indique, vous pouvez enregistrer un travail d'abord choisir un ensemble d' indices I de p 5 n ( par exemple) des lignes aléatoires et en utilisant la factorisation orthogonale A T I : = Q R . (La factorisation QR est celle où Q est carré et R est rectangulaire de rang r , et les n - r colonnes restantes de R sont nulles. L'utilisation d'une factorisation QR permutée améliorera la stabilité; la permutation doit ensuite être prise en compte dans un recette plus détaillée.)mnIp5nAI:T=QRQRrnrR

En règle générale, cela vous donnera un sous - espace beaucoup moindre dimension enjambé par les colonnes de , le dernier n - r colonnes de Q . Ce sous - espace contient l'espace nul de A . Maintenant , choisir un autre, l' indice aléatoire disjoints set et calculer la factorisation QR de ( A I : N ) T . Multipliez l'espace nul résultant à gauche par N pour obtenir un N amélioré de dimension probablement encore plus faible. Itérer jusqu'à ce que la dimension de N ne diminue plus. Ensuite, vous avez probablement l'espace nul correct et pouvez vérifier en calculant A NNnrQA(AI:N)TNNNAN. Si ce n'est pas encore négligeable, effectuez d'autres itérations avec les lignes les plus significatives.

Edit: Une fois que vous avez , vous pouvez trouver un ensemble maximal J de colonnes linéairement indépendantes de A par une factorisation orthogonale de N T = Q R avec pivotement. En effet, l'ensemble J d'indices non choisis comme pivots aura cette propriété.NJANT=QRJ

Arnold Neumaier
la source
+1 pour un moyen efficace de déterminer l'espace nul d'une grande matrice. Je dois me rappeler de consulter cette réponse plus tard lorsque j'en aurai besoin.
Geoff Oxberry
En effet, cela semble raisonnable, cependant mes matrices tiennent dans 16 Go de RAM, donc je resterais avec matlab qr standard.
Alexander
Professeur Neumaier, j'ai décidé de tester cet algorithme, mais je ne comprends pas exactement ce qu'est et que signifie "calculer la factorisation QR de ( A I : N ) T "? Pourriez-vous s'il vous plaît expliquer un peu plus. N(AI:N)T
Alexander
J'ai un peu modifié ma réponse. est calculé par la recette de Geoff Oxberry. N
Arnold Neumaier
Je vous remercie. Je l'ai implémenté. Cependant, pour autant que je vois, cet algorithme ne permet pas de me définir un ensemble de colonnes linéairement indépendantes de (puisque nous décomposons A T I : plutôt que A I : ), mais juste aide à estimer la base de nullspace lui - même? AAI:TAI:
Alexander