Espace nul d'une matrice dense rectangulaire

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

A \in R^{m \times n}, m >> n; m a x (m) \approx 100000

$A \in R^{m \times n}, m >> n; max(m) \approx 100000$

ϵ

$\epsilon$

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? $\epsilon$ $A$

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

linear-algebra Alexandre
la source

Réponses:

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ù est lié à la précision de la machine (voir ici dans la documentation de MATLAB ). $A = U\Sigma V^{H}$ $V$ $\Sigma$ $\max(m,n) \cdot \varepsilon$ $\varepsilon$

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). $A^{T} = QR$ $A$ $r$ $n-r$ $Q$ $A$ $r$ $R$

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.

A

$A$

A

$A$

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

(colonnes de

) qui se trouvent dans l 'espace nul. Les

premières entrées de ce vecteur correspondent aux colonnes de

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

pour obtenir une matrice non singulière?

n - r

$n-r$

A

$A$

A^{T}

$A^{T}$

r

$r$

A^{T}

$A^{T}$

A

$A$

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

, vous pouvez calculer le rang de

comme dans la réponse ci-dessus (pas besoin de transposer la matrice), puis les

premières entrées (où

est le rang de

) du vecteur de permutation correspondent aux colonnes indépendantes de

. 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.

A

$A$

A

$A$

A

$A$

r

$r$

r

$r$

A

$A$

A

$A$

Geoff Oxberry

Si , que votre question indique, vous pouvez enregistrer un travail d'abord choisir un ensemble d' indices de ( par exemple) des lignes aléatoires et en utilisant la factorisation orthogonale . (La factorisation QR est celle où est carré et est rectangulaire de rang , et les colonnes restantes de 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.) $m\gg n$ $I$ $p\approx 5n$ $A_{I:}^T=QR$ $Q$ $R$ $r$ $n-r$ $R$

En règle générale, cela vous donnera un sous - espace beaucoup moindre dimension enjambé par les colonnes de , le dernier colonnes de . Ce sous - espace contient l'espace nul de . Maintenant , choisir un autre, l' indice aléatoire disjoints set et calculer la factorisation QR de . Multipliez l'espace nul résultant à gauche par pour obtenir un amélioré de dimension probablement encore plus faible. Itérer jusqu'à ce que la dimension de ne diminue plus. Ensuite, vous avez probablement l'espace nul correct et pouvez vérifier en calculant $N$ $n-r$ $Q$ $A$ $(A_{I:}N)^T$ $N$ $N$ $N$ $AN$ . 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 de colonnes linéairement indépendantes de par une factorisation orthogonale de avec pivotement. En effet, l'ensemble d'indices non choisis comme pivots aura cette propriété. $N$ $J$ $A$ $N^T=QR$ $J$

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

"? Pourriez-vous s'il vous plaît expliquer un peu plus.

N

$N$

(A_{I :} N)^{T}

$(A_{I:}N)^T$

Alexander

J'ai un peu modifié ma réponse.

est calculé par la recette de Geoff Oxberry.

N

$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

plutôt que

), mais juste aide à estimer la base de nullspace lui - même?

A

$A$

A_{I :}^{T}

$A_{I:}^T$

A_{I :}

$A_{I:}$

Alexander