Wave of the future – discovery of mathematical ‘wavelets’ by Ingrid Daubechies
Hans Christian Von Baeyer
“I WAS IN MONTREAL AT THE TIME, TO GIVE A LECTURE, AND IT WAS MISERABLY COLD. I tried to see the city, but I could stand being outdoors for only a few minutes before I had to dash back inside again to warm up with a hot drink. So I was kind of forced to stay in my hotel room–and calculate.” Ingrid Daubechies was recalling her momentous discovery, in February 1987, of a particular type of mathematical construct called wavelets, which subsequently sent ripples of excitement through the arcane community of applied mathematicians. “It was a period of incredibly intense concentration. I was engaged to be married, and at the same time totally wrapped up in my ideas, even when I was sightseeing, or washing my hair, or cooking. But then everything sort of fell into place pretty quickly. By the end of March it was all finished. I felt drained and elated. And then we got married.”
Picturing her struggling through the snowdrifts of Montreal, clutching her freezing ears while images of wavelets careered through her brain, was a bit difficult when she told me about it last June, with the mercury hovering around 90. We were sitting over iced tea in her native city of Brussels, at a table resplendent with roses, strawberries, and sliced watermelon, while through the open French windows we could hear her two toddlers tumbling about on the lawn. But the excitement of her intellectual adventure sparkled in her blue eyes, and her discourse became increasingly urgent as she searched for ways to cast her mathematical thought processes into ordinary words.
The subject on which Daubechies (pronounced DOHB-shee) quickly became one of the world’s leading authorities is signal processing–a branch of applied mathematics that is concerned with analyzing, transmitting, manipulating, storing, and reconstructing signals. A signal is simply a wiggly line, like a graph of the daily temperature throughout the year or a tracing of the trembling electrical output of a human brain. The multitude of applications of signal processing to physics, astronomy, computer science, engineering, and medicine is boundless. Daubechies visibly delights in the interdisciplinary nature of her work: she loves to talk to people in other fields and to help them adapt her insights and results to their own particular problems.
Signal processing isn’t something that only scientists do. We all do it, all the time, without thinking. Consider the unmatched ability of our eyes and brains to lift hidden images out of seemingly meaningless backgrounds. In the internationally best-selling book Magic Eye and its sequels, random-looking jumbles of colored dots and streaks–jumbles that look like pointillist abstract paintings but that are in fact patterns produced by powerful computer programs–turn out to be hypnotic picture puzzles. With sufficient relaxation of the eye muscles and a little patience, the viewer soon discovers three-dimensional images of weird creatures like winged lions displayed as if on a stage behind the page. The wondrous moment when the image begins to coalesce out of the chaotic foreground justifies the title of the book and bears witness to the power of the human mind–a power that is far ahead of technology. No robot yet built can come close to duplicating a feat of pattern recognition that any bright preschooler can master in a few minutes.
The most astonishing feature of the magic eye trick is that the lion is lurking in the picture all along, in full view of the observer. Every bit of the complex information about its three-dimensional shape, angel wings and all, is openly displayed on the printed page–it’s just a matter of collecting that information in the right way. This task of decoding is a sophisticated example of what applied mathematicians call image processing.
The difficulty of image processing is evident even in one dimension, well before the peculiarities of plane and solid geometry complicate the problem. In one dimension, one speaks of a signal rather than an image, but the two concepts are intimately related. For a typical signal, think of the output of a microphone, which picks up sound by converting the fluctuating pressure of air on the surface of a membrane into an electric current. A record of the turbulent oscillations of that current constitutes a type of signal called a time series. It can be registered by a pen on a moving strip of paper, or chopped into digital data bits and stored electronically, or traced out visually by a dancing bright dot into a jagged line on the monitor screen of an oscilloscope.
Imagine that the microphone is installed in an open window above a busy city street, and that a girl in the house opposite strikes a middle C on her piano. Somewhere in the impenetrable thicket of the microphone signal, that note lies hidden. The human ear cannot pick it out of the noise of the street, and the eye cannot perceive its graceful pattern in the jittery excursions of the oscilloscope trace. To find that note is a test of the techniques of signal processing. It is a simple, one-dimensional analogue of finding a winged lion in a psychedelic jumble of colored splotches–but it isn’t easy.
WITHIN THE LAST TEN years the science of signal processing has undergone a revolution, one stirred up largely by wavelets. The speed of modern computers, together with the accuracy of wavelet analysis, now arms the signal processor with unprecedented power to recover that lonely musical note from the din of the city, to see a star in a galaxy of confused radio signals, to pick out a tumor lurking in a mass of innocent-looking tissue. But though the tools are new, the technique is old. Wavelet analysis is essentially a refinement of the method invented in the beginning of the nineteenth century by the French mathematician and physicist Jean-Baptiste Fourier.
Fourier discovered that every signal, no matter how complex it may appear, can be reproduced by adding a sufficient number of the simple, regular curves called sine waves. All sine waves are infinitely long serpentines with exactly the same unvarying shape. Two characteristics distinguish one sine wave from another: the wave’s amplitude, or the height of each crest, and its frequency–the number of crests recorded in a unit of time. A computer can reconstruct any signal, no matter how complex, by adding together a number of simple sine waves of different amplitudes and frequencies. Of course, as the number of constituent waves increases, so does the complexity of the resulting signal.
But Fourier went further. In addition to demonstrating how a signal can be synthesized, he showed how it can be analyzed. Given a signal, how do you find the waves that make it up? How do you dissect it into its constituent simple sine waves–the irreducible atoms of signal processing, so to speak? The solution he discovered is laborious in practice but easy work for a computer. It is a mathematical procedure that acts as a kind of filter for finding out how much any particular sine wave contributes to an arbitrary signal. The resulting list of the amplitudes and frequencies of the waves that make up a signal is called its Fourier representation. Sometimes it is referred to as a Fourier spectrum because of its similarity to the compilation of the intensities of the pure colors that make up any mixture of light.
Assume that the girl in the house across the street from our microphone strikes middle C and lets it reverberate. Unless the street noise is overwhelming, Fourier analysis of the signal will pick out the note and determine its amplitude with phenomenal accuracy. From the list of waves that combine to create the sound picked up by the microphone, the exceptional strength and persistence of middle C will stick out like a sore thumb.
Fourier analysis is good not only for picking out such signals as that reverberating piano note but also for describing them in a very concise way. Engineers relish this sort of shorthand, called compression, because by reducing the sheer volume of information that is needed to describe a signal, it helps them transmit signals more efficiently over crowded communications lines. A continuous signal consists in principle of an infinity of values, or in digitized form, of an immense number of data points. Transmitting that middle C would require measuring the signal thousands of times each second for as long as it reverberated and then sending those values. With Fourier analysis, however, all that is needed is a list of the amplitudes and frequencies of each of the signal’s constituent sine waves. Sine waves have the handy attribute of going on and on forever until they are told to stop, so each wave tacitly stands for an infinite number of points. Thus they are ideal shorthand for long, regular signals.
BUT FOR ALL ITS ELEGANCE AND power, Fourier analysis suffers from a severe drawback: it does not deal well with signals of short duration. Suppose that the girl across the street abandons her piano and strikes a cymbal. An oscilloscope would show the resulting sudden, brief, and loud signal as a tall, narrow spike. Fourier analysis of this signal yields a very large number of waves with high frequencies–each of infinite duration. When they are superimposed, they cancel one another out except at the one point in time when they all reinforce one another to produce the spike. All the components, taken individually, are spread out in time and therefore fail to reproduce the pinpoint timing of the spike. For the temporal structure of this particular signal, the original time series, in which it’s the cymbal clash that sticks out like a sore thumb, turns out to be a much better representation.
The success of Fourier analysis in describing frequencies and its failure to reproduce accurate timing are manifestations of a fundamental principle of signal processing. Applied to sound, the principle states: The more accurately you know the pitch of a note, the less precisely you can determine when it was struck, and vice versa. It is no accident that this insight recalls a famous result of quantum mechanics. Heisenberg’s celebrated uncertainty principle dictates that if you are certain about the position of a particle, you don’t know much about its velocity, and the other way around. In fact, the uncertainty principle is nothing but a consequence of signal processing applied to the atomic realm.
Seen in this light, the Fourier spectrum and the time series represent the two extremes of displaying a signal: if you want to know the pitch of the note struck on the girl’s piano, you use the spectrum; if you want to know when she hit the cymbal, you use the time series.
Of course, in practice, in the real, everyday world, we want both: from the chaos of a microphone signal we would like to extract information on pitch as well as on timing. In fact, there is an ancient representation of acoustic signals that manages to record both with unsurpassed economy–the familiar system of musical notation. By representing the timing and pitch of each note, and leaving out a wealth of such subsidiary information as the precise levels of intensity desired and the infinite subtleties of modulation that distinguish great music from mechanical reproduction, musical notation focuses on those properties of the score that have been singled out as paramount. For many decades signal analysts have been scrambling to develop the technological counterpart of the wonderful compromise music scribes achieved in medieval times by placing black dots on five parallel lines.
The most obvious marriage of a time series with a Fourier representation consists of dividing the signal into a sequence of finite time slots–windows, in the jargon of signal analysis–and then finding the appropriate Fourier representation for each slot. This procedure, called windowed Fourier analysis, is a mathematical version of musical notation. Each window corresponds to a specific, short interval of time; and its Fourier analysis, to the notes heard during that interval. The elements of this representation–the atoms from which arbitrarily complex signals can be constructed–are wave trains of short duration. They resemble serpentine inchworms and are the ancestors of what came to be called wavelets.
For some purposes, the windowed Fourier representation turns out to be an adequate compromise, but it too suffers from a serious shortcoming. Because each window has a fixed, finite length, it is impossible to locate a sharp spike in the signal very precisely: you can determine which window the spike belongs in, but not exactly where it occurs inside that frame.
ALL THIS WAS WELL KNOWN to Ingrid Daubechies when she was stumbling along Montreal’s icy streets. But she was also aware of a variety of new developments that have a bearing on the subject, in fields as diverse as quantum theory, seismology, and computer vision. What was needed, she felt, was a synthesis of all these strands that would yield a better representation of signals. And she found one.
Daubechies came up with a way of mathematically analyzing signals that works well for cymbal crashes and similar signals. Whereas Fourier analysis breaks down complex signals into their component sine waves, Daubechies’s method breaks them down into wavelets. These cleverly crafted little beasts have miraculous mathematical properties. For one, the length of each wavelet is mathematically related to the pitch it represents–the higher the pitch, the briefer the wavelet. Since a cymbal crash contains many high-frequency components, its constituent wavelets are brief; middle C, by contrast, contains longer wavelets. Daubechies’s wavelets also have no redundancy, which means that each wavelet is an essential component of the complex signal it represents. By contrast, the component sine waves used in windowed Fourier analysis have a great deal of redundancy, so they contain more information than is really necessary to reconstruct a signal.
Daubechies didn’t invent wavelets. Mathematicians had tinkered with the little critters before, but they couldn’t get them to do anything particularly useful. Indeed, before Daubechies discovered her own family of wavelets, applied mathematicians had almost convinced themselves that a viable wavelet analysis was impossible. At the same time, Fourier analysis left something to be desired. Fourier’s ingenious method of filtering out one frequency after another depends on the perfect smoothness and regularity of an infinitely long sinusoidal wave. Daubechies found herself forced to construct wavelets with unheard-of properties. Compared with the short, smooth elements of the windowed Fourier representation, her wavelets have fractal properties, which give some of them the appearance of Alpine cliffs. But, as she assured me, the computer doesn’t care about visual aesthetics, and those graceless crags conceal wonderful mathematical properties. “I guess we just have to live with the way they look,” she says of her homely creations with motherly solicitude.
As for effectiveness, the proof of the pudding is in the eating. How well can wavelets find musical notes and cymbal clashes in a noisy signal? To find out, Daubechies prepared a simulated test signal consisting of two drawn-out notes with similar pitches–such as C and C-sharp–as well as two cymbal clashes in quick succession. Then she subjected the signal to both a windowed Fourier analysis and a wavelet analysis, with striking results. The windowed Fourier representation was able to distinguish either the pitches of the two long notes or the timing of the two spikes, but not both at the same time. Wavelets, on the other hand, unambiguously sorted out the two frequencies as well as the two peaks. They served simultaneously as a microscope and a telescope, as it were. Daubechies’s analysis is, in a sense, the optimal compromise between two incompatible ways of recording a signal.
I asked Daubechies how she imagines her wavelets. She explained that she doesn’t think in terms of formulas or words, but mostly in pictures. To illustrate how they appear to her, she drew an array of dots to represent the data of a digitized signal and then connected them by means of a treelike structure issuing from a dot in the top line and broadening out toward the bottom. At the foot of the drawing, and on the right, she placed further dots to represent the fact that this scheme continues to the end of the signal. And then, shoving an invisible load forward and away from her body with simulated effort, with palms upturned and fingers splayed, she explained how in her mind she pushed and pulled on these connected dots to force them into different patterns. In the process she suddenly realized that if only she were clever enough, this prodding, instead of producing endlessly changing patterns, would eventually cause the dots to settle into a stable pattern. And that’s how she discovered her wavelets.
Although I understood only vaguely what she meant, her words vividly recalled to my mind how Einstein described his own thinking: “The words or the language,” he once responded to an interviewer’s question, “as they are written or spoken, do not seem to play any role in my mechanism of thought. The psychical entities which seem to serve as elements in thought are certain signs and more or less clear images which can be ‘voluntarily’ reproduced and combined…. The above-mentioned elements are, in my case, of visual and some muscular type. Conventional words or other signs have to be sought for laboriously only in a secondary stage.” Until I met Ingrid Daubechies I had never quite understood what he meant by that word muscular.
As applied mathematicians throughout the world learned of the remarkable properties of Daubechies’s wavelets, they began to incorporate them into their own work. Today “compactly supported orthonormal wavelet bases,” commonly called Daubechies wavelets, have become fundamental elements of the mathematical apparatus of signal processing. But Daubechies wants to do more than just prove pretty theorems–above all she wants to be helpful. “Wavelets are just tools,” she insists, “simple, versatile, powerful tools for performing a huge variety of tasks. That’s what I emphasize in all my talks.”
THESE DAYS SHE RECEIVES A lot of invitations to lecture. In part, her popularity can be attributed to the high premium she places on making sure that she is understood. Before she addresses people outside her own discipline of applied mathematics, she first learns to speak their language and seeks out illustrative examples they are familiar with. “I don’t pretend to be an engineer, or a physician, or a plasma physicist, but I try to find out how they have approached signal processing in their own way, instead of trying to impose my idiom on them.”
One of the applications of her work is finding meaningful patterns in turbulent systems. Whether the fluid is water gushing from a faucet, air pummeling the surface of an airplane wing, or hot, electrically charged gases racing through a fusion reactor, the underlying mathematical equations describing the processes, although they are known, are too complex to be solved by even the largest supercomputers. To find order in the description of a turbulent system is primarily a daunting exercise in image processing, which is essentially signal processing in multiple dimensions. The task is to discover, in the confusing maze of constantly shifting data, persistent eddies that escape the eye but betray the presence of unsuspected forces. The trick is to find the winged lion hidden in the random-looking data. But unless one knows what to look for, unless one has a good idea of the possible sizes and shapes of such eddies beforehand, they elude ordinary analysis. Wavelets may do better.
Another application of wavelet analysis depends on its ability to compress information. Every single fingerprint the FBI collects will eventually be digitized into about 80 million data bits. Over the course of time, the bureau has accumulated hundreds of millions of such prints, so it will face the danger of drowning in information. Accordingly, the FBI evaluated different image-processing technologies to find the one most effective at eliminating redundant data from this flood and facilitating the transmission and retrieval of the compressed data. By reducing the amount of raw data by a factor of about 20 and still managing to reproduce clearer images than its rivals, the wavelet representation won the competition hands down, and it is now in the course of being implemented: in the future, felons will owe their capture to Ingrid Daubechies’s theorems. I suspect that part of this victory may be related to her remarkable ability to communicate complicated ideas to people trained in fields far from her own.
But her favorite application at the moment is unrelated to the concerns of fluid mechanics or criminology. She has recently joined Princeton’s mathematics department, and in the coming months she plans to work closely with experts in biomedical research to apply her wavelets to the analysis of such signals as electrocardiograms, electroencephalograms, and the multitude of modern medical images produced with a wide variety of techniques.
An ECG, for example, is a long chart of the electric signal produced by the heart. Beyond the obvious periodicity of the pulse, an uninitiated viewer sees nothing but irregular noise. But to the expert this record encodes a wealth of hidden information about the functioning of our most vital muscle. Imagine how much that expert could be helped by having the record digitized, stored, and retrievable at will, to be compared with different traces of the same heart, or with those of others, and above all, to be statistically analyzed. Is it not likely that just as wavelets can discover a musical note or the crash of a cymbal in the noise of a street, they would be able to tease out subtle hints of abnormality or disease that escape superficial examination? Even if such a program could not replace the experienced eye of an expert, it would speed preliminary screening, and it could bring the benefits of modern medicine to people who have no access to it today. Or so Ingrid Daubechies hopes.
Whatever successes she may achieve in her endeavor to bring sophisticated mathematics to bear on biomedical problems, they will undoubtedly reflect her unique style. Just as her wavelets are designed to achieve the best possible compromise between two contradictory representations, her entire career is marked by her conscious effort to mediate between different approaches, to discover commonalities among disciplines, and to find harmony and coherence in diversity.
At the end of our meeting that day in Brussels, I asked her what she thought of Magic Eye. With mild regret she confessed that she had never been able to relax her eyes sufficiently to find the winged lion. But I suppose that’s not a great loss to someone whose inner vision is as powerful and clear as hers.
COPYRIGHT 1995 Discover
COPYRIGHT 2004 Gale Group