Optimiser le calcul d'intercorrélations qui se suivent, efficace ou non ?

[inviteafe1cd13]

J'espère poster sur le bon forum, je me soumets avec humilité aux fourches caudines si tel n'est pas le cas. Faites-moi mal.
C'est un problème que je fais sous matlab, mais le raisonnement pourrait être étendu en partie - c'est essentiellement un problème mathématique, d'où mon post dans cette section (je pense que matlab n'aide qu'à la marge en vectorisant certaines opérations - corrigez-moi si je me trompe)

Le problème est le suivant :
soit X et Y deux vecteurs de réels de longueur N, avec N trèèèèèèèèèès grand (une semaine échantillonnée à 500 Hz). Je vais soumettre à X et Y les outrages suivants :

Pour chaque entier j compris entre 0 et N-500
* je prélève un sous-échantillon de n=501 échantillons sur chaque vecteur X(j:j+500) et Y(j:j+500);
* je calcule R(j) le vecteur d'intercorrélation associé à X et Y tronçonné, d'après la formule pour m compris entre 0 et n-1
fin (boucle sur j)

Ca fait beaucoup de calculs. Enormément de calculs. Des calculs qui en plus se répètent souvent. En effet, regardons de plus près pour j=0 et j=1 (par facilité, le cas j-1 -> j doit se faire facilement) :
pour j=0, je fais
pour j=1, je fais
ie

Question 1 : suis-je dans le juste, ou me suis-je planté ? (fatigue, esprit rouillé)

"Chouette ! On peut alléger la charge du processeur !" me dis-je avec joie.

MAIS
MAIS
Mêêêê

En pratique, on calcule l'intercorrélation en faisant une FFT des deux signaux, un multiplication XY*, et une FFT inverse. Dans le cas présenté, on l'effectue N-500 fois. Je ne me souviens plus du temps d'opération de la fft ....

Là, que vais-je faire ?
Initialisation : je calcule pour j=0 l'intercorrélation de manière classique.
Pour j=1,N-501
Pour m=0,n-1

fin m
fin j
Donc je vais faire (N-501)*(n-1) opérations

Sachant que je travaille sous matlab pour des raisons de compatibilité avec mes collègues, sachant que matlab vectorise certaines opérations et qu'il utilise fftw :
question 2 (numérique) : est-ce que je gagne en temps à faire le calcul que je propose ?
question 3 (pratique) : .... je vais vraiment gagner un temps appréciable, ou je me casse la tête pour pas grand-chose ?
-----

[acx01b]

la fft est en O(n log n)
la convolution par fft : ton signal est de taille L, tu découpes en tronçons de N = 512 donc tu auras L fois à calculer la fft, la multiplication et la fft inverse donc au total tu auras un algo en O(L . N . log N)

avec ton algo, tu calcules R(j,m) en 2 multiplications + 2 additions donc en O(1), et ceci N.L fois pour avoir R(0 --> L, 0 --> 511), tu tiens donc un algo en O(N.L)

par contre tu n'auras pas exactement les même valeurs avec les 2 méthodes, car dans un cas il s'agit de convolution circulaire (fft) dans l'autre non, sauf si tu fais du zero padding quand tu calcules ta fft

enfin il n'est pas forcément intéressant de calculer la fft L fois, peut-être que tu pourrais te contenter de la calculer L/N fois en découpant ton signal en L/N tronçons indépendants

[inviteafe1cd13]

Merci pour la réponse. Donc j'ai une légère amélioration de la rapidité du calcul, en O(log(N)) ... Ca répond donc à la question 3 : mieux vaut optimiser ailleurs
(par exemple, sous-échantillonner)
Je retiens aussi ton autre suggestion, mais là j'ai un espèce d'attachement terrien atavique à exploiter chaque petit bout de donnée disponible. Attachement peut-être infondé, il faut que je rumine tout ça. Merci encore !

[invite986312212]

bonjour,

je te donne un avis de statisticien, qui vaut ce qu'il vaut: de deux choses l'une: ou bien tes processus sont stationnaires, et alors pour estimer les corrélations tu n'as besoin de regarder qu'une petite partie des données (pour estimer une corrélations, quelques milliers de valeurs suffisent amplement), ou bien tes processus ne sont pas stationnaires et alors ça n'a pas de sens de calculer la corrélation sur toute la durée mesurée. Il faut dans ce cas calculer une fonction de corrélation locale, par exemple à l'aide de transformée en ondelettes.

[A voir en vidéo sur Futura]