Spectre approximatif d'une grande matrice

Je veux calculer le spectre ( toutes les valeurs propres) d'une grande matrice clairsemée (des centaines de milliers de lignes). C'est dur.

Je suis prêt à me contenter d'une approximation. Existe-t-il des méthodes d'approximation pour ce faire?

Bien que j'espère une réponse générale à cette question, je serais également satisfait d'une réponse dans le cas spécifique suivant. Ma matrice est un laplacien normalisé d'un grand graphique. Les valeurs propres seront comprises entre 0 et 2 avec un grand nombre d'entre elles regroupées autour de 1.

Si votre graphique n'est pas dirigé (comme je le soupçonne), la matrice est symétrique et vous ne pouvez rien faire de mieux que l'algorithme de Lanczsos (avec une réorthogonalisation sélective si nécessaire pour la stabilité). Comme le spectre complet est composé de 100 000 nombres, je suppose que vous êtes principalement intéressé par la densité spectrale.

Pour obtenir une densité spectrale approximative, prenez le spectre du premier sous-espace de Krylov de dimension 100 environ, et remplacez sa densité discrète par une version lissée.

Le premier spectre de Krylov aura des valeurs propres bien isolées presque résolues (si elles existent), se rapproche des valeurs propres à la fin du spectre non isolé et est quelque peu aléatoire entre les deux, avec une distribution dont la fonction de distribution cumulée ressemble à celle du vrai spectre . Il y convergerait en arithmétique exacte si la dimension augmentait. (Si votre opérateur était de dimension infinie, ce serait toujours le cas, et vous obtiendriez l'intégrale de la véritable fonction de densité spectrale sur le spectre continu.)

La réponse d'Arnold Neumaier est discutée plus en détail dans la section 3.2 de l'article «Approximation des densités spectrales des grandes matrices» de Lin Lin, Yousef Saad et Chao Yang (2016) .

D'autres méthodes sont également discutées, mais l'analyse numérique à la fin de l'article montre que la méthode Lanczos surpasse ces alternatives.

Si vous êtes d'accord pour penser à des choses qui ne sont pas des valeurs propres mais des fonctions qui, dans un certain sens, vous disent encore quelque chose sur le spectre, alors je pense que vous devriez vérifier certains des travaux de Mark Embree à l'Université Rice.

Voici encore une autre façon de caractériser le spectre.

$\mathbf{A} v_k = \lambda_k v_k$$\mathbf{A}$

$$S(\omega) = \sum_k \frac{\pi^{-1}\sigma}{\sigma^2 + (\lambda_k - \omega)^2} = \frac{\sigma}{\pi} \mathop{\mathrm{Tr}} [\sigma^2 + (\omega - \mathbf{A})^2]^{-1}$$ $$S(\omega) = \frac{\sigma}{\pi}\langle z^T [\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z \rangle$$ $z$$+1$$-1$$\sigma$$\omega$$[\sigma^2 + (\omega - \mathbf{A})^2]^{-1} z$$[\omega + i \sigma - \mathbf{A}]^{-1} [\omega - i \sigma - \mathbf{A}]^{-1}$$S(\omega)$

$\omega$

$\omega$

Voir le document "On Sampling-based Approximate Spectral Decomposition" par Sanjiv Kumar, Mehryar Mohri & Ameet Talwalkar (ICML 2009.). Il utilise l'échantillonnage des colonnes de votre matrice.

Puisque votre matrice est symétrique, vous devez procéder comme suit:

Soit A votre matrice n * n. Vous voulez réduire le calcul des valeurs propres d'une matrice n * n au calcul des valeurs propres d'une matrice k * k. Choisissez d'abord votre valeur de k. Disons que vous choisissez k = 500, car vous pouvez facilement calculer les valeurs propres d'une matrice 500 * 500. Ensuite, choisissez aléatoirement k colonnes de la matrice A. Construisez la matrice B qui ne conserve que ces colonnes et les lignes correspondantes.

B = A (x, x) pour un ensemble aléatoire de k indices x

B est maintenant une matrice ak * k. Calculez les valeurs propres de B et multipliez-les par (n / k). Vous avez maintenant k valeurs qui sont approximativement distribuées comme les n valeurs propres de A. Notez que vous n'obtenez que k valeurs, pas n, mais leur distribution sera correcte (jusqu'au fait qu'elles soient une approximation).

Vous pouvez toujours utiliser les bornes du théorème du cercle de Gershgorin pour approximer les valeurs propres.

Si les termes hors diagonale sont petits, la diagonale elle-même est une bonne approximation du spectre. Sinon, si vous vous retrouvez avec une approximation de l'espace propre (par d'autres méthodes), vous pouvez essayer d'exprimer les entrées diagonales dans ce système. Cela conduira à une matrice avec des termes hors diagonale plus petits et la nouvelle diagonale sera une meilleure approximation du spectre.