Celebratio Mathematica

Dear Yves,

You asked me what I’m up to, and what Car­oline is do­ing…

Car­oline is al­most walk­ing: she can stand up, without sup­port, for 10 or 15 seconds, and when she has a sup­port (our hands, or a piece of fur­niture) she takes little steps. She’s al­ways happy and is a real joy… ex­cept at night, when she still wakes up very of­ten and asks for mommy.

As to the mommy, she has been con­sid­er­ing the curi­ous setup I’m go­ing to de­scribe to you.

Jim John­ston (who Al­bert knows well) told us long ago (a year) that he’d like to have a setup to pro­duce wave­let pack­ets, but where he’d be able to change mid­stream the base be­ing used. When we ob­tained bases on the in­ter­val with an equal num­ber of scale func­tions and wave­lets for each res­ol­u­tion, we told him that we had de­vised something that did ex­actly what he wanted: you could chop it in­to pieces, and cre­ate op­tim­al pack­ets for each piece.

(In par­en­theses: When I learned the con­struc­tion of “loc­al­ized sine” bases — in con­nec­tion with which, so the en­gin­eer­ing folks tell me, I should cite not only Mal­var, but also Prinsen and Brad­ley, who were cited in Mal­var’s art­icle and had already come up with some of the ideas — I poin­ted it out to John­ston right away as a solu­tion. But he prefers wave­let pack­ets, be­cause they al­low the use of dif­fer­ent res­ol­u­tions at once. That is, if you have a low-fre­quency sig­nal from \( t_0 \) to \( t_1 \), but also little ke­bab bites of high fre­quency from \( t_2 \) to \( t_3 \) and from \( t_4 \) to \( t_5 \), where \( t_0 < t_2 < t_3 < t_4 < t_5 < t_1 \), then with wave­lets you can mod­el the low fre­quen­cies throughout the whole win­dow \( t_0 \rightarrow t_1 \), while us­ing the little win­dows for the high fre­quen­cies. With a setup such as Mal­var’s, you’d have to cut everything in­to pieces, even for the low fre­quen­cies. Ap­par­ently, that’s a real prob­lem for chunks of mu­sic with mul­tiple in­stru­ments, ac­cord­ing to John­ston (who tried to im­ple­ment Prinsen and Brad­ley).)

But he didn’t like that reply! Even though we were cut­ting things in a way that did not ru­in the reg­u­lar­ity! Us­ing an ar­gu­ment of Al­bert’s, I ex­plained to him that it’s as if we were ex­tend­ing the func­tion smoothly and then de­com­pos­ing that ex­ten­sion. The reas­on he re­jec­ted it is this: sup­pose that you re­con­struct the sig­nal after round-off, or quant­iz­a­tion, or some oth­er pro­cess that adds noise to the coef­fi­cients. Then, from the very fact that the wave­lets on the in­ter­val have an ab­rupt edge at the end of the in­ter­val, the re­con­struc­tion after noise will have dis­con­tinu­it­ies. Worse yet: er­rors in the coef­fi­cients cor­res­pond­ing to very low fre­quen­cies can lead to such dis­con­tinu­it­ies, which is to say, to high-fre­quency er­rors. Veeerry bad, says J.J.

So, I’ve thought up the fol­low­ing hy­brid scheme:

• Sup­pose we want blocks of size \( T \), with a dif­fer­ent basis of wave­let pack­ets on each block.

• We start by de­com­pos­ing, and ap­ply­ing all pos­sible fil­ters to, all the data between 0 and \( T+\Delta T \), where \( \Delta T \) is chosen so that, even at the coarsest res­ol­u­tion, no func­tion has sup­port great­er than \( \Delta T \).

(I’m as­sum­ing that we have de­cided a pri­ori not to go bey­ond a fixed num­ber of con­sec­ut­ive fil­ters.) It doesn’t much mat­ter what we do at the edge \( T+\Delta T \). (In prac­tice, I think it’s best to use your wave­lets on the in­ter­val for this edge, for the time be­ing.)

• We now de­cide which, among all pos­sible bases, is the op­tim­al one. (That is, we de­cide about the op­tim­al tiling for this chunk of sig­nal. Since we are us­ing the in­ter­val \( 0 \rightarrow T + \Delta T \) for that de­cision, where­as later on we will re­strict to \( 0\rightarrow T \), the de­cision might not in fact be op­tim­al, but I don’t know how to fix this.)

