Les matheux sont dans la place - pt=prout

[IanPiotr]

Bah si c'est écrit correctement, la plus grande, c'est la plus grande, donc dans ton exemple, 82. Il y a des situations (genre en théories des chaînes de Markov) où le truc significatif c'est la plus grande en module, mais généralement on précise ("dominant eigenvalue", avec une petite explication).

Mais sinon, tu relis le papier, il doit y avoir une explication de pourquoi c'est telle valeur propre qui compte, et ça doit lever l'ambiguïté...

(Note que parfois, il y a des raisons de fond pour que la valeur propre réelle positive soit dominante, ce qui résoud les problèmes)

Le papier est un peu avare en explications de ce côté là ("the unit eigenvector corresponding to the maximum eigenvalue of Q is selected as the optimal rotation."). J'imagine qu'avec un meilleur niveau en maths je pourrais comprendre le fond du raisonnement et cela répondrait à mon interrogation, mais là je dois dire que j'applique la méthode plus que je ne la comprends. Du coup je vais partir sur la plus grande valeur, merci de ton aide.

[Anonyme20240202]

https://pdfs.semanticscholar.org/312...285a29684a.pdf

"largest positive eigenvalue" page 6, papier original de Horn

À l'arrache je dirais qu'il faut que tu comprennes d'abord le lien entre opération matricielle et rotation, et ensuite l'algorithme en lui même et pourquoi ils veulent maximiser cette fonction, ça a l'air intéressant en tout cas

[Anonyme20240202]

Ouais le début du papier que j'ai linké explique tout super bien (1. Intro et début du point 2.), en gros toute transformation se simplifie en une translation et une rotation, donc pour faire correspondre deux images il font de l'optimisation (minimise un truc) avec la méthode des moindres carrés https://fr.wikipedia.org/wiki/M%C3%A...es_carr%C3%A9s, apparemment le plus compliqué c'est de trouver la rotation

Le reste du papier c'est un espèce de blabla imbuvable qui fait correpondre quaternions et matrices (assez intuitif à comprendre), pas compris l'intérêt du bordel, j'ai vraiment du mal avec ce genre de jargon sur 400 lignes, peuvent pas s'expliquer simplement les mecs

La conclusion (6.) est aussi intéressante et résume bien le truc (et redit "most positive eigenvalue")

[IanPiotr]

https://pdfs.semanticscholar.org/312...285a29684a.pdf

"largest positive eigenvalue" page 6, papier original de Horn

À l'arrache je dirais qu'il faut que tu comprennes d'abord le lien entre opération matricielle et rotation, et ensuite l'algorithme en lui même et pourquoi ils veulent maximiser cette fonction, ça a l'air intéressant en tout cas

