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\to 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+\mathrm{\Delta }T$, where $\mathrm{\Delta }T$ is chosen so that, even at the coarsest res­ol­u­tion, no func­tion has sup­port great­er than $\mathrm{\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+\mathrm{\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\to T+\mathrm{\Delta }T$ for that de­cision, where­as later on we will re­strict to $0\to 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\to 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: $$\begin{array}{rlll}\psi & (x)=\sum _{n=0}^{N-2}{a}_n\phi (x-n)& +& Q(x)\\ & \uparrow & & \downarrow \\ & \text{ support }& & \text{tail,}\\ & [0,2N-1]& & \text{having support }\\ & & & [N-1,2N-1]\end{array}$$ where $$\begin{array}{rl}{a}_0& =\frac{h_{2N-1}}{h_0},\\ a_n& =\frac{h_{2N-1-2n}-h_{2n}{a}_{n-1}}{h_0}.\end{array}$$ 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,\mathrm{\infty }]}$ and the “tails” of the pre­vi­ous block. That is, $$\begin{array}{rl}f{|}_{[0,T]}(x)& =\sum _{\alpha }{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[0,T]}({\phi }_{\alpha }\text{ being wavelet packets)}\\ & =\sum _{\text{inner }\alpha }{c}_{\alpha }^0{\phi }_{\alpha }(x)+\sum _{\text{edge }\alpha }{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[0,T]}\end{array}$$ $$\Rightarrow f^{\mathrm{diff}}{|}_{[T,\mathrm{\infty })}(x)=f{|}_{[T,\mathrm{\infty })}(x)-\sum _{\text{edge }\alpha }{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[T,\mathrm{\infty })}.$$ This dif­fer­ence $f^{\mathrm{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>\mathrm{\Delta }T$, so the tails of $[0,T]$ don’t go bey­ond $2T$.) That is, I first look at $[T,2T+\mathrm{\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 $$\parallel f{\parallel }^2\le 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\ge 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 $$\begin{array}{rl}\sum _{\sigma }|c_{n,\alpha }{|}^2\le & C{2}^J\sum _{\alpha }|⟨f{|}_{[nT,(n+2)T]},{\phi }_{n,\alpha }⟩{|}^2\\ & \uparrow \\ & \text{depends on the}\\ & \text{choice of }{m}_0,m_1\end{array}$$ $$\Rightarrow \sum _{n,\alpha }|c_{n,\alpha }{|}^2\le 2C{2}^J\parallel f{\parallel }^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 \star \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\to 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+\mathrm{\Delta }T$, où $\mathrm{\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 $\mathrm{\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+\mathrm{\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\to T+\mathrm{\Delta }T$ pour cette décision, al­ors qu’on va se re­streindre à $0\to 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\to 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: $$\begin{array}{rlll}\psi & (x)=\sum _{n=0}^{N-2}{a}_n\phi (x-n)& +& Q(x)\\ & \uparrow & & \downarrow \\ & \text{ support }& & \text{queue}\\ & [0,2N-1]& & \text{qui a support }\\ & & & [N-1,2N-1]\end{array}$$ où $$\begin{array}{rl}{a}_0& =\frac{h_{2N-1}}{h_0},\\ a_n& =\frac{h_{2N-1-2n}-h_{2n}{a}_{n-1}}{h_0}.\end{array}$$ 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,\mathrm{\infty }]}$ et les “queues” du bloc précédent. C.à.d. $$\begin{array}{rl}f{|}_{[0,T]}(x)& =\sum _{\alpha }{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[0,T]}{\phi }_{\alpha }\text{ paquets d’odelettes}\\ & =\sum _{\alpha \text{ intérieures}}{c}_{\alpha }^0{\phi }_{\alpha }(x)+\sum _{\alpha \text{ bord}}{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[0,T]}\end{array}$$ $$\Rightarrow f^{\mathrm{diff}}{|}_{[T,\mathrm{\infty })}(x)=f{|}_{[T,\mathrm{\infty })}(x)-\sum _{\alpha \text{ bord}}{c}_{\alpha }^0{\phi }_{\alpha }(x){|}_{[T,\mathrm{\infty })}.$$ Cette différence $f^{\mathrm{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>\mathrm{\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+\mathrm{\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 $$\parallel f{\parallel }^2\le 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\ge 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 $$\begin{array}{rl}\sum _{\sigma }|c_{n,\alpha }{|}^2\le & C{2}^J\sum _{\alpha }|⟨f{|}_{[nT,(n+2)T]},{\phi }_{n,\alpha }⟩{|}^2\\ & \uparrow \\ & \text{dépendant}\\ & \text{des }{m}_0,m_1\text{ choisis}\end{array}$$ $$\Rightarrow \sum _{n,\alpha }|c_{n,\alpha }{|}^2\le 2C{2}^J\parallel f{\parallel }^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