Les matheux sont dans la place - pt=prout

**BentheXIII** · 04/03/2017, 06h37

Coin,

j'ai affaire à un problème de regression polynomiale en présence de bruit. Je cherche à fitter trois angles (fonctions du temps) au moyen d'une base polynomiale de dimension N. Je dispose de mesures (bruitées) des angles. Les inconnues du problème sont donc les N+1 vecteurs de R3 x0, x1,...,xN.

Ce modèle linéraire equivaut donc à écrire les trois angles Y = [y1,y2,y3].T en fonction du temps comme

Y(t) = [I_3, t * I_3, t^2/2 I_3,...,t^N/N I_3] [x0.T,x1.T,...,xN.T] (qui est bien à valeur dans R3)

C'est un problème de moindre carré élémentaire en absence de bruit, mais qui se comporte relativement salement une fois les mesures corrompues. Un exemple ci-dessous: à gauche, les normes des coefficients x0,x1,...xN pour un fitting en absence de bruit. A droite, la même avec un bruit de mesure.

(j'ai un excellent à priori sur x0 que je sais nul par avance, d'où sa valeur)

Là où ça devient grave, c'est que je suis intéressé par Y(t), mais également par ses dérivées première et seconde en fonction du temps. Et l'explosion en norme des termes de plus haut degré vient introduire des oscillations foutant le dawa

Je sais que les "angles" que je mesure ont en réalité un comportement seulement continu par morceau, et de surcroit semblable à celui de x |--> tan(x). Employer une série de fourier est donc probablement une mauvaise idée car en absence de contenu fréquentiel clairement identifiable, le bruit blanc Gaussien va venir perturber toutes les harmoniques (sans parler de la vitesse de décroissance des coefficients qui risque de ne pas être bien follichone).

Bref. Je me dis que la régression polynomiale en présence de bruit gaussien doit pas être bien nouvelle. J'ai trouvé ce papier comme point de départ sur le Kernel Filtering (http://www.stat.ucla.edu/~cocteau/st...hba_spline.pdf) et me demandait si les sorcier(e)s du topic avaient des idées sur le sujet.

**ducon** · 04/03/2017, 13h30

C’est parce que les polynômes de Lagrange ne sont pas les bons pour un problème comme le tien. Essaie plutôt de travailler avec une norme comme la norme 1, la norme 2 ou la norme sup.
Par exemple, essaie cette norme sur ton espace N(f)+N(df)+N(d²(f)) où N est une des trois normes classiques précédentes.

**Dr.Kant** · 04/03/2017, 15h50

Dans la meme veine, renseignes toi sur les methodes de regularisation https://en.m.wikipedia.org/wiki/Tikhonov_regularization
Mais l'idee de Ducon est bonne, il faut inclure ce que tu cherches a mesurer dans ton score.

**BentheXIII** · 04/03/2017, 18h15

Merci pour les suggestions. J'avais tenté quelque chose de similaire en réecrivant la fonction de coût de

à

Par contre, j'ai un problème de pondération des différentes normes entre elles si je veux N(f) -> 0, N(df)+N(d²(f)) devront rester contenues, mais non nulles. Et j'ai peur que trouver une combinaison de gain qui marche n'apporte pas de garanties avec un autre signal de mesure légèrement différent.

Il y a certainement une méthode analytique pour relier l'incertitude dans N(f) (directement liée à la précision des mesures, au travers de leur matrice de covariance) à celle dans N(df) et N(d²(f)) .

@Kant: je connaissais ce truc sous le nom de Ridge estimation, je vais voir ce que ça donne

**Aghora** · 04/03/2017, 19h49

Tu as un modèle d'état et un modèle d'observation si j'ai bien compris ? Pourquoi pas Kalman ? (bon, j'ai lu très vite aussi)

(et on voit pas tes formules)

**Eradan** · 04/03/2017, 20h05

Extension SmartReferer pour Firefox, et il en existe une équivalente pour Chrome.