• This de­cision taken, we take a step back. The goal, for this chunk \( 0\rightarrow T \), is to use only func­tions whose sup­port have non­trivi­al in­ter­sec­tion with \( [0,T] \). In fact, the an­swer is giv­en by your con­struc­tion, but I’m go­ing to choose not to or­thonor­mal­ize at the end (for reas­ons I’ll ex­plain be­low). I want the chosen su­per­pos­i­tion to re­pro­duce ex­actly the sig­nal on \( [0,T] \), and I will use only wave­let pack­ets that are not mod­i­fied at the end. Some of them will have a tail go­ing bey­ond \( T \) — and those tails will be very im­port­ant, but I don’t want to dis­tin­guish them ex­cept for the part con­tained in \( [0,T] \). This means I should elim­in­ate cer­tain pack­ets: every time I use a split­ting with \( m_0 \) and \( m_1 \), the fil­ters at the very end us­ing \( m_1 \) only yield lin­ear com­bin­a­tions of what’s giv­en by hav­ing \( m_0 \) at the end. (It was you who ob­served that the \( \psi_{j,k}|_{[0,T]} \) that have less than half their sup­port in the in­teri­or of \( [0,1] \) are in fact lin­ear com­bin­a­tions of the \( \phi_{j,k}|_{[0,1]} \).) More con­cretely: \[ \eqalign{ \psi& (x) = \sum^{N-2}_{n=0} a_n \phi(x-n) &+ &Q(x)\cr &\uparrow &&\downarrow\cr &\text{ support }&&\text{tail,} \cr &[0, 2N-1] &&\text{having support }\cr &&&[N-1,2N-1]\cr } \] where \[ \eqalign{ a_0 &= \frac{h_{2N-1}}{h_0},\cr a_n &= \frac{h_{2N-1-2n} - h_{2n} a_{n-1}}{h_0}. } \] A com­pletely ana­log­ous for­mula holds for \( m_1 (\xi), m_0(\xi) \). So, each time that I do a split­ting at en­d­point \( T \), I trans­fer the \( N-1 \) coef­fi­cients from the end of the \( m_1 \) band to the \( m_0 \) band (us­ing the for­mula above), and I drop the \( N-1 \) cor­res­pond­ing taps in the \( m_1 \) band.

The res­ult is in­deed a rep­res­ent­a­tion of \( f \) by wave­let pack­ets, which re­pro­duces \( f \) ex­actly in \( [0,T] \) and where each edge pack­et has a tail ex­tend­ing bey­ond \( T \) of a size match­ing its res­ol­u­tion.

(Those tails are the reas­on why I haven’t used your setup dir­ectly: if I use the coef­fi­cients res­ult­ing from or­thonor­mal­iz­a­tion, I’m able to write down a nice tail for \( \psi \), but for wave­let pack­ets in­cor­por­at­ing sev­er­al \( m_1 \)’s, my tails be­come ever short­er, which is not the de­sired ef­fect. Moreover, the pro­ced­ure here is sim­pler down the line.)

• Now we move on to the next block. I start by tak­ing the dif­fer­ence between \( f|_{[T, \infty]} \) and the “tails” of the pre­vi­ous block. That is, \[ \eqalign{ f|_{[0,T]}(x) &= \sum_{\alpha}c^0_{\alpha} \phi_{\alpha} (x)|_{[0,T]} \quad(\phi_\alpha\text{ being wavelet packets)} \cr &=\sum_{\text{inner }\alpha} c^0_{\alpha} \phi_{\alpha}(x) + \sum_{\text{edge }\alpha } c^0_{\alpha}\phi_{\alpha}(x)|_{[0,T]} }\] \[ \Rightarrow f^{\operatorname{diff}}|_{[T,\infty)}(x) = f|_{[T,\infty)} (x) - \sum_{\text{edge }\alpha} c^0_{\alpha} \phi_{\alpha}(x) |_{[T,\infty)} . \] This dif­fer­ence \( f^{\operatorname{diff}}(x) \) equals zero at \( T \), to­geth­er with all its de­riv­at­ives up to or­der \( n \), if \( \psi \in C^{n+\epsilon} \). There­fore, at edge \( T \), it can be de­com­posed per­fectly via the in­ter­val con­struc­tion that you and S. Jaf­fard in­tro­duced some years ago, us­ing only \( \phi_{j,k} \)’s with sup­port con­tained in the in­ter­val (or the half-line, since I’m only con­sid­er­ing one edge), and some sup­ple­ment­ary \( \psi_{j,k} \)’s (\( N-1 \) of them to be ex­act).