intéréssant ! et ça a le mérite d'être explicite.
Je suis d'accord, j'aimerais pouvoir prendre le temps de comprendre le fond de la démarche. Malheureusement, mes notions de maths sont bien trop incomplète (j'ai découvert les quaternions avec ce papier...), et je n'ai hélas pas le temps de m'y investir suffisamment. En tout cas, merci pour ces réponses rapides

[Laya]

Je suis un peu rouillé mais j'imagine qu'on prend la plus grosse valeur propre parce que c'est la direction qui correspond à la variation la plus importante du nuage de point.
C'est proche de ce que l'on fait lorsque l'on fait une PCA (analyse en composante principale), sauf que l'on projette ensuite sur le vecteur propre ayant la valeur propre la plus importante correspondant à la variance la plus importante.



Si je prend ce poisson on a représenté les 2 vecteurs propres, et le vecteur propre diagonal correspond au vecteur ayant la plus grande valeur propre. Tu remplaces le poisson par ton nuage de point et c'est pareil.

corrigez moi si je me trompe

[Anonyme20240202]

Le papier que j'ai linké est assez marrant en tout cas, au début le mec dit:

"Bon les branquignoles d'avant avaient du mal à faire correspondre deux couples de 3 points via une transformation, ensuite y'a d'autres branquignoles qui se sont ramenés avec des solutions pour plus de 3 points mais c'est des méthodes itératives dégueulasses, et enfin moi j'arrive avec une expression de forme fermée absolument nickel et j'explose la concurrence, lisez la suite:"

[Aghora]

C'est ça, tu as globalement résumé tout les articles scientifiques dans le domaine. Et puis les moindres carrés c'est très simple, surtout que les transfos sont linéaires.

[Shosuro Phil]

C'est ça, tu as globalement résumé tout les articles scientifiques dans le domaine. Et puis les moindres carrés c'est très simple, surtout que les transfos sont linéaires.

J'ai le déplaisant souvenir d'avoir fait des TD de méthodes numériques avec, en particulier, les moindres carrés... je ne maitrisais rien, j'avais mes notes, et j'essayais d'expliquer les transformations unitaires à des élèves ingénieurs que ça barbait encore plus que moi.

[Dsmii]

J'ai le déplaisant souvenir d'avoir fait des TD de méthodes numériques avec, en particulier, les moindres carrés... je ne maitrisais rien, j'avais mes notes, et j'essayais d'expliquer les transformations unitaires à des élèves ingénieurs que ça barbait encore plus que moi.

Si ça peut te donner une idée, la dernière fois que j'ai entendu parler d'opérations unitaires, c'était dans un pavé qui me servait de cours de maths en Sup'. Deux ans après, je crois que la seule chose dont je me souviens, c'est qu'on peut décomposer beaucoup de choses en composition de réflexions (et pire, en composition de transposition), mais j'ai jamais poussé beaucoup plus loin la logique.
Enfin, si, maintenant que je réfléchis à ce post, je me souviens vaguement d'un exercice de décomposition Matrice symétrique définie positive = ??? * Matrice de rotation (le titre de l'exo devait être genre S = M*oméga)). Mais j'aurais pas râlé sur un peu de dessin à l'époque pour expliquer les fondements de la chose, à l'instar de ce qu'a fait Laya !

[Anonyme20240202]

D'ailleurs dans la catégorie des vrais mathématiciens y'a l'excellent 3Blue1Brown qui explique tout ça proprement:

[Gobbopathe]

Si Youtube avait existé quand j'étais en prépa...

[ducon]

Il aurait dû colorer en rose values et en jaune vectors.

[Shosuro Phil]

Jusque là, c'est des choses qui étaient raisonnablement bien expliquées en prépa à mon époque. Surtout si on reste en deux braves dimensions...

[Aghora]

J'ai le déplaisant souvenir d'avoir fait des TD de méthodes numériques avec, en particulier, les moindres carrés... je ne maitrisais rien, j'avais mes notes, et j'essayais d'expliquer les transformations unitaires à des élèves ingénieurs que ça barbait encore plus que moi.

Eh bien si tu veux savoir, j'ai tendance à confondre ou pas les moindres carrés avec la pseudo-inverse. Desfois je me dis que c'est la même chose, desfois un truc différent. Je retiendrai jamais.

[BentheXIII]

Je recommande la lecture de ce papier pour comprendre pourquoi il s'agit bien de la plus grande valeur propre positive dont il est question. Le "Wahba problem" vise à trouver la parametrisation d'une matrice de rotation minimisant les RMS d'une fonction de coût associée, où chaque terme sommé correspond à || v_i - A(x) u_i|| ^2, où (v_i,u_i) sont deux vecteurs et A(x) la matrice orthogonale dont on cherche la parametrization optimale (au sens de la norme qu'on cherche à minimiser). Les deux problèmes sont assez proches !

Je te conseille ce papier qui fait le point sur différentes implémentations de l'ICP.


- - - Mise à jour - - -

Si ça peut te donner une idée, la dernière fois que j'ai entendu parler d'opérations unitaires, c'était dans un pavé qui me servait de cours de maths en Sup'. Deux ans après, je crois que la seule chose dont je me souviens, c'est qu'on peut décomposer beaucoup de choses en composition de réflexions (et pire, en composition de transposition), mais j'ai jamais poussé beaucoup plus loin la logique.
Enfin, si, maintenant que je réfléchis à ce post, je me souviens vaguement d'un exercice de décomposition Matrice symétrique définie positive = ??? * Matrice de rotation (le titre de l'exo devait être genre S = M*oméga)). Mais j'aurais pas râlé sur un peu de dessin à l'époque pour expliquer les fondements de la chose, à l'instar de ce qu'a fait Laya !

