Discussion :

[Bktero]

Bonjour

Je poste habituellement sur le forum Matlab, mais pour ce problème je me suis dit (et surtout lisant une remarque du modérateur du forum Matlab) qu'il serait peut-être mieux de poster sur un forum ayant directement à voir avec les algorithmes et les mathématiques. Merci d'avance de l'attention que vous porterez à mon problème.


Contexte : je suis élève en école d'ingénieur, actuellement en stage, où je fais de l'acoustique, de la détection de sources sonores pour être exact. Depuis quelques jours, j'utilise un algorithme dit de Capon, du nom de son créateur. Il n'est pas tout nouveau et à déjà fait ses preuves, néanmoins on m'a demandé de faire des tests dessus, pour aider un doctorant travaillant sur les algorithmes de détection. Je me suis donc lancé dans les tests.

Il marche plutôt en pratique, c'est à dire avec des échantillons acquis via des microphones (j'ai une antenne linéaire constituée d'un certain nombre de microphones), mais quand j'ai essayé de l'utiliser avec un signal théorique (imitant l'expérience), que je crée à partir de formules sous Matlab, ça s'est un peu gâté. En effet, j'ai tout plein de warnings de sa part concernant des problèmes de conditionnement.



Problème : j'ai dans les 2 cas (expérience ou théorie) une matrice signal dont le nombre de lignes correspond aux différents instants d'échantillonnage, chaque colonne représente un microphone donné. Typiquement, 1024 lignes / échantillons et 6 colonnes / microphones. Je dispose également d'un vecteur a, dépendant d'un angle theta, qui décrit les retards temporels de réception de l'antenne (je ne pense pas que cela soit très important pour vous de comprendre cela )

Je dois calculer la matrice de covariance de cette matrice signal, et ensuite inverser cette matrice de covariance (je noterai IR cette matrice de covariance inversée). Et là surgit le problème de conditionnement.

La question que vous posez à plusieurs personnes sur ce forum, quand elles parlent d'inversion de matrice, est "pourquoi inversez la matrice?" Et bien tout simplement car je dois trouver les minimums de la fonction P = ah*IR*a, où ah désigne la transposée conjuguée de a, lorsque la variable theta varie.

Ma question : le problème de conditionnement est-il vraiment dérangeant ? En effet, j'ai appris que le conditionnement intervient lors de la résolution de systèmes linéaires, mais je n'ai pas ici l'impression de résoudre un système linéaire. De façon cachée, j'en résoudrais un ?

Merci d'avance de vos réponses, en fonction de ce que vous me direz, je poserai d'autres questions

Bonne journée.

[Invité]

Le problème de conditionnement intervient quand la matrice de variance covariance a des valeurs propres très faibles (précisement, quand le rapport entre la plus grande et la plus petite valeur propre devient grand).

Quand on fait des calculs sur des matrices mal conditionnées, ces valeurs propres très faibles et leurs vecteurs propres associés sont très sensibles au bruit sur les données, et aux erreurs d'arrondi provenant des calculs en virgule flottante.

Tant qu'on n'inverse pas la matrice, ce n'est pas gênant, puisque les valeurs propres sont petites. Mais dès qu'on l'inverse, ces petites valeurs propres deviennent très grandes, et les erreurs sur les vecteurs propres associés dominent... Cela intervient quand on résoud un système linéaire, mais aussi dans tout algorithme qui utilise une inversion matricielle.

Pour régler le problème, tu as trois possibilités :

1- ajouter à ta matrice de variance covariance une petite diagonale (lambda fois l'identité, où lambda est petit par rapport à ta plus grande valeur propre, genre 1/10000), cet ajout ne déstabilisera pas les axes principaux de ta matrice, mais il bornera le paramètre de conditionnement. Cette approche s'apparente à une méthode de régularisation.
2- utiliser un algorithme moins sensible au conditionnement (par exemple une SVD de la matrice de départ au lieu d'une inversion de la matrice de variance covariance)...
3- commencer par diagonaliser ta matrice de variance covariance, te placer dans le référentiel factoriel, et éliminer les dimensions portées par de petites valeurs propres. Cela va mécaniquement faire disparaitre ton problème de conditionnement, et te permettre au passage de résoudre un problème plus simple. (Il te faudra cependant "revenir", en fin de parcours, dans ton référentiel d'origine).

Francois

[FR119492]

Salut!

(par exemple une SVD de la matrice de départ au lieu d'une inversion de la matrice de variance covariance)

Je pense que fcharton a raison. La méthode SVD est malheureusement assez mal connue parce que rarement enseignée (trop mathématique pour les ingénieurs et pas assez pour les mathématiciens). En outre, elle est épouvantable à programmer; c'est pourquoi Numerical Recipes recommande d'utiliser une "boîte noire" toute faite comme on en trouve dans LAPack ou Matlab. Mais c'est aussi une méthode d'une stabilité remarquable, la méthode à utiliser quand plus rien d'autre ne marche.
Jean-Marc Blanc

[Bktero]

Merci pour vos conseils.

D'ailleurs, une version modifiée de l'algorithme qu'on m'a donné à tester consiste justement à ajouter "une petite diagonale".

Je vais regarder cette méthode SVD également.

Je pense en fait que l'algorithme Capon est un peu faible, c'est vrai qu'il est ancien. Si certains ont développé des versions améliorées, c'est peut-être en partie pour corriger ses problèmes de sensibilités au conditionnement.

[Invité]

Mais c'est aussi une méthode d'une stabilité remarquable, la méthode à utiliser quand plus rien d'autre ne marche.

En stats, elle présente un avantage supplémentaire : elle évite le calcul des matrices de variance covariance (la SVD se comporte comme une "racine carrée"). Il y en a quelques bonnes mises en oeuvre sur le web, sur netlib, ou dans NR (2eme edition et une autre dans la troisième).

A mon avis, cela fait réellement partie du petit nombre de fonctions sur lesquelles il vaut la peine de passer du temps. Bien comprendre les SVD, c'est aussi mieux comprendre pas mal de problèmes statistiques. En stats, elle est presque toujours indispensable : le mauvais conditionnement (aka multicollinéarité), c'est la situation normale d'un problème statistique (sinon, cela veut dire que la donnée ne contient par grand chose, en terme d'information...)

Maintenant, si c'est pour un usage peu fréquent, une petite diagonale ajoutée, et un coup de cholesky, ou quelque chose comme ca... Dans le cas de Capon, c'est peut être la meilleure solution, car ca va permettre de conserver l'alogrithme d'origine.

Francois