Celebratio Mathematica

Dear Yves,

I’d just been typ­ing a long email to you for over an hour when Nets­cape gave up the ghost and the whole mes­sage was lost. You might say there’s some di­vine justice there — that this is my pun­ish­ment for not hav­ing replied to you soon­er. So here I am writ­ing by hand (at least you’ll have the ac­cents which I still haven’t figured out how to make on this key­board that lacks them), and I’m en­clos­ing pho­to­co­phies of the art­icles I’m dis­cuss­ing.

Again, sorry I didn’t reply soon­er to your emails. You’re right; it’s a chore that’s be­ing asked of you, and I should have worked to light­en your task right away. But I had no way to know: I wasn’t aware that Björn [En­gquist] had put you on the list of names sug­ges­ted to the Dean. (But that’s not really a good ex­cuse: Björn had asked me for 5 or 6 names, and I gave him 2 right away, say­ing that I’d email the oth­ers — but then I for­got.) I’ve also wondered why you might be un­able to view a Lu­cent web page: maybe it’s be­cause view­ing from out­side the US is blocked? In any case, here is the web ad­dress that works for me:

ht­tp://wim.sweldens.com

\begin{array}{c}\hline\qquad\qquad\qquad\end{array} (Con­tinu­ation 2 days later, after my phone call of March 27.) I will fax this let­ter to you, as agreed, and I’ll also send it in hard copy, to­geth­er with the art­icles that I dis­cuss in the let­ter.

The Dean, and through him, the Com­mit­tee on Ap­point­ments and Ten­ure, don’t ex­pect from you an in-depth ana­lys­is of all as­pects of his work. In fact they have chosen (or En­gquist and Dob­kin have chosen for them) ex­perts in the vari­ous fields. So if you wish you can say from the get-go that you will be dis­cuss­ing only cer­tain as­pects of his sci­entif­ic out­put, leav­ing the rest to oth­er ex­perts.

From the view­point of Ap­plied Math at Prin­ceton, we have been search­ing for years for someone who would in­terest both the Dept. of Com­puter Sci­ence and us, but there clearly has been a mis­match. The people I put forth when I was the dir­ect­or, such as Rokh­lin, En­gquist, Bill Cook and even Ad­el­man, from MIT, did not in­terest them at all, or only mildly; they were warm­er on Greengard (who however did not want to leave NYU), but their coun­ter­pro­pos­als were mainly people who we re­garded as much less strong, such as Eric Gross [sic], or who were work­ing in less in­ter­est­ing areas (like Dem­mel — heavy-duty lin­ear al­gebra soft­ware). Re­gard­ing Wim Sweldens, on the oth­er hand, there is in­terest on both sides: the com­puter graph­i­cists are very im­pressed by his SIG­GRAPH track re­cord, that be­ing a con­fer­ence that has as many par­ti­cipants (about 4,000) and as much prestige in com­puter graph­ics as the ICM in math­em­at­ics. In gen­er­al, a talk at ICM is eas­ily enough, without fur­ther ado, to se­cure a ten­ured po­s­i­tion in a top de­part­ment in this field. At the same time, there is also in­terest in him among our group, not only on my part (or I would nev­er have pro­posed him), but also on the part of Björn En­gquist and Wein­an E, who have had very pro­duct­ive con­ver­sa­tions with him.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

What I find most in­ter­est­ing in Wim, and what is for me the main reas­on why he’s at­tract­ive as a bridge between ap­plied math and com­puter sci­ences, is that he has a very good grasp of math­em­at­ic­al in­tu­ition, and is in­ter­ested not only in get­ting soft­ware and pro­grams to work well, but also in study­ing the math­em­at­ic­al reas­ons for their suc­cess (like me, he be­lieves that good soft­ware re­quires not only good “cook­ing skills” — though that plays a role too — , but also, and primar­ily, es­sen­tially math­em­at­ic­al ideas. For ex­ample: in­teg­ra­tion by Le­besgue’s meth­od yields an al­gorithm that is far bet­ter than Riemann’s.) There­fore he’s al­ways in­ter­ested in ex­plor­ing the math­em­at­ic­al as­pects of cer­tain de­vel­op­ments, even if that re­quires (on a first ap­proach) a drastic sim­pli­fic­a­tion in the de­scrip­tion, bey­ond what oth­er com­puter sci­ent­ists would con­sider reas­on­able. And in our col­lab­or­a­tion, he of­ten has his share of key ideas, even though more of­ten than not the tech­nic­al com­pon­ent falls to me.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