Ces méthodes sont toujours en vogue dans mon domaine pour justement éviter le recours à une méthode des moindres carrés / pseudo-inverse (c'est la même chose non? ) pour résoudre un système surdéterminé du type Hx = b (et surtout pour éviter le calcul de inv (H.T @ H)), dans le contexte d'un filtre de navigation tournant sur une machine ne disposant pas de la précision numérique requise pour ce genre de calculs.

[Dsmii]

Ces méthodes sont toujours en vogue dans mon domaine pour justement éviter le recours à une méthode des moindres carrés / pseudo-inverse (c'est la même chose non? ) pour résoudre un système surdéterminé du type Hx = b (et surtout pour éviter le calcul de inv (H.T @ H)), dans le contexte d'un filtre de navigation tournant sur une machine ne disposant pas de la précision numérique requise pour ce genre de calculs.

Par curiosité, et par flemmardise d'aller chercher sur Wikipédia quand je sais qu'il y a des gens très bien ici, comment vous prenez une décomposition plutôt qu'une autre, passé le "Déjà faut pouvoir décomposer selon telle forme" ? Dans quelle mesure on arrive à arbitrer entre précision (coucou les matrices à conditionnement pourrave) et vitesse de convergence ?
Et lorsqu'on peut décomposer, pourquoi utiliser les moindres carrés par exemple plutôt que la décomposition ? (Bon, OK, Cholesky, c'est tricher, mais quid de LU/QR vs moindres carrés ? )

EDIT : je viens de me relire et c'est pas clair, je parle pour la résolution d'un système linéaire Ax = b.

[Aghora]

Par curiosité, et par flemmardise d'aller chercher sur Wikipédia quand je sais qu'il y a des gens très bien ici, comment vous prenez une décomposition plutôt qu'une autre, passé le "Déjà faut pouvoir décomposer selon telle forme" ? Dans quelle mesure on arrive à arbitrer entre précision (coucou les matrices à conditionnement pourrave) et vitesse de convergence ?
Et lorsqu'on peut décomposer, pourquoi utiliser les moindres carrés par exemple plutôt que la décomposition ? (Bon, OK, Cholesky, c'est tricher, mais quid de LU/QR vs moindres carrés ? )

EDIT : je viens de me relire et c'est pas clair, je parle pour la résolution d'un système linéaire Ax = b.

Parce que ton égalité Ax = b, elle est pas exacte, c'est pourquoi on cherche la solution la plus proche possible, à l'aide des moindres carrés. Et là, c'est pseudo-inverse, ou SVD, suivant le rang de ta matrice A. Dans mes souvenirs.

Les décompositions dont tu parles sont des moyens de calculer l'inverse d'une matrice de manière optimisée numériquement.

[BentheXIII]

Pour compléter, y'a des cas marginaux où résoudre le problème surdéterminé Hx = b est rigoureusement équivalent à résoudre (H.T @ H) x = H.T @ b : si H est de rang plein (même rang que la dimension de x, ce qui est un minimum pour l'existence de la pseudo inverse), ET si b appartient à l'image de H, alors la solution (exacte) de (H.T @ H) x = H.T b est également la solution (exacte) de H x = b.

[Enyss]

Au passage, une façon intéressante de voir la méthode des moindres carrés, c'est de la comprendre en termes de projection dans un espace de Hilbert.

Les données x=(x_i) sont un point d'un espace de Hilbert R^n, et on a un sous espace vectoriel E de R^n composé de toutes les fonctions (= points de l'espace de Hilbert) admissibles. La fonction qui minimise le carré de la différence, c'est simplement la projection de x sur E. Et vu de cette façon, on obtient l'unicité "gratuitement", et même la façon de calculer cette projection (si on connait un peu les espaces de Hilbert)

Au passage, on n'a pas forcément si on minimise selon d'autres normes. En gros, si la boule unité n'est pas strictement convexe, on n'a pas forcément unicité, par exemple si on veut minimiser la somme de la valeur absolue de la différence (norme L1) ou encore minimiser le maximum de la différence (norme L-infini)