• At the oth­er edge, \( 2T \), I do the same thing as be­fore. (For sim­pli­city, let’s sup­pose that \( T > \Delta T \), so the tails of \( [0,T] \) don’t go bey­ond \( 2T \).) That is, I first look at \( [T,2T{+}\Delta T] \) to de­cide what tiling to choose in the time-fre­quency do­main, and I per­form the de­com­pos­i­tion suit­able to the edge \( 2T \), re­dis­trib­ut­ing the num­bers for the last \( N-1 \) taps of each \( m_1 \) over the cor­res­pond­ing \( m_0 \).

The whole amounts to a vari­ation on a con­struc­tion where one uses “too few” scale func­tions at left edges and “too many” scale func­tions at right edges; the res­ult­ing con­struc­tion, too, has as many scale func­tions as wave­lets at each res­ol­u­tion. Moreover, this con­struc­tion has the ad­vant­age that if noise is in­tro­duced near the edges, it won’t lead to dis­con­tinu­it­ies. So long as one uses only a fixed num­ber \( J \) of res­ol­u­tion levels, the func­tions used in the de­com­pos­i­tion al­ways form a Riesz basis. If I de­note the coef­fi­cients ob­tained by \( c_{n,\alpha} \), where \( n \) is for the block \( [nT, (n{+}1) T] \) and \( \alpha \) is the wave pack­et in­dex, I find \[ \|f\|^2 \leq 2 \sum_{n,\alpha}|c_{n,\alpha}|^2 \] (be­cause the \( \phi_{n,\alpha} \) are or­tho­gon­al for fixed \( n \), and the \( \phi_{n,\alpha} \) and \( \phi_{n+k,\beta} \) have dis­joint sup­ports if \( k\geq 2 \)).

What’s more, the ef­fect de­scribed above of “re­dis­trib­ut­ing” the coef­fi­cients at the edges leads to a bound of the type \[ \eqalign{ \sum_{\sigma} |c_{n,\alpha}|^2 \leq\ & C \,2^{J} \sum_{\alpha} |\langle f|_{[nT,(n+2)T]}, \phi_{n,\alpha} \rangle |^2\cr &\uparrow\cr &\text{depends on the}\cr &\text{choice of }m_0, m_1 } \] \[ \Rightarrow \sum_{n,\alpha} |c_{n,\alpha}|^2 \leq 2\, C\, 2^J \|f\|^2. \] If \( J \) is large, the con­di­tion­ing con­stant giv­en by those bounds is really small…

J. John­ston is very en­thu­si­ast­ic about this con­struc­tion be­cause he loves this idea of blocks that in­ter­pen­et­rate over a dis­tance pre­scribed by the res­ol­u­tion at each level. We shall see what that gives in prac­tice.

And that’s what I’ve been up to! (Apart from teach­ing, and writ­ing the art­icle with Al­bert and Pierre Vi­al about wave­lets on the in­ter­val.)

Hearty greet­ings to Thi­erry and Al­bert! Hugs and kisses,

In­grid

\[ \star\qquad\star\qquad\star \]

Cher Yves,

Tu me de­mandes ce que je fais, et ce que fait Car­oline…

Car­oline marche pr­esque: elle se tient de­bout, sans ap­pui, pendant 10 à 15 secondes, et quand elle a un ap­pui (nos mains, ou un meuble), elle fait des petits pas. Elle est tou­jours gaie et une vraie joie… sauf la nu­it, où elle se réveille en­core très souvent et de­mande sa ma­man.

Quant à sa ma­man, elle a re­gardé la drôle de schéma que je vais te décri­re ici.