**BentheXIII** · 04/03/2017, 20h21

Envoyé par Aghora

Tu as un modèle d'état et un modèle d'observation si j'ai bien compris ? Pourquoi pas Kalman ? (bon, j'ai lu très vite aussi)

(et on voit pas tes formules)

parce que je ne connais pas la dynamique sous-jacente. Les angles sont gouvernés par leur équation cinématique, fonction de la vitesse angulaire, dont la dérivée (l'accélération) est affectée par un tenseur d'inertie... que je ne connais pas. Donc pas possible de propager l'à-priori.

Bizarre pour les formules. Elles sont hébergées sur Imgur mais je les vois bien apparaitre

**TarteAuxFleurs** · 04/03/2017, 20h38

Envoyé par BentheXIII

parce que je ne connais pas la dynamique sous-jacente. Les angles sont gouvernés par leur équation cinématique, fonction de la vitesse angulaire, dont la dérivée (l'accélération) est affectée par un tenseur d'inertie... que je ne connais pas. Donc pas possible de propager l'à-priori.

Bizarre pour les formules. Elles sont hébergées sur Imgur mais je les vois bien apparaitre

Tu vois les formules car c'est toi qui les as postés et que du coup, elles sont déjà en cache dans ton navigateur

**yanad** · 08/03/2017, 10h36

Salut,

J'ai un probleme de comprehension sur la methode des differences finis. En gros j'essaye de programmer l'algorithme STOMP et je bloque betement sur l'implementation de la matrice suivante :

Deja je ne comprends pas trop leur notation qui passe d'une ligne de -2 en dessous de la diagonale a une ligne de -2 au dessus

J'ai tente de repartir de la definition de la matrice mais rien a faire je ne retrouve pas leurs matrice

Une idee ?

**Helix** · 08/03/2017, 10h51

A mon avis, la matrice A n'est pas carrée tout simplement. La différence finie porte sur trois échantillons. En ne gérant pas les bords, avec un signal d'entrée de N valeurs, tu obtiens une sortie avec N-2 valeurs.
Ta sortie est calculée par y(n) = x(n-1) - 2x(n) + x(n+1).

**yanad** · 09/03/2017, 07h01

C'etait bien ca, merci beaucoup

**Anonyme20240202** · 04/04/2017, 17h47

Je me sens très con, ça fait des années et des années que je me dis qu'il faudra que je comprenne (vraiment comprendre) la transformée de fourier. Bon pour excuse je l'utilise/la manipule absolument jamais, mais la je m'intéresse un peu au traitement du signal et j'ai toujours trouvé ça assez puissant d'extraire les données fréquentielles d'un signal donné (prière de ne pas m'étrangler pour cette formulation vulgaire).

Bon bref, ça paraitra surement évident pour ceux qui l'utilisent régulièrement mais la formule est en fait assez intuitive (en anglais):

https://web.archive.org/web/20120418...ier-transform/

http://toxicdump.org/stuff/FourierToy.swf

Après je me demande si la formule est l'algorithme le plus optimal pour obtenir ce résultat, je formule sûrement mal ma question, mais en gros est-ce qu'il n'y a pas plus malin pour obtenir le même résultat?

J'ai entendu parler de la FFT, je vais lire l'article wiki à ce sujet, mais c'est des algos qui convergent rapidement vers le bon résultat avec une précision arbitraire c'est ça? https://fr.wikipedia.org/wiki/Transf...Fourier_rapide

Je suis curieux de savoir comment Fourier en est arrivé là aussi. J'ai lu l'histoire vite fait mais pour l'instant je pige absolument pas comment on passe de la propagation de la chaleur aux séries de Fourier

**Souly** · 04/04/2017, 18h20

La FFT, c'est un algorithme (y'en a plusieurs) pour calculer, de manière exacte, la transformée de Fourier discrète. On l'appelle rapide car elle effectue un nombre d'opérations arithmétiques (multiplication et addition) proportionnel à N log N, où N est le nombre d'échantillons de ton signal.
En effet, si on regarde naïvement la définition de la transformée de Fourier, il y a N^2 multiplications à calculer (N multiplications pour chacune des N fréquences). N log N est donc une amélioration conséquente du temps de calcul.

Savoir si on peut faire mieux, au sens plus rapide, est une vaste question, pas vraiment résolue. Dans certains cas, y'a des bornes inférieures, dans d'autres on sait pas. D'après Wikipédia, on peut faire mieux que N log N multiplications (linéaire en N), mais au prix de beaucoup trop d'additions, donc c'est pas rentable.

Mais déjà, N log N, dans la pratique, c'est très bien. Pour un échantillonnage d'1 million de mesures, on est de l'ordre de 6 millions, à comparer aux mille milliards de multiplications qui seraient nécessaires en faisant le calcul bêtement. Et il semble assez clair qu'on ne pourra pas descendre en dessous d'une complexité linéaire (ou alors on 'oublie' des mesures), on voit rapidement que 6 millions, c'est pas loin d'1 million, donc quasiment optimal dans la pratique.

**Anonyme20240202** · 04/04/2017, 18h26

Ok je vois merci, c'est donc une "vraie" amélioration, pas simplement une approximation, j'irai lire les détails, je pense que je vais implémenter la FFT pour un projet perso

(j'ai sûrement déjà du faire ça en TP à l'école mais la pédagogie aux fraises donnait pas envie, on te crache la formule comme ça, une vieille explication d'un prof qui a souvent mal compris lui-même et exercice abstrait).

**Souly** · 04/04/2017, 18h29

Envoyé par Kamikaze

Ok je vois merci, c'est donc une "vraie" amélioration, pas simplement une approximation, j'irai lire les détails, je pense que je vais implémenter la FFT pour un projet perso

(j'ai sûrement déjà du faire ça en TP à l'école mais la pédagogie aux fraises donnait pas envie, on te crache la formule comme ça, une vieille explication d'un prof qui a souvent mal compris lui-même et exercice abstrait).

Y'a aussi des approximations, mais ce n'est plus de la vraie FFT.

Pour l'aspect historique, je suppose que ça doit venir du fait que la propagation de la chaleur, c'est une équation différentielle pas linéaire, et que Fourier a cherché à se ramener à des fonctions qui s'intègrent bien, donc des fonctions trigonométriques. Et comme la transformée de Fourier, c'est la décomposition d'une fonction en sommes de fonctions trigo...

**Møgluglu** · 04/04/2017, 18h36

Envoyé par Souly

Mais déjà, N log N, dans la pratique, c'est très bien. Pour un échantillonnage d'1 million de mesures, on est de l'ordre de 6 millions, à comparer aux mille milliards de multiplications qui seraient nécessaires en faisant le calcul bêtement. Et il semble assez clair qu'on ne pourra pas descendre en dessous d'une complexité linéaire (ou alors on 'oublie' des mesures), on voit rapidement que 6 millions, c'est pas loin d'1 million, donc quasiment optimal dans la pratique.

La FFT a aussi l'avantage d'être numériquement stable et facilement parallélisable. Par contre, malgré sa complexité algorithmique avantageuse, c'est un algo qui ne passe pas bien à l'échelle à cause de sa mauvaise localité. (Ce que les théoriciens considèrent comme un détail d'implémentation, et les expérimentalistes comme une grossière erreur du modèle théorique.) Enfin c'est un problème pour des grosses grosses FFT à l'échelle d'un supercalculateur, pas celles que tu fais tourner sur ton PC.

Kamikaze: oui, tu peux l'implémenter toi-même, en 1D et 2D ça se fait bien, et ensuite tu pourras te comparer avec la bibliothèque FFTW...

**Souly** · 04/04/2017, 18h41

Envoyé par Møgluglu

La FFT a aussi l'avantage d'être numériquement stable et facilement parallélisable. Par contre, malgré sa complexité algorithmique avantageuse, c'est un algo qui ne passe pas bien à l'échelle à cause de sa mauvaise localité. (Ce que les théoriciens considèrent comme un détail d'implémentation, et les expérimentalistes comme une grossière erreur du modèle théorique.) Enfin c'est un problème pour des grosses grosses FFT à l'échelle d'un supercalculateur, pas celles que tu fais tourner sur ton PC.

Kamikaze: oui, tu peux l'implémenter toi-même, en 1D et 2D ça se fait bien, et ensuite tu pourras te comparer avec la bibliothèque FFTW...

Je ne sais pas ce qu'est la localité. Je suis un matheux, moi

**Vautour** · 04/04/2017, 18h57

Bah, des localités pour mieux comprendre les systèmes de fusion.
http://users.dimi.uniud.it/~mario.ma...3/Chermak1.pdf

**Souly** · 04/04/2017, 19h03

Envoyé par Vautour

Bah, des localités pour mieux comprendre les systèmes de fusion.
http://users.dimi.uniud.it/~mario.ma...3/Chermak1.pdf

Ah bah si c'est ça alors ça va.

Bon ok, mon cerveau s'est mis en veille dès l'abstract.

**Aghora** · 04/04/2017, 19h08

Envoyé par Kamikaze

Ok je vois merci, c'est donc une "vraie" amélioration, pas simplement une approximation, j'irai lire les détails, je pense que je vais implémenter la FFT pour un projet perso

(j'ai sûrement déjà du faire ça en TP à l'école mais la pédagogie aux fraises donnait pas envie, on te crache la formule comme ça, une vieille explication d'un prof qui a souvent mal compris lui-même et exercice abstrait).

Attention au gain de la FFT, surtout si tu fais de l'embarqué !
http://www.analog.com/media/en/train...als/MT-003.pdf

- - - Mise à jour - - -

Envoyé par Souly

Pour l'aspect historique, je suppose que ça doit venir du fait que la propagation de la chaleur, c'est une équation différentielle pas linéaire, et que Fourier a cherché à se ramener à des fonctions qui s'intègrent bien, donc des fonctions trigonométriques. Et comme la transformée de Fourier, c'est la décomposition d'une fonction en sommes de fonctions trigo...

C'est pas les séries de Fourier ça plutôt ? Où chaque coeff est égal à la transfo de Fourier ?

@Kamikaze : si tu t'intéresses à la théorie de la TF, regardes du côté de la théorie de la mesure et de l'intégrale de Lebesgue.

**Souly** · 04/04/2017, 19h12

Envoyé par Aghora

C'est pas les séries de Fourier ça plutôt ? Où chaque coeff est égal à la transfo de Fourier ?

Euh, c'est pareil, non ? Vision selon les coeff ou selon la série ?

**Aghora** · 04/04/2017, 19h16

Envoyé par Souly

Euh, c'est pareil, non ? Vision selon les coeff ou selon la série ?

Pas tout à fait, pas dans mes cours.
https://fr.wikipedia.org/wiki/S%C3%A9rie_de_Fourier

Ce que j'appelle transformée de Fourier, c'est la relation qui te donne ce qu'ils appellent les coefficients de Fourier de la série.

Notez aussi que les traiteurs de signaux ne s'emmerdent plus vraiment à faire des intégrales. Ils ont un formulaire et on nous disait "Trouvez moi un seul signal dans la nature qui ne soit pas intégrable !".

**Helix** · 04/04/2017, 19h20

Ne pas confondre séries de Fourier et transformée de Fourier.
Les séries de Fourier permettent de décomposer une fonction périodique en une somme infinie (une série) de sinusoïdes déphasées. Les coefficients donnent l'amplitude et la phase de chaque sinusoïde. Le spectre est discret.
La transformée de Fourier permet faire la même chose sur des fonctions fonctions non-périodiques, mais alors la série (somme discrète) devient une intégrale (somme continue). Le spectre est continu.

**Souly** · 04/04/2017, 19h23

Envoyé par Helix

Ne pas confondre séries de Fourier et transformée de Fourier.
Les séries de Fourier permettent de décomposer une fonction périodique en une somme infinie (une série) de sinusoïdes déphasées. Les coefficients donnent l'amplitude et la phase de chaque sinusoïde. Le spectre est discret.
La transformée de Fourier permet faire la même chose sur des fonctions fonctions non-périodiques, mais alors la série (somme discrète) devient une intégrale (somme continue). Le spectre est continu.

Ouais, j'étais approximatif. Mais on parlait de transformée de Fourier discrète à l'origine, donc spectre discret et fonction supposée périodique (même si ce n'est pas le cas) ?

**Aghora** · 04/04/2017, 19h25

La TFD, c'est bien une somme sur N points de ton signal, multiplié par l'exponentielle complexe.

**Møgluglu** · 04/04/2017, 20h02

Envoyé par Souly

Je ne sais pas ce qu'est la localité. Je suis un matheux, moi

Le fait que dans la vraie vie, prendre un bouquin sur une étagère qui en contient 10 ça va plus vite que prendre le même bouquin dans la bibliothèque qui en contient 10000, même quand tu sais exactement où il est. Faut avoir une conception très spéciale des lois de la physique pour imaginer qu'on peut accéder à un élément quelconque d'un tableau de taille n en temps constant indépendant de n.

Enfin c'est hors sujet ici, on a déjà montré que la solution existe et qu'elle est unique.

Envoyé par Vautour

Bah, des localités pour mieux comprendre les systèmes de fusion.
http://users.dimi.uniud.it/~mario.ma...3/Chermak1.pdf

Exactement.

(Je suis arrivé jusqu'aux remerciements cachés à la fin de l'intro.)

**ducon** · 04/04/2017, 20h05

Envoyé par Souly

Je ne sais pas ce qu'est la localité. Je suis un matheux, moi

C’est pourtant une notion mathématique mais je n’en sais pas plus moi non plus.

**Helix** · 04/04/2017, 20h12

Envoyé par Souly

Ouais, j'étais approximatif. Mais on parlait de transformée de Fourier discrète à l'origine, donc spectre discret et fonction supposée périodique (même si ce n'est pas le cas) ?

Oui oui. Je n'ai pas dit que tu avais tord, mais je voulais simplement préciser le vocabulaire

Et tu as également raison de souligner le fait que le signal discret est supposé périodique (c'est toujours un bon moment lorsque j'explique à mes étudiants l'origine de telle ou telle structure dans la TFD d'une image).

**Vautour** · 04/04/2017, 21h57

Envoyé par Møgluglu

Exactement.

(Je suis arrivé jusqu'aux remerciements cachés à la fin de l'intro.)

J'ai pas lu le papier, mais j'ai assisté deux fois à un exposé d'un coauteur de l'auteur du papier

Bien expliquées, les localités ça semble cool

**Autiste Redding** · 19/04/2017, 05h34

Salut les matheux. Je viens vers vous avec une énigme concoctée par un ami de ma compagne (qui a un doctorat en mathématiques).
Voici la colle :
Si vous en avez marre de la géométrie, voici une énigme combinatoire:

On dispose de douze pièces d'apparences identiques.
Parmi elles, une et une seule est fausse.
Son poids diffère de celui des pièces authentiques.
On dispose d'une balance à deux plateaux, elle permet de comparer le poids de deux ensembles de pièces.
Montrer que l'on peut, en au plus trois pesées, dire quelle pièce est fausse
et si elle est plus lourde ou plus légère que les pièces authentiques.

Bon courage!"
Le parrain de mon fils, fan de casse-têtes en tout genre a séché en étant à ce stade :

je trouve en 3 pesées 3 fois sur 4 mais le 4ème cas c'est 4 pesées...

Bon courage, les élèves de l'auteur en chie...

Discussion: Les matheux sont dans la place - pt=prout

Outils de la discussion

Règles de messages