[BentheXIII]

Et pour reboucler avec Enyss, l'espace vectoriel engendré par les colonnes de la matrice H (l'image de H) n'est autre que ce fameux sous-espace E.

[Shosuro Phil]

Au passage, on n'a pas forcément si on minimise selon d'autres normes. En gros, si la boule unité n'est pas strictement convexe, on n'a pas forcément unicité, par exemple si on veut minimiser la somme de la valeur absolue de la différence (norme L1) ou encore minimiser le maximum de la différence (norme L-infini)

Et aussi, est-ce que ce serait aussi simple de minimiser la distance pour d'autres normes? Rien qu'en se limitant aux normes L1 et L-infini, je ne suis pas sûr que "projeter" sur un sous-espace (au sens, trouver un point du sous-espace qui minimise la distance) soit faisable computationnellement.

[Enyss]

Une simple descente de gradient va marcher, puisque y->||x-y|| est une fonction convexe sur E.

[Shosuro Phil]

Une simple descente de gradient va marcher, puisque y->||x-y|| est une fonction convexe sur E.

Je me posais la question du point de vue computationnel, pour un résultat exact (sous hypothèse que les calculs sont exacts). La descente de gradient, c'est une méthode approchée.

[Enyss]

Désolé, j'ai interprété "computationnelle" comme la traduction du terme anglais "computational". Je n'avais jamais rencontré le terme computationnel en maths pour parler des méthodes exactes.

[Shosuro Phil]

C'est parce que je suis pas matheux, je suis informaticien Le terme n'est pas vraiment utilisé, en fait. J'aurais pu utiliser "algorithmique", mais c'est pareil, le terme est beaucoup utilisé par les matheux pour désigner des méthodes approchées.

[Anonyme20240202]

Y'a rien de plus rigoureux qu'un compilateur (bien fait), l'informatique c'est les vrais matheux

Nan je blague (à moitié) mais en ce moment je me fais pas mal de réflexions sur le sujet:

Si on veut une vraie rigueur ne devrait ont pas garantir l'analyse lexicale correcte des maths par une machine, donc en gros la compilation?
Avec bien sûr une attention particulière à la lisibilité par un humain. De la même manière que ce que tentent de faire les langages informatiques de plus en plus (maximum de fonctionalités et de "puissance" avec un maximum de clarté et accessoirement de brieveté)