Jim John­ston (qu’Al­bert connaît bi­en) nous avait dit depuis longtemps (un an) qu’il aim­erait bi­en un schéma où il pour­rait faire des paquets d’ondelettes, mais où il pour­rait changer le choix de la base à util­iser en cours de route. Quand nous avons ob­tenu les bases sur l’in­ter­valle avec nombre égal de fonc­tions échelle et ondelettes à chaque résolu­tion, nous lui avons an­noncé que nous avi­ons une réponse que faisait ex­acte­ment ce qu’il faisait: on pour­rait découper en mor­ceaux, et faire des paquets op­timaux sur chaque mor­ceau.

(Entre par­enthèses: quand j’avais ap­pris la con­struc­tion des bases “si­nus local­isés” — pour lesquelles, me dis­ent les ingénieurs, il faudrait citer non seule­ment Mal­var, mais aus­si Prinsen and Brad­ley, cités dans l’art­icle de Mal­var, et qui avaient déjà eu une partie des idées — je l’ai aus­sitôt in­diquée à John­son comme une solu­tion. Mais il aime mieux les paquets d’ondelettes, parce qu’ils per­mettent d’avoir des résolu­tions différents en même temps. C.à.d., si tu as un sig­nal de basse fréquence de \( t_0 \) à \( t_1 \), mais aus­si des petits chouïas de haute fréq. de \( t_2 \) à \( t_3 \), et de \( t_4 \) à \( t_5 \), où \( t_0 < t_2 < t_3 < t_4 < t_5 < t_1 \), al­ors tu peux, avec les ondelettes, ut­liliser toute la fenêtre \( t_0 \rightarrow t_1 \) pour la basse fréq., et en même temps de petites fenêtres pour les hautes fréq. Avec un schéma à la Mal­var, tu découper­ais en mor­ceaux, même pour les basses fréq. Ap­par­em­ment, c’est un réel problème pour les mor­ceaux de mu­sique avec plusieurs in­stru­ments, me dit John­ston (qui a es­sayé d’im­plémenter Prinsen et Brad­ley.)

Mail il n’ai­mait pas cette réponse! Mal­gré le fait que nous cou­pi­ons de façon à ne pas déranger la reg­u­lar­ité! En util­is­ant un ar­gu­ment d’Al­bert, je lui ex­pli­quais que c’était comme si on pro­longeait la fonc­tion de manière douce et qu’on décom­po­sa­it al­ors cette ex­ten­sion. La rais­on pour laquelle il n’en voulait pas est la suivante: sup­po­sons qu’on re­con­stru­ise apès ar­rondi, ou quan­ti­fic­a­tion, ou un autre procédé qui a su­per­posé un bruit aux coef­fi­cients. Al­ors, par le fait même que les ondelettes sur l’in­ter­valle ont un bord ab­rupt à la fin de l’in­ter­valle, la re­con­struc­tion, après er­reurs, aura des dis­con­tinu­ités…Pire: des er­reurs sur des coef­fi­cients cor­res­pond­ant à de très basses fréquences peuvent men­er à ces dis­con­tinu­ités, c.à.d. des er­reurs de haute fréquence. Trrrrès mauvais, d’après J.J.

Al­ors j’ai pensé au schéma hy­bride suivant:

• Sup­po­sons qu’on veuille des blocs de taille \( T \), avec une base différente de paquets d’ondelettes sur chaque block.

• Com­mençons par décom­poser, en fais­ant tous les fil­trages pos­sibles, toutes les données entre 0 et \( T+\Delta T \), où \( \Delta T \) est choisi de façon telle que, même à la résolu­tion la plus grossière, aucune fonc­tion n’a un sup­port plus grand que \( \Delta T \).

(Je sup­pose qu’on a a pri­ori décidé de ne pas al­ler au-delà d’un nombre fixe de fil­trages suc­ces­sifs). Peu im­porte ce qu’on fait au bord \( T+\Delta T \). (En pratique, je crois que le mieux est d’util­iser tes ondelettes sur l’in­ter­valle pour ce bord-ci, pro­vis­oire.)

• Décidons al­ors quelle est, parmi toutes les bases pos­sibles, la base op­ti­male. (C.à.d., on décide du pav­age op­tim­al, pour ce bout de sig­nal. Comme on util­ise \( 0 \rightarrow T + \Delta T \) pour cette décision, al­ors qu’on va se re­streindre à \( 0\rightarrow T \) plus loin, la décision pour­rait bi­en ne pas être tout à fait op­ti­male, mais je ne sais pas com­ment y remédi­er.)

• Cette décision prise, re­tournons en arrière. Le but est de n’util­iser, pour ce mor­ceau \( 0\rightarrow T \), que des fonc­tions dont le sup­port a une in­ter­sec­tion non triviale avec \( [0,T] \). En fait, la réponse est donnée par ta con­struc­tion, mais je vais choisir de ne pas or­thonor­m­al­iser au bout (pour des rais­ons que j’ex­plique plus loin). Je veux que la su­per­pos­i­tion chois­ie re­produise ex­acte­ment le sig­nal sur \( [0,T] \), et je n’util­iserai que des paquets d’ondelettes non modi­fiés au bout. Cer­tains d’entre eux auront une queue que dépasse \( T \) — et ces queues seront très im­port­antes mais je ne veux les dis­tinguer que par la partie con­tenue dans \( [0,T] \). Ceci veut dire que je dev­rai éliminer cer­tains paquets: chaque fois que j’util­ise un “split­ting” avec \( m_0 \) et \( m_1 \), les fil­tres tout au bout util­is­ant \( m_1 \) ne donnent que des com­binais­ons linéaires de ce que les \( m_0 \) au bout donnent. (C’est ton ob­ser­va­tion que les \( \psi_{j,k}|_{[0,T]} \) qui ont moins de la moitié de leur sup­port à l’intérieur de \( [0,1] \) sont en fait des com­binais­ons linéaires des \( \phi_{j,k}|_{[0,1]} \).) Con­crètement: \[ \eqalign{ \psi& (x) = \sum^{N-2}_{n=0} a_n \phi(x-n) &+ &Q(x)\cr &\uparrow &&\downarrow\cr &\text{ support }&&\text{queue} \cr &[0, 2N-1] &&\text{qui a support }\cr &&&[N-1,2N-1]\cr } \] où \[ \eqalign{ a_0 &= \frac{h_{2N-1}}{h_0},\cr a_n &= \frac{h_{2N-1-2n} - h_{2n} a_{n-1}}{h_0}. } \] Une for­mule tout à fait ana­logue tient pour \( m_1 (\xi), m_0(\xi) \). Al­ors à chaque fois que je fais un “split­ting” au bout \( T \), je re­porte les \( N-1 \) coeff. du bout de la bande \( m_1 \) dans la bande \( m_0 \) (util­is­ant la for­mule ci-des­sus), et je laisse tomber les \( N-1 \) taps cor­res­pond­ants dans la bande \( m_1 \).

Le résul­tat est bi­en une re­présen­t­a­tion de \( f \) par des paquets d’ondelettes, qui re­produit \( f \) ex­acte­ment dans \( [0,T] \) et où tous les paquets du bord ont des queues de la taille cor­res­pond­ant à leur résolu­tion, dépassant \( T \).

(Ces queues ont la rais­on pour laquelle je n’ai pas util­isé ton schéma dir­ecte­ment: si j’util­ise les coeffs. résul­t­ant d’une or­thonor­m­al­isa­tion, j’ar­rive à écri­re une jolie queue pour \( \psi \), mais pour des paquets d’ondelettes in­cor­por­ant plusieurs \( m_1 \), mes queues devi­ennent de plus en plus cour­tes, ce qui n’est pas l’ef­fet désiré. En plus, ce schéma-ci est plus simple pour la suite).

• Procédons main­ten­ant au bloc suivant. Je com­mence par faire la différence entre \( f|_{[T, \infty]} \) et les “queues” du bloc précédent. C.à.d. \[ \eqalign{ f|_{[0,T]}(x) &= \sum_{\alpha}c^0_{\alpha} \phi_{\alpha} (x)|_{[0,T]}\quad\phi_\alpha\text{ paquets d’odelettes} \cr &=\sum_{\alpha\text{ intérieures}} c^0_{\alpha} \phi_{\alpha}(x) + \sum_{\alpha \text{ bord}} c^0_{\alpha}\phi_{\alpha}(x)|_{[0,T]} }\] \[ \Rightarrow f^{\operatorname{diff}}|_{[T,\infty)}(x) = f|_{[T,\infty)} (x) - \sum_{\alpha\text{ bord}} c^0_{\alpha} \phi_{\alpha}(x) |_{[T,\infty)}. \] Cette différence \( f^{\operatorname{diff}}(x) \) est égale à zéro en \( T \), ain­si que toutes des dérivées jusqu’à l’or­dre \( n \), si \( \psi \in C^{n+\epsilon} \).

Au bord \( T \), elle peut donc être décom­posée à mer­veille avec le schéma sur l’in­ter­valle que S. Jaf­fard et toi avaient con­stru­it il y a quelques années, n’util­is­ant que les \( \phi_{j,k} \) avec sup­ports con­tenus dans l’in­ter­valle (ou la demi-droite, puisque je ne re­garde qu’un seul bord), et quelques \( \psi_{j,k} \) sup­plémen­taires (ex­acte­ment \( N-1 \)).

• A l’autre bout, \( 2T \), je fais la même chose qu’av­ant. (Pour plus de sim­pli­cité, sup­po­sons \( T > \Delta T \), de façon à ce que les queues de \( [0,T] \) ne dépas­sent pas \( 2T \).) C.à.d. je re­garde d’abord \( [T,2T+\Delta T] \) pour décider quel dallage choisir en temps-fréquence, et je fais la décom­pos­i­tion ad­aptée au bord \( 2T \), en re­dis­tribuant les nombres pour les derniers \( N-1 \) taps de chaque \( m_1 \) sur le \( m_0 \) cor­res­pond­ant.

Le tout cor­res­pond à une vari­ation sur un schéma où on util­iserait “trop peu” de fonc­tions échelle aux bords gauches et “trop” de fonc­tions échelle aux bords droits; le résul­tat est aus­si un schéma avec autant de fonc­tions échelle que d’ondelettes à chaque résolu­tion; en plus, ce schéma a l’av­ant­age que si on in­jecte du bruit près des bords, il ne don­nera pas lieu à des dis­con­tinu­ités. Aus­si longtemps qu’on n’util­ise qu’un nombre fixe \( J \) de niveaux de résolu­tion, les fonc­tions util­isées dans la décom­pos­i­tion con­stitu­ent tou­jours une base de Riesz. Si je dénote les coeffs ob­tenus par \( c_{n,\alpha} \), \( \,n \) pour le bloc \( [nT, (n+1) T] \),  \( \alpha \) pour l’in­dice du paquet d’onde, al­ors je trouve \[ \|f\|^2 \leq 2 \sum_{n,\alpha}|c_{n,\alpha}|^2 \] (parce que les \( \phi_{n,\alpha} \) sont or­tho­gonaux pour \( n \) fixe, et les \( \phi_{n,\alpha} \) et \( \phi_{n+k,\beta} \) ont des sup­ports dis­joints si \( k\geq 2 \)).

D’autre part, l’ef­fet de “re­dis­tri­bu­tion” des coeffs aux bords, décrit plus haut, mène à une borne du type \[ \eqalign{ \sum_{\sigma} |c_{n,\alpha}|^2 \leq\ & C 2^{J} \sum_{\alpha} |\langle f|_{[nT,(n+2)T]}, \phi_{n,\alpha} \rangle |^2\cr &\uparrow\cr &\text{dépendant}\cr &\text{des }m_0, m_1 \text{ choisis} } \] \[ \Rightarrow \sum_{n,\alpha} |c_{n,\alpha}|^2 \leq 2\, C\, 2^J \|f\|^2. \] Si \( J \) est grand, la con­stante de con­di­tion­nement donnée par ces bornes est fort petite…

J. John­ston est très en­th­ousi­aste pour ce schéma parce qu’il aime bi­en cette idée d’in­terpénétra­tion des blocs sur une dis­tance dictée par la résolu­tion de chaque niveau. Nous al­lons voir main­ten­ant ce que cela donne en pratique.

Et voilà ce que je fais! (A part en­sei­gn­er, et rédi­ger l’art­icle avec Al­bert et Pierre Vi­al, sur les ondelettes sur l’in­ter­valle).

Un grand bon­jour à Thi­erry et Al­bert! Je t’em­brasse,

In­grid