I’m en­clos­ing here his list of pub­lic­a­tions. I’ve marked a few which I will de­scribe be­low. I will in­clude cop­ies of them in the pack­et that I’ll send you. These art­icles il­lus­trate three “themes” in my “Sweldens file” for your be­ne­fit, all with­in the frame­work of the in­ter­ac­tion “ap­plied math \( \leftrightarrow \) al­gorithms”.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

“Lift­ing” is Sweldens’ name for a con­struc­tion that al­lows the con­struc­tion of longer wave­let fil­ters start­ing from short­er ones. It its most prim­it­ive form, it amounts to a simple al­geb­ra­ic ob­ser­va­tion: \begin{equation}\label{eqon} \eqalign{ \text{if }\quad & m_0 (\xi)\quad \text{ and } \quad \tilde{m}_0(\xi) \text{ satisfy }\cr & m_0 (\xi) \, \overline{\tilde{m}_0 (\xi)} + m_0(\xi + \pi)\, \overline{\tilde{m}_0 (\xi+\pi)} =1, \tag{*} } \end{equation} and if we define \[ m^{\#}_0 (\xi)=\tilde{m}_0(\xi) + e^{-i\xi} \alpha (2\xi)\, \overline{m_0\,(\xi+\pi)}, \] where \( \alpha \) is any tri­go­no­met­ric poly­no­mi­al, then the pair \( m_0,m^\#_0 \) also sat­is­fies \eqref{eqon}. Sev­er­al people have made this ob­ser­va­tion in­de­pend­ently: Sweldens, Dah­men & Mic­chelli, Her­ley & Vet­terli —  and all in all, it’s a fairly trivi­al one. They all ob­served as well that biortho­gon­al wave­let splines can be gen­er­ated from the trivi­al pair \( m_0 = \frac{1}{\sqrt{2}} \), \( \tilde{m}_0 = \frac{1}{\sqrt{2}} \) in two steps: \( m,\tilde{m}_0 \rightarrow m_0, m^{\#}_0\rightarrow m^b_0, m^{\#}_0 \) (dual op­er­a­tion). The dif­fer­ence between Sweldens’ work and the oth­ers’ is the in­ter­pret­a­tion he gave (in terms of pre­dic­tion and up­dat­ing — see art­icle A), which then al­lows sev­er­al very use­ful gen­er­al­iz­a­tions and ap­plic­a­tions:

• “in-place” al­gorithm: for in­stance, in Haar:
stand­ard alg.: \[ \eqalign{ c^0_k \longrightarrow s^1_k &= \frac{c^0_{2k} + c^0_{2k+1}}{2}\cr d^1_k &= c^0_{2k+1} - c^0_{2k}}\quad \text{(non-normalized).} \] One must store the \( c^0_{2k} \), \( c^0_{2k+1} \) in memory after cal­cu­lat­ing the \( s^1_k \), in or­der to cal­cu­late the \( d^1_k \).

lift­ing alg.:

For each cal­cu­la­tion: one quant­ity is re­placed by an­oth­er (\( c^0_{2k+1} \) by \( d^1_k \), later \( s^1_k \) by \( c^0_{2k} \)).

This al­lows one to make much big­ger cal­cu­la­tions and in situ­ations where the “pre­dic­tion” and the “up­date” are not uni­form, as in the

• ap­plic­a­tion to nonuni­form sur­faces and tri­an­gu­la­tions (see art­icle A: second-gen­er­a­tion wave­lets)

• in the set­ting of the 2 tri­an­gu­lar op­er­a­tions

One can very well use non­lin­ear op­er­a­tions (util­ized in B) or ad­apt­at­ive ones (as in C).

• fi­nally, by in­tro­du­cing more than 2 steps if ne­ces­sary, one can factor in­to tri­an­gu­lar steps all wave­let fil­ters of that sort (see D) — that’s the im­ple­ment­a­tion that was in­teg­rated in­to JPEG2000 be­cause it is so easy.

This set­ting is an ex­ample where Sweldens (and I) have looked first at a math­em­at­ic­al prob­lem to see if its solu­tion would sug­gest an al­gorithm. With my stu­dent Ig­or Guskov, who joined us early on in this ef­fort, we made a de­tailed study (pa­pers E and F) in di­men­sion 1, which then sug­ges­ted to Ig­or the 2d (sur­face) con­struc­tion in his thes­is, and also the ap­plic­a­tions spelled out in pa­per G (joint with Schröder).

Here we pro­ceeded in the op­pos­ite dir­ec­tion. A beau­ti­ful idea was first im­ple­men­ted (with spec­tac­u­lar res­ults) — see art­icle H, and then it piqued my math­em­at­ic­al curi­os­ity — see art­icle I (a pre­print, not yet on Sweldens’ web page). We are hop­ing that a more con­cer­ted math­em­at­ic­al ef­fort will lead us to oth­er 2d al­gorithms.

However, this in­ter­min­able let­ter must come to an end if it’s to be of any use to you, so I’ll fin­ish now, two days and two pens later, with

hugs and kisses,

In­grid

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

Cher Yves,

Al­ors que j’étais en train depuis plus d’une heure à taper un long e-mail pour toi, mon Nets­cape a rendu l’âme et tout le mes­sage est perdu. Tu me dir­as qu’il y a une justice di­vine — que c’est ma pun­i­tion pour ne pas t’avoir répondu plus tôt. Du coup je rédige ceci à la main (au moins tu aur­as les ac­cents que je n’ai tou­jours pas maîtrisés sur mon clavi­er qui ne les a pas), et j’in­clus des pho­to­cop­ies des art­icles dont je parle.

Je m’ex­cuse en­core de ne pas avoir répondu plus tôt à tes e-mails. Tu as rais­on: c’est une corvée que l’on te de­mande, et j’avais dû tout de suite te rendre la tâche la plus fa­cile pos­sible. Je n’avais pas pu l’an­ti­ciper: je ne savais pas que Björn t’avait mis sur la liste des noms suggérés au Dean. (Mais ce n’est pas vraiment une bonne ex­cuse: Björn m’avait de­mandé 5 ou 6 noms, et je lui en avais donné 2 tout de suite, en lui dis­ant que j’émail­erais les autres\ldots et puis j’ai oublié.) Je me suis de­mandée aus­si pour­quoi tu pour­rais avoir des problèmes pour re­garder une page à Lu­cent: il se peut que ce soit parce qu’il y aurait un bloc­age pour des pays autres que les E-U. En tous cas, voici l’ad­dresse sur le réseau qui marche pour moi:

ht­tp://wim.sweldens.com

\begin{array}{c}\hline\qquad\qquad\qquad\end{array} (Je con­tin­ue 2 jours plus tard, après mon coup de fil le 27 mars.) Je te fax­erai cettre lettre, comme convenu, et je te l’en­ver­rai aus­si “en dur”, ac­com­pagnée des art­icles dont je parle dans la lettre.

Le Dean, et à tra­vers lui, le Com­mit­tee on Ap­point­ments and Ten­ure, ne s’at­tendent pas à une dis­cus­sion ap­pro­fon­die de ta part de tous les as­pects de son trav­ail. En fait, ils ont choisi des ex­perts (ou En­gquist et Dob­kin ont choisi pour eux) dans les différents do­maines. Tu peux donc très bi­en dire dès le départ que tu n’ad­dressera que cer­taines fa­cettes de sa pro­duc­tion sci­en­ti­fique, lais­sant les autres à d’autres ex­perts.

Du point de vue des Math. App. à Prin­ceton, nous sommes depuis plusieurs années à la recher­che de quelqu’un qui intéresserait con­jointe­ment le Dépt de Com­puter Sci­ences et nous, mais il y avait claire­ment un mis-match. Les per­sonnes que j’avais pro­posées quand j’étais dir­ec­teur, comme Rokh­lin, En­gquist, Bill Cook et même Ad­el­man, de MIT, ne les intéres­saient pas du tout ou seule­ment modérément; ils étaient plus chauds pour Greengard (qui lui ne voulait pas quit­ter NYU), mais ils contre-pro­po­sa­ient sur­tout des gens que nous considéri­ons comme beau­c­oup moins forts, comme Eric Gross [sic], ou dans des branches moins intéress­antes (comme Dem­mel — gros pro­grammes d’algèbre linéaire). Pour Wim Sweldens par contre, il y a de l’interêt des deux côtés: les “graph­i­cistes” en in­form­atique sont très im­pres­sionnés par son pal­marès à SIG­GRAPH, une conférence qui à autant de par­ti­cipants (4,000 en­viron) et autant de prestige en graph­ics que ICM pour les mathématiciens. En général, un ex­posé à ICM suf­fit large­ment, et sans aucune dis­cus­sion, pour ob­tenir la ten­ure dans un “top de­part­ment” dans ce do­maine. D’autre part, il y a aus­si de l’intérêt dans notre groupe, pas seule­ment de ma part (sinon je ne l’aurais ja­mais pro­posé), mais aus­si de la part de Björn En­gquist et Wein­an E, qui ont eu des dis­cus­sions très pro­duct­ives avec lui.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

Ce que je trouve le plus intéress­ant dans Wim, et ce qui con­stitue pour moi la rais­on prin­cip­ale pour son at­trait comme un pont entre les math. app. et l’in­form­atique, est qu’il com­prend très bi­en l’in­tu­ition mathématique, et qu’il est intéressé non seule­ment par des codes ou pro­grammes que marchent bi­en, mais aus­si par une étude des rais­ons mathématiques pour leur succès (comme moi, il est per­suadé qu’un bon code ne re­quiert pas seule­ment de la “cuisine” — bi­en qu’elle joue un rôle aus­si — mais aus­si, et prin­cip­ale­ment, des idées es­sen­ti­elle­ment mathématiques. Par ex­emple: intégrer selon la méthode de Le­besgue donne un al­gorithme de loin supérieur à l’al­gorithme de Riemann.) Par conséquent, il est tou­jours intéressé d’ex­plorer l’as­pect mathématique de cer­tains déve­lop­pe­ments, même s’il faut par­fois, sim­pli­fi­er drastique­ment (dans un premi­er à bord) la de­scrip­tion, au-delà de ce que d’autres in­form­aticiens trouveraient rais­on­nable. Et dans mes col­lab­or­a­tions, il a souvent sa part des idées cru­ciales, même si le côté tech­nique mathématique re­tombe plus souvent sur moi.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

J’at­tache ici la liste de ses pub­lic­a­tions. J’en ai mar­qué quelques-unes que je veux décri­re ci-des­sous. J’in­clu­erai leurs cop­ies dans le paquet que je t’en­ver­rai. Ces art­icles il­lustrent trois “thèmes” dans mon “dossier Sweldens” pour toi, tous dans le cadre in­ter­ac­tion math app \( \leftrightarrow \) al­gorithmes.

\begin{array}{c}\hline\qquad\qquad\qquad\end{array}

“Lift­ing” est le nom donné par Sweldens à une con­struc­tion qui per­met de dériver des fil­tres d’ondelettes plus longs à partir d’autres, plus courts. Dans son st­ade le plus prim­itif, il s’agit d’une simple ob­ser­va­tion algébrique: \begin{equation}\label{eqtw} \eqalign{ \text{si }\quad & m_0 (\xi)\quad \text{ et } \quad \tilde{m}_0(\xi) \text{ satisfont }\cr & m_0 (\xi) \, \overline{\tilde{m}_0 (\xi)} + m_0(\xi + \pi)\, \overline{\tilde{m}_0 (\xi+\pi)} =1, \tag{*} } \end{equation} et on défi­nit \[ m^{\#}_0 (\xi)=\tilde{m}_0(\xi) + e^{-i\xi} \alpha (2\xi)\, \overline{m_0\,(\xi+\pi)}, \] où \( \alpha \) est un polynôme tri­go­nométrique ar­bit­raire, al­ors la paire \( m_0 \) et \( m^\#_0 \) sat­is­font \eqref{eqtw} égale­ment. Cette ob­ser­va­tion a été faite pour plusieurs per­sonnes indépen­dem­ment: Sweldens, Dah­men & Mic­chelli, Her­ley & Vet­terli — et somme toute, c’est une ob­ser­va­tion as­sez triviale. Ils ont tous aus­si ob­servé que les ondelettes splines biortho­gonales peuvent être générées à partir de la paire triviale \( m_0 = \frac{1}{\sqrt{2}} \), \( \tilde{m}_0 = \frac{1}{\sqrt{2}} \) en 2 étapes: \( m,\tilde{m}_0 \rightarrow m_0, m^{\#}_0\rightarrow m^b_0, m^{\#}_0 \) (opéra­tion duale). La différence entre le trav­ail de Sweldens et les autres est l’in­ter­préta­tion qu’il a donnée (en ter­mes de prédic­tion et up­date — voir art­icle A) qui al­ors per­mettait plusieurs général­isa­tions et ap­plic­a­tions très utiles:

• al­gorithme “in-place”: par ex. dans Haar:

alg. stand­ard: \[ \eqalign{ c^0_k \longrightarrow s^1_k &= \frac{c^0_{2k} + c^0_{2k+1}}{2}\cr d^1_k &= c^0_{2k+1} - c^0_{2k}}\quad \text{(non normalisés).} \] Il faut garder les \( c^0_{2k} \), \( c^0_{2k+1} \) en mémoire après le cal­cul de \( s^1_k \), pour pouvoir cal­culer \( d^1_k \). \small­break alg. lift­ing:

À chaque cacul: une quant­ité est re­m­placée par une autre (\( c^0_{2k+1} \) par \( d^1_k \), plus tard \( s^1_k \) par \( c^0_{2k} \)).

Ceci per­met de faire des cal­culs beau­c­oup plus gros et dans des cadres où la “prédic­tion” et le “up­date” ne sont pas uni­formes, commes dans l’[sic]

• ap­plic­a­tion à des sur­faces et tri­an­gu­la­tions non-uni­formes (voir art­icle A: second-gen­er­a­tion wave­lets)

• dans le cadre des 2 opéra­tions tri­an­gu­laires

• fi­nale­ment, en in­troduis­ant plus de 2 étapes si néces­saire, on peut fac­tor­iser en étapes tri­an­gu­laires tous les fil­tres ondelettes de la sorte (voir D) — c’est cette im­plémen­ta­tion-là qui a été intégrée à JPEG2000 parce que elle est tell­e­ment fa­cile.

Ce cadre-ci est un ex­emple où Sweldens (et moi) avons re­gardé d’abord un problème mathématique pour voir si sa solu­tion suggérerait un al­gorithme. En 1d, nous avons fait, avec Ig­or Guskov, mon étu­di­ant, qui nous a joints très vite dans cet ef­fort, une étude détaillée (papi­ers E et F) qui a al­ors suggéré à Ig­or la con­struc­tion en 2d (sur­face) dans sa thèse, et des ap­plic­a­tions détaillées dans papi­er G (joint avec Schröder).

Ici, le chemine­ment in­verse a été fait. Une idée très belle a d’abord été im­plémentée (avec des résul­tats spec­tac­u­laires) — voir art­icle H, et a en­suite ex­cité ma curi­os­ité mathématique — voir art­icle I (un pre­print, pas en­core sur la page web de Sweldens). Nous espérons que des travaux math. plus poussés nous amèner­ont à d’autres al­gorithmes en 2d.

Cette lettre in­ter­min­able doit cepend­ant se ter­miner si je veux qu’elle te soit de quelque utilité, donc je ter­mine, 2 jours et 2 bics plus tard, avec

des grosses bises,

In­grid