J'imagine qu'il y a certainement des termes appropriés (comment on qualifie un langage cohérent, que l'on peut Parser/faire l'analyse lexicale https://en.wikipedia.org/wiki/Lexical_analysis, sans ambiguité?)

Je sais que y'a déjà des trucs similaire qui doivent exister (https://en.wikipedia.org/wiki/Proof_assistant) (https://en.wikipedia.org/wiki/Lambda_calculus)

Et je me doute que Turing et Godel risquent de se pointer (https://en.wikipedia.org/wiki/Halting_problem) (https://en.wikipedia.org/wiki/G%C3%B...eness_theorems)

---

Mais il apparait assez clairement que y'a tout un tas de notations et de mécaniques qui ont été conservées en maths pour des raisons purement historiques ou autre raison relativement arbitraire, sans AUCUNE considération de rigueur ou de praticité.
Par opposition à des notations et des mécaniques choisies spécifiquement dans un but précis.

Un exemple un peu contrit et sûrement maladroit pour donner l'idée de ce que j'essaye de dire:

Si t'écris √2 + 3²

T'as deux opérateurs unaires, mais y'en a un qui donne lieu à une opération de durée indéfinie, sauf que ça n'apparait pas immédiatement à la lecture, l'algorithme pour la racine d'un nombre et celui pour le carré d'un entier sont différents mais aucun temps de calcul ni rien n'apparait dans l'opération.

De même la notation en base 10:
34 est évidemment pair
37 est impair
6534698465468748641867 est impair

Ça apparait immédiatement du fait de la notation, mais si j'écris un nombre en base 1, avec le point "." comme unité:
.................................................. .......................

Vous êtes incapable de dire si c'est pair ou impair puisqu'il faut dénombrer le nombre auparavant.

Et ça aussi n'apparait pas.

Donc bon encore une fois c'est super maladroit et je ne suis pas bien au courant de la recherche actuelle sur le sujet, mais j'ai toujours été hyper frustré, notamment dans mes études, de l'arbitraire et du gloubiboulga absolument infâme qui est utilisé partout. Y'a toute une complexité artificielle qui apparait du fait de l'exotisme, de l'arbitraire, du jargon des notations, et tu passes plus de temps à t'accomoder des notations et de cet arbitraire plutôt que de comprendre le concept fondamental derrière.

S'pour ça que je fais souvent de la pub pour la chaine youtube 3Blue1Brown, mais le succès de cette chaine est le témoin incontestable, un symptome évident, de ce problème.

Aussi pour aller plus loin, pourquoi se restreindre à des représentations sous forme de caractères, y'a plein de concepts mathématiques qui seraient peut-être plus évident sous forme de représentation vidéo, l'imprimerie c'est ringard, on peut même se passer des mots

Un exemple classique c'est ce genre d'images qui deviennent très populaires sur internet



J'ai pas l'impression que y'ait une grosse remise en cause des notations mais personellement j'ai toujours trouvé ça complètement illisible et incohérent

- - - Updated - - -

Comme dirait Neumann

Young man, in mathematics you don't understand things. You just get used to them.

Et pour finir la vidéo que je re poste à chaque fois:



- - - Updated - - -

Et pour finir ouais, le pire c'est que lors de conférence ou autre, tous les mathématiciens qui s'expriment vont quasiment systématiquement parler des "images mentales" qu'ils utilisent pour appréhender tel ou tel concept, en s'excusant à chaque fois "c'est pas très rigoureux mais ça m'aide" alors que ça détient peut-être plus de vérité que l'explication "rigoureuse" qui suit. Qui purement mécaniquement est rigoureuse mais tu peux toujours écrire un programme très simple en 2000 lignes de code, alors que 3 suffisent. La véracité d'un enchainement de notations est différent de la vérité fondamentale du concept sous jacent, qu'on peut aussi peut-être qualifier de "compréhension".

[Shosuro Phil]

Y'a rien de plus rigoureux qu'un compilateur (bien fait), l'informatique c'est les vrais matheux

Je suis bien d'accord (mais quand je dis que je ne suis pas un matheux, la moitié de mes collègues pouffent, hein - je suis un informaticien qui a une agrég de maths, et pas avec l'option info).

Je sais que y'a déjà des trucs similaire qui doivent exister (https://en.wikipedia.org/wiki/Proof_assistant) (https://en.wikipedia.org/wiki/Lambda_calculus)

Et je me doute que Turing et Godel risquent de se pointer (https://en.wikipedia.org/wiki/Halting_problem) (https://en.wikipedia.org/wiki/G%C3%B...eness_theorems)

Ils sont partout, ces deux gredins. C'est même pour ça que les assistants de preuve s'appellent assistants, et pas prouveurs: ce qu'on peut vraiment démontrer de manière automatisée est trop faible; résultat, c'est un humain qui utilise le logiciel pour trouver le chemin de preuve, et le logiciel se "contente" de vérifier que tout est correct. Et on laisse les philosophes décider de si l'esprit humain est capable de faire des choses de manière non algorithmique.

(Ça, c'est l'idéal; en pratique, tant qu'on n'est pas un utilisateur expert, on passe son temps à se battre pour faire comprendre à cet abruti qu'on veut faire ci ou ça)

[Gobbopathe]

Dans le même genre je me rappelais avoir mis beaucoup d'efforts à visualiser le dessin de la cycloïde, et j'ai vu récemment une vidéo de ce type, ça m'a ramené quelques années en arrière...

[Anonyme20240202]

Exactement on devrait remplacer le mot cycloïde par un lien hypertexte vers la vidéo d'un cycloïde!

[ducon]

Je suis bien d'accord (mais quand je dis que je ne suis pas un matheux, la moitié de mes collègues pouffent, hein - je suis un informaticien qui a une agrég de maths, et pas avec l'option info).

Un agrégé de maths qui n’est pas un matheux.
Bretzel liquide.