THE MATHEMATICAL MICROSCOPE

Waves, Wavelets, and Beyond

by Barbara Burke

Mathematician Michael Frazier of Michigan State University was educated in the tradition that maintains that "real" mathematics by "real" mathematicians is and should be useless. "I never expected to do any applications—I was brought up to believe I should be proud of that," he says. ''You did pure harmonic analysis for its own sake, and anything besides that was impure, by definition." But in the summers of 1990 and 1991 he found himself using a mathematical construction to pick out the pop of a submarine hull from surrounding ocean noise.

In St. Louis, Victor Wickerhauser was using the same mathematics to help the Federal Bureau of Investigation store fingerprints more economically, while at Yale University Ronald Coifman used it to coax a battered, indecipherable recording of Brahms playing the piano into yielding its secrets. In France, Yves Meyer of the University of Paris-Dauphine found himself talking to astronomers about how they might use these new techniques to study the large-scale structure of the universe.



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement



Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier THE MATHEMATICAL MICROSCOPE Waves, Wavelets, and Beyond by Barbara Burke Mathematician Michael Frazier of Michigan State University was educated in the tradition that maintains that "real" mathematics by "real" mathematicians is and should be useless. "I never expected to do any applications—I was brought up to believe I should be proud of that," he says. ''You did pure harmonic analysis for its own sake, and anything besides that was impure, by definition." But in the summers of 1990 and 1991 he found himself using a mathematical construction to pick out the pop of a submarine hull from surrounding ocean noise. In St. Louis, Victor Wickerhauser was using the same mathematics to help the Federal Bureau of Investigation store fingerprints more economically, while at Yale University Ronald Coifman used it to coax a battered, indecipherable recording of Brahms playing the piano into yielding its secrets. In France, Yves Meyer of the University of Paris-Dauphine found himself talking to astronomers about how they might use these new techniques to study the large-scale structure of the universe.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier Over the past decade a number of mathematicians accustomed to the abstractions of pure research have been dirtying their hands—with great enthusiasm—on a surprising range of practical projects. What these tasks have in common is a new mathematical language, its alphabet consisting of identical squiggles called wavelets, appropriately stretched, squeezed, or moved about. A whole range of information—your voice, your fingerprints, a snapshot, x-rays ordered by your doctor, radio signals from outer space, seismic waves—can be translated into this new language, which emerged independently in a number of different fields, and in fact was only recently understood to be a single language. In many cases this transformation into wavelets makes it easier to transmit, compress, and analyze information or to extract information from surrounding "noise"—even to do faster calculations. In their initial excitement some researchers thought wavelets might virtually supplant the much older and very powerful mathematical language of Fourier analysis, which you use every time you talk on the telephone or turn on a television. But now they see the two as complementary and are exploring ways to combine them or even to create more languages "beyond wavelets." Different languages have different strengths and weaknesses, points out Meyer, one of the founders of the field: "French is effective for analyzing things, for precision, but bad for poetry and conveying emotion—perhaps that's why the French like mathematics so much. I'm told by friends who speak Hebrew that it is much more expressive of poetic images. So if we have information, we need to think, is it best expressed in French? Hebrew? English? The Lapps have 15 different words for snow, so if you wanted to talk about snow, that would be a good choice." Some information processing is best done in the language of Fourier; other with wavelets; and yet other tasks might require new languages. For the first time in a great many years—almost two centuries, if one goes back to the very birth of Fourier analysis—there is a choice. A MATHEMATICAL POEM Although wavelets represent a departure from Fourier analysis, they are also a natural extension of it: the two languages clearly belong to the

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier same family. The history of wavelets thus begins with the history of Fourier analysis. In turn the roots of Fourier analysis predate Fourier himself (and much of what is now called Fourier analysis is due to his successors). But Fourier is a logical starting point; his influence on mathematics, science, and our daily lives has been incalculable, if to many people invisible. Yet he was not a professional mathematician or scientist; he fit these contributions into an otherwise very busy life. His father's twelfth child, and his mother's ninth, Joseph Fourier was born in 1768 in Auxerre, a town roughly halfway between Paris and Dijon. His mother died when he was nine and his father the following year. Although two younger siblings were abandoned to a foundling hospital after their mother's death, Fourier continued school and in 1780 entered the Royal Military Academy of Auxerre, where at age 13 he became fascinated by mathematics and took to creeping down at night to a classroom where he studied by candlelight. Fourier's academic success won the favor of the local bishop. But when at the end of his studies his application to join the artillery or the army engineers was rejected, he entered the abbey of St. Benoît-sur-Loire. (The popular story that he was rejected by the army because he was not of noble birth—and therefore ineligible "even if he were a second Newton"—is questioned by at least two of Fourier's contemporaries.) The French Revolution erupted before Fourier took his vows. At first indifferent, he became increasingly committed to the cause of establishing "a free government exempt from kings and priests"1 and in 1793 joined the revolutionary committee of Auxerre. Twice he was arrested, once in the bloody days shortly before the fall of Robespierre and again the following year, on charges of terrorism. In defending himself Fourier pointed out that during the Terror no one in Auxerre was condemned to death; a friend related that once, to prevent a man he believed to be innocent from arrest and the guillotine, Fourier invited the agent charged with the arrest to lunch at an inn and, "having exhausted every means of retaining his guest voluntarily," left the room on a pretext, locked the door, and ran to warn the suspect, returning later with excuses. After several years teaching in Paris, Fourier next accompanied Napoleon to Egypt, serving as permanent secretary of the Institute of Egypt that Napoleon had set up, in part to study Egypt's past and natural history. Upon Fourier's return to France, Napoleon appointed him prefect of the department of Isère. He served as prefect, living in Grenoble, for 14 years, earning a reputation as an able administrator; he was responsible for the draining of some 20,000 acres of swamps that

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier Mathematical Analysis … mathematical analysis … defines all observable relationships, measures time, space, force, temperature. This difficult science grows slowly but once ground has been gained it is never relinquished. … Analysis brings together the most disparate phenomena and discovers the hidden analogies which unify them. If material escapes us like air or light because of its extreme fineness, if bodies are placed far from us in the immensity of space, if man desires to know the aspect of the heavens for times separated by many centuries, if the effects of gravity and temperature occur in the interior of the solid earth at depths which will remain forever inaccessible, yet mathematical analysis can still grasp the laws governing the phenomena. Analysis makes them actual and measurable and seems to be a faculty of human reason meant to compensate for the brevity of life and the imperfection of our senses. … —Joseph Fourier, La Théorie Analytique de la Chaleur had caused annual epidemics of fever. After Waterloo, denied a government pension because he had served under Napoleon, he found a safe haven in the Bureau of Statistics in Paris, and in 1817 (after an initial rebuff by King Louis XVIII) he was elected to the Academy of Sciences. Despite his administrative duties—and his isolation from Paris for many years—Fourier managed to pursue his scientific and mathematical interests. Victor Hugo called him a man "whom posterity has forgotten,"2 but Fourier's name is as familiar to countless scientists, mathematicians, and engineers as the names of their own children. This fame rests on ideas he set forth in a memoir in 1807 and published in 1822 in his book, La Théorie Analytique de la Chaleur (The Analytic Theory of Heat). Physicist James Clark Maxwell called Fourier's book "a great mathematical poem," but the description does not begin to give an idea of its influence. In the seventeenth century Isaac Newton had a new insight: that forces are simpler than the motions they cause, and the way to understand the natural world is to use differential and partial differential equations to describe these forces—gravity, for example. Newton's differential equation showing how the gravitational pull between two objects is determined by their mass and the distance between them replaced countless observations, and predictive science became possible. Theoretically possible, at least. Solving differential equations—actually predicting where we will be taken by forces that

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier themselves depend at each moment on our changing position—is not easy. As Fourier himself wrote in La Théorie Analytique de la Chaleur , although the equations that describe the propagation of heat have a very simple form, "existing methods do not give any general way to integrate them; as a result it is impossible to determine the values of the temperature after a given period of time. This numerical interpretation … is nevertheless essential. … As long as we cannot achieve it … the truth that we wish to discover is as thoroughly hidden in the formulas of analysis as in the physical question itself."3 Some 150 years after Newton, Fourier provided a practical way to solve numerically a whole class of such equations, linear partial differential equations. His ideas dominated mathematical analysis for 100 years and had surprising ramifications even for number theory and probability. Outside mathematics their influence is difficult to exaggerate. Virtually every time scientists or engineers model systems or make predictions, they use Fourier analysis. Fourier's ideas have also found applications in linear programming, in crystallography, and in countless devices from telephones to radios and hospital x-ray machines; they are, in mathematician T. W. Körner's words, "built into the commonsense of our society." A RABBLE OF FUNCTIONS There are two parts to Fourier's contribution: first, a mathematical statement (actually proved later by Dirichlet), and, second, showing why this statement is useful. The mathematical statement is that any periodic (repeating) function can be represented as a sum of sines and cosines (see Figure 7.1). Roughly what this means is that any periodic curve, no matter how irregular (the output of an electrocardiogram, for example), can be expressed as the sum, or superposition, of a series of perfectly regular sine and cosine curves, of different frequencies. The irregular curve and the sum of sines and cosines are two different representations of the same object in different "languages." Even a jagged line can be represented as a Fourier series. The trick is to multiply the sines and cosines by a coefficient to change their amplitude (the height of their waves) and to shift them so that they either add or cancel (changing the phase). One can also treat nonperiodic functions this way, using the Fourier transform (see Box on p. 202). Fourier himself found this statement "quite extraordinary," and it met with some hostility. Mathematicians were used to functions that when graphed took the form of regular curves; the function f(x) = x2, for

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier FIGURE 7.1 In 1807 Fourier showed that any function (even an irregular one) can be expressed as the sum of a series of sines and/or cosines. The function at the top is a combination of the three functions below: sin (x), 0.3 sin (3x) and 0.2 cos (5x). example, produces a well-behaved, symmetrical parabola. (A function gives a rule of changing an arbitrary number into something else; f(x) = x2 says to square any number x; if x = 2, then f(x) = 4.) The idea that any arbitrary curve could be expressed as a series of sines and cosines and thus treated as a function came as a shock and contributed to a profound and sometimes disturbing change in mathematics; mathematicians spent much of the nineteenth century coming to terms with just what a function was. "We have seen a rabble of functions arise whose only job, it seems, is to look as little as possible like decent and useful functions," wrote French mathematician Henri Poincaré in 1889. "No more continuity, or perhaps continuity but no derivatives. … Yesterday, if a new function was invented it was to serve some practical end; today they are specially invented only to show up the arguments of our fathers, and they will never have any other use."4 Ironically, Poincaré himself was ultimately responsible for showing that seemingly "pathological" functions are essential in describing nature (leading to such fields as chaos and fractals), and this new direction for mathematics proved enormously fruitful, giving new vigor to a discipline that some had found increasingly anemic, if not moribund. In 1810 the French astronomer Jean-Baptiste Delambre had issued a report on mathematics expressing the fear that "the power of our methods is almost exhausted,"5 and some 30 years earlier Lagrange, comparing mathematics to a mine whose riches had all been exploited, wrote that it was ''not impossible that the mathematical positions in the academies will one day become what the university chairs in Arabic are now."6 "Looking back," writes Körner in his book Fourier Analysis, we can see Fourier's memoir "as heralding the surge of new mathematical methods and results which were to mark the new century." THE EXPLANATION OF NATURAL PHENOMENA The German mathematician Carl Jacobi wrote that Fourier believed the chief goal of mathematics to be "the public good and the explanation

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier FIGURE 7.2 The Fourier Transform The Fourier transform is the mathematical procedure by which a function is split into its different frequencies, like a prism breaking light into its component colors. But the Fourier transform goes further and tells both how much of each frequency the function contains (the amplitude of the frequency) and the phase of the signal at each frequency (the extent to which it is shifted with respect to a chosen origin). The term also describes the result of that operation: the Fourier transform of a particular function (that varies with time) is a new function (that varies with frequency). A Fourier series is a special case of Fourier transform, representing a periodic, or repeating, function. For functions that vary with time, such as sound recorded as changes in air pressure, or fluctuations in the stock market, frequency is generally measured in hertz or cycles per second. For functions that vary with space, "frequency" is often related to the inverse of a distance. For instance, the Fourier transform of a fingerprint will have large values near the "frequency" 15 ridges per centimeter. The Fourier series of a periodic function of period 2π is given by the formula The Fourier coefficients, an and bn, tell how much a signal contains of each frequency n: its amplitude at frequency n is the square root of . Calculating coefficients of the Fourier series of a function f(x) involves integral calculus: (This means that you multiply the function f(x) by the appropriate sine or cosine and integrate, measuring the area enclosed by the resulting curve; the result is divided by π. To multiply the function by a sine or cosine, the value of each point on the function is multiplied by the value of the corresponding point on the sine or cosine.) The phase can, in principle, be calculated from the coefficients. If you plot the point an, bn on a coordinate system, the amplitude is the length of the line from the origin to that point, while the phase is the angle formed by that line and the positive x axis (Figure 7.2). The function can be reconstructed from the coefficient using formula (1) above; the sine or cosine at each frequency is multiplied by its coefficient, and the resulting functions are added together, point by point; the first term is divided by 2.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier of natural phenomena," and Fourier showed how his mathematical statement could be used to study natural phenomena such as heat diffusion, by turning a difficult differential equation into a series of simple equations. Suppose, for example, we want to predict the temperature at time t of each point along a metal bar that has been briefly heated at one end. We start by establishing the initial temperature, at time zero, which we consider a function of distance along the bar. (This is why Fourier needed a technique that would work with all functions, even irregular or discontinuous ones: he couldn't expect the initial temperature to be so obliging as to take the form of a regular curve.) When that function is translated into a Fourier series a remarkable thing happens: the intractable differential equation describing the evolution of the temperature decouples, becoming a series of independent differential equations, one for the coefficient of each sine or cosine making up the function. These equations tell how each Fourier coefficient varies as a function of time. The equations, moreover, are very simple—the same as the equation that gives the value of a bank account earning compound interest (negative interest in this case). One by one, we simply plug in the coefficients describing the temperature at time zero and crank out the answers; these are the Fourier coefficients of the temperature at time t, which can be translated back into a new function giving the new temperature at each point on the bar. The procedure is no harder than the one banks use to compute the balance in their clients' accounts each month. Essentially we have made a little detour in Fourier space, where our calculations are immensely easier—as if, faced with the problem of multiplying the Roman numerals LXXXVI and XLI, we translated them into Arabic numerals to calculate 86 × 41 = 3526, and then translated the answer back into Roman numerals: LXXXVI × XLI = MMMDXXVI. The techniques Fourier invented have of course had an impact well beyond studies of heat or even solutions to differential equations. Real data tend to be very irregular: consider an electrocardiogram or the readings of a seismograph. Such signals often look like "complicated arabesques," to use Yves Meyer's expression—tantalizing curves that contain all the information of the signal but that hide it from our comprehension. Fourier analysis translates these signals into a form that makes sense. In addition, in many cases the sines and cosines making up a Fourier series are not simply a mathematical trick to make calculations easier; they correspond to the frequencies of the actual physical waves

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier making up the signal. When we listen to music or conversation, we hear changes in air pressure caused by sound waves—high sounds having high frequency and low sounds having lower frequency. (In fact, a piano can perform a kind of Fourier analysis: a loud sound near a piano with the damper off will cause certain strings to vibrate, corresponding to the different frequencies making up the sound.) Similarly—although this was not known in Fourier's time—radio waves, microwaves, infrared, visible light, and x-rays are all electromagnetic waves differing only in frequency. Being able to break down sound waves and electromagnetic waves into frequencies has myriad uses, from tuning a radio to your favorite station to interpreting radiation from distant galaxies, using ultrasound to check the health of a developing fetus, and making cheap long-distance telephone calls. With the discovery of quantum mechanics, it became clear that Fourier analysis is the language of nature itself. On the "physical space" side of the Fourier transform, one can talk about an elementary particle's position; on the other side, in "Fourier space" or "momentum space," one can talk about its momentum or think of it as a wave. The modern realization that matter at very small scales behaves differently from matter on a human scale—that at small scales we cannot have precise knowledge of both sides of the transform at once, we cannot know simultaneously both the position and momentum of an elementary particle—is a natural consequence of Fourier analysis. BEING ACADEMIC OR BEING REAL While irregular functions can be expressed as the sum of sines and cosines, those sums usually are infinite. Why translate a complex signal into an endless arithmetic problem, calculating an infinite number of coefficients, and summing an infinite number of waves? Fortunately, a small number of coefficients is often adequate. From the heat diffusion equation, for example, it is clear that the Fourier coefficients of high-frequency sines and cosines rapidly get exceedingly close to zero, and so all but the first few frequencies can safely be ignored. In other cases engineers may assume that a limited number of calculations give a sufficient approximation until proved otherwise. In addition, engineers and scientists using Fourier analysis often don't bother to add up the sines and cosines to reconstruct the signal—they "read" Fourier coefficients (at least the amplitudes; phases are more difficult) to get the information they want, rather the way some musicians can hear music silently, by reading the notes. They may spend

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier hours on end working quite happily in this "Fourier space," rarely emerging into "physical space." But the time it takes to calculate Fourier coefficients is a problem. In fact, the development of fast computers and fast algorithms has been crucial to the pervasive, if quasi-invisible, use of Fourier analysis in our daily lives in connection with today's digital technology. The basis for digital technology was given by Claude Shannon, a mathematician at Bell Laboratories whose Mathematical Theory of Communications was published in 1948; while he is not well known among the general public, he has been called a "hero to all communicators."7 Among his many contributions to information theory was the sampling theorem (discovered independently by Harry Nyquist and others). This theorem proved that if the range of frequencies of a signal measured in hertz (cycles per second) is n the signal can be represented with complete accuracy by measuring its amplitude 2n times a second. This result, a direct consequence of Fourier analysis, is simple to state and not very difficult to prove, but it has had enormous implications for the transmission and processing of information. It is not necessary to reproduce an entire signal; a limited number of samples is enough. Since the range of frequencies transmitted by a telephone line is about 4000 hertz, 8000 samples per second are sufficient to reconstitute your voice when you talk on the telephone; when music is recorded on a compact disc, about 44,000 samples a second are used. Measuring the amplitude more often, or trying to reproduce it continuously, as with old-fashioned records, does not gain anything. Another consequence is that, in terms of octaves, more samples are needed in high frequencies than in low frequencies, since the frequency doubles each time you go up an octave: the range of frequency between the two lowest As on a piano is only 28 hertz, while the range of frequency between the two highest As is 1760 hertz. Encoding a piece of music played in the highest octave would require 3520 samples a second; in the lowest octave, 56 would be enough. The sampling theorem opened the door to digital technology: a sampled signal can be expressed as a series of digits and transmitted as a series of on-and-off electrical pulses (creating, on the other hand, round-off errors). Your voice can even be shifted temporarily into different frequencies so that it can share the same telephone line with many other voices, contributing to enormous savings. (In 1915 a 3-minute call from coast to coast cost more than $260 in today's dollars). In 1948 Shannon and his colleagues Bernard Oliver and John Pierce expected digital

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier The Fast Fourier Transform An algorithm is a recipe for doing computations. When schoolchildren learn to "carry," "borrow," or multiply two-digit numbers without a calculator, they are learning algorithms. Fast algorithms are mathematical shortcuts for dealing with large computations. The fast Fourier transform, published by J. W. Cooley and T. W. Tukey in 1965, is a prime example. It cuts the number of computations from n2 in standard Fourier analysis to n log n. When n is big, this makes a substantial difference: if n = 1,000,000, then n2 = 1,000,000,000,000, but n log n = 6,000,000 (log 1,000,000 is 6 since 106 = 1,000,000). The logarithm is roughly the number of digits, so it grows slowly. The larger n is, the more impressive the difference becomes. If n is a billion and a computer can complete a billion calculations a second, this cuts computing time from approximately 32 years to 9 seconds. With the FFT one can computer π to a billion digits in about 45 minutes; without it the job would take almost 10,000 years. transmission to "sweep the field of communications;"8 the revolution came, if later than they had expected. Fueling this revolution was the fast Fourier transform (see Box on this page), a mathematical trick that catapulted the calculation of Fourier coefficients out of horse-and-buggy days into supersonic travel. With it, calculations could be done in seconds that previously were too costly to do at all. "It's the difference," Michael Frazier says, "between being academic and being real." This fast algorithm, known as the FFT, requires computers in order to be useful. "Once the method was established it became clear that it had a long and interesting prehistory going back as far as Gauss," Körner writes. "But until the advent of computing machines it was a solution looking for a problem." On the other hand, the gain in speed from the FFT is greater than the gain in speed from better computers; indeed, significant gains in computer speed have come from such fast algorithms built into computer hardware. DRIVING A CAR HALF A BLOCK It could be argued that the fast Fourier transform was too successful. "Because the FFT is very effective, people have used it in problems

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier The wavelet method stands this traditional wisdom on its head. Making no assumptions about the signal, Donoho says, "you do as well as someone who makes correct assumptions, and much better than someone who makes wrong assumptions." (Furthermore, if you do know something about the signal, you can adjust the coefficient threshold and get even better results.) The trick is that an orthogonal wavelet transform makes a signal look very different while leaving noise alone. "Noise in the signal becomes noise in the wavelet transform and it has about the same size at every resolution and location," Donoho says. (That all orthogonal representations leave noise unchanged has been known since the 1930s.) So while noise masks the signal in "physical space," the two become disentangled in "wavelet space." In fact, Donoho said, a number of researchers—at the Massachusetts Institute of Technology, Dartmouth, the University of South Carolina, and elsewhere—independently discovered that thresholding wavelet coefficients is a good way to kill noise. "We came to it by mathematical decision theory, others simply by working with wavelet transforms and noticing what happened," he said. Among those was Mallat, who uses a somewhat different approach. Donoho's method works for a whole range of functions but isn't necessarily optimal for each. When it is applied to blurred images, for example, it damages some of the edges; the elimination of small coefficients creates ripples that can be annoying. Mallat and graduate student Wen Liang Hwang developed a way to avoid this by computing the wavelet transform of the signal and selecting the points where the correlation between the curve and the wavelet is greatest, compared to nearby points. These maximum values, or wavelet maxima, are kept if the points are thought to belong to a real edge and discarded if they are thought to correspond to noise. (That decision is made automatically, but it requires more calculations than Donoho's method; it is based on the existence and size of maxima at different resolutions.) WAVELETS DON'T EXIST … Although Donoho and Johnstone's technique is simple and automatic, wavelets aren't always foolproof. With orthogonal wavelets it can matter where one starts encoding the signal: shifting over a little can change the coefficients completely, making pattern analysis hazardous. This danger does not exist with continuous wavelets, but they have their own pitfalls; what looks like a correlation of coefficients (different coefficients "seeing" the same part on the signal) may sometimes be an

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier artifact introduced by the wavelets themselves. "It's the kind of thing where you can shoot yourself in the foot without half trying," Grossmann said. Generally, using wavelets takes practice. "With a Fourier transform, you know what you get," Meyer says. "With a wavelet transform you need some training in order to know what you get. I have a report from EDF [Electricité de France] giving conclusions of engineers about wavelets—they say they have trouble with interpretation." Part of that difficulty may be fear of trying something new; Gregory Beylkin of the University of Colorado at Boulder reports that one student, who learned to use wavelets before he knew Fourier analysis, experienced no difficulty. Farge has had similar experiences, but Meyer thinks the problem is real. Because Fourier analysis has existed for so long, and most physicists and engineers have had years of training with Fourier transforms, interpreting Fourier coefficients is second nature to them. In addition, Meyer points out, Fourier transforms aren't just a mathematical abstraction: they have a physical meaning. "These things aren't just concepts, they are as physical, as real, as this table. But wavelets don't exist in nature; that's why it is harder to interpret wavelet coefficients," he said. Curiously, though, both our ears and our eyes appear to use wavelet techniques in the first stages of processing information. The work on "wavelets" and hearing goes back to the 1930s, Daubechies said. "They didn't talk about wavelets—they talked about constant q filtering, in which the higher the frequency, the better resolution you have in time." This is unlikely to lead to new insights about hearing or vision, she said, but it could make wavelets effective in compressing information. "If our ear uses a certain technique to analyze a signal, then if you use that same mathematical technique, you will be doing something like our ear. You might miss important things, but you would miss things that our ear would miss too." COMPRESSING INFORMATION One way to cope with an ever-increasing volume of signals is to widen the electronic highways—for example, by moving to higher frequencies. Another, which also reduces storage and computational costs, is to compress the signal temporarily, restoring it to its original form when needed. In fact, only a small number of all possible "signals" are capable of being compressed, as the Russian mathematician Andrei Kolmogorov pointed out in the 1950s. A compressible signal can by definition be expressed

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier by something shorter than itself: one sequence of digits (the signal) is encoded by a shorter sequence of digits (e.g., a computer program). It is easy to see that, using any given language (such as the computer language Pascal), the number of short sequences is much smaller than the number of long sequences: most long sequences cannot be encoded by anything shorter than themselves. (Even a highly efficient encoding scheme like a library card catalog cannot cope with an infinite number of books; eventually, the only way to distinguish one book from another would be to print the entire book in the card catalog.) Like Heisenberg with his uncertainty principle, Kolmogorov has set an absolute limit that mathematicians and scientists cannot overcome, however clever they are. Accepting some loss of information makes more compression possible, but a limit still remains. In practice, however, many signals people want to compress have a structure that lends itself to compression; they are not random. For instance, any point in such a signal might be likely to be similar to points near it. (In a picture of a white house with a blue door, a blue point is likely to be surrounded by other blue points, a white point by other white points.) Wavelets lend themselves to such compression; because wavelet coefficients indicate only changes, areas with no change (or very small change) are automatically ignored, reducing the number of figures that have to be kept to encode the information. So far, Daubechies says, image compression factors of about 35 or 40 have been achieved with wavelets with little loss. That is, the information content of the compressed image is about 1/35th or 1/40th the information content of the original. But wavelets alone cannot achieve those compression factors; an even more important role is played by clever quantization methods, mathematical ways of giving more weight in the encoding to information that is important for human perception (edges, for example) than information that is less so. "If you just buy a commercially available image compressor you can get a factor of 10 to 12, so we're doing better than that," Daubechies said. "However, people in research groups who fine-tune the Fourier transform techniques in commercial image compressors claim they can also do something on the order of 35. So it's not really clear that we can beat the existing techniques. I do not think that image compression—for instance, television image compression—is really the place where wavelets will have the greatest impact." But the fact that wavelets concentrate the information of a signal in relatively few coefficients makes them good at detecting edges in images, which may result in improved medical tests. Healy and Weaver have

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier found that with wavelets they can use magnetic resonance imaging to track the edge of the heart as it beats by sampling only a few coefficients. And wavelet compression is valuable in speeding some calculations. In the submarine detection work that Frazier and colleague Jay Epperson did for Daniel H. Wagner Associates, they were able to compress the original data by a factor of 16 with good results. Ways to compress huge matrices (square or rectangular arrays of numbers) have been developed by Beylkin, working with Ronald Coifman and Vladimir rokhlin at Yale. The matrix is treated as a picture to be compressed; when it is translated into wavelets, "every part of the matrix that could be well represented by low-degree polynomials will have very small coefficients—it more or less disappears," Beylkin says. Normally, if a matrix has n2 entries, then almost any computation requires at least n2 calculations and sometimes as many as n3. With wavelets one can get by with n calculations—a very big difference when n is large. Talking about numbers "more or less" disappearing, or treating very small coefficients as zero, may sound sloppy but it is "very powerful, very important"—and must be done very carefully, Grossmann says. It works only for a particular large class of matrices: "If you have no a priori knowledge about your matrix, if you just blindly use one of those things, you can expect complete catastrophe." Just how important these techniques will prove to be is still up in the air. Daubechies predicts that "5, certainly 10 years from now you'll be able to buy software packages that use wavelets for doing big computations, in simulations, in solving partial differential equations." Meyer is more guarded. "I'm not saying that algorithmic compression by wavelets is a dead end; on the contrary, I think it's a very important subject. But so far there is very little progress; it's just starting." Of the matrices used in turbulence, he said, only one in 10 belongs to the class for which Beylkin's algorithm works. "In fact, Rokhlin has abandoned wavelet techniques in favor of methods adapted to the particular problem; he thinks that every problem requires an ad hoc solution. If he is right, then Ingrid Daubechies is wrong, because there won't be 'prefabricated' software that can be applied to a whole range of problems, the way prefabricated doors or windows are used in housing construction." TURBULENCE AND WAVELETS Rokhlin works on turbulent flows in connection with aerodynamics; Marie Farge in Paris, who works in turbulence in connection with

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier weather prediction, remains confident that wavelets will prove to be an effective tool. She was working on her doctoral thesis when she heard about wavelets from Alex Grossmann in 1984. "I was very much excited—in turbulence we have needed a tool like wavelets for a long time," she said. (Much later she learned that some turbulence researchers in the former Soviet Union, in Perm, had been working with similar techniques completely independently since 1976.) "When you look at turbulence in Fourier space," Farge explains, "you see cascades of energy, where energy is transferred from one wavenumber [frequency] to another. But you don't see how those cascades relate to what is happening in physical space; we had no tool that let us see both sides at once, so we could say, voilà , this cascade corresponds to this interaction. So when Alex showed me that wavelets were objects that allowed one to unfold the representation both in physical space and in scale, I said to myself, this is it, now we're going to get somewhere. "I invited him to speak in a seminar and told everyone in the turbulence community in Paris to come. I was shocked by their reaction to his talk. 'Don't waste your time on that,' they told me. Now some of the people who were the most skeptical are completely infatuated and insist that everyone should use wavelets. It's just as ridiculous. It's a new tool, and one cannot force it into problems as shapeless as turbulence if it isn't calibrated first on academic signals that we know very well. We have to do a lot of experiments, get a lot of practice, develop methods, develop representations." She uses orthogonal wavelets, or related wavelet packets, for compression but continuous wavelets for analysis: "I would never read the coefficients themselves in an orthogonal basis; they are too hard to read." With continuous wavelets she can take a one-dimensional signal that varies in space, put it into wavelet space, and get a two-dimensional function that varies with space and scale: she can actually see, on a computer screen or a printout what is happening at different scales at any given point. Orthogonal wavelets also give time-scale information, of course (although in a rougher form, since one doubles the scale each time, ignoring intermediate scales). The difference is largely one of legibility. Once, Meyer says, Jean Jacques Rousseau invented a musical notation based on numbers rather than notes on a staff, only to be told that it would never catch on, that musicians wanted to see the shape and movement of music on the page, to see the patterns formed by notes.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier The coefficients of orthogonal wavelets correspond to Rousseau's music by numbers; continuous wavelets to the musical notation we know. Farge compares the current state of turbulence research to "prescientific zoology." Many observations are needed, she says, to see what structures in turbulence are dynamically important and to try to recreate the theory in terms of their interactions. Possible candidates are ill-defined creatures called "coherent structures" (a tornado, for example, or the vortex that forms when you drain the bath). She uses wavelets to isolate them and to see how many exist at different scales or whether a single structure exists at a whole range of scales. Identifying the dynamically important structures would tell researchers "where we should invest lots of calculations and where we can skimp," Farge said. For studying turbulence requires calculations that defy the most powerful computers. The Reynolds number for interactions of the atmosphere—a measure of its turbulence—ranges from 109 to 1012; direct computer simulations of turbulence can now handle Reynolds numbers on the order of 102 or 103. But so far the results have been disappointing, Meyer says: "There should be something between turbulence and wavelets, everyone thinks so, but so far no one has a real scientific fact to offer." Certainly wavelets do not offer an easy trick for solving nonlinear equations (such as the Navier-Stokes equation used to describe turbulent flows), in the way that Fourier turned many linear equations into cookbook problems. "Wavelets are structurally a little better adapted to nonlinear situations," such as those found in turbulence, Meyer said. "But is something that is better in principle actually better in practice?" He is disturbed that when wavelets are used in nonlinear problems they "are used in a neutral way; they are always the same wavelets—they aren't adapted to the problem. … It is in this sense that there is perhaps a doubt about using wavelets to solve nonlinear problems. What can one hope for from methods that don't take the particular problem into account? At the same time, there are general methods in science. So one can give a different answer depending on one's personality." FINGERPRINTS AND HUNGARIAN DANCES One contribution of wavelets, Farge says, is that they have "forced people to think about what the Fourier transform is, forced them to think that when they choose a type of analysis they are in fact mixing the signal and the function used for the analysis. Often when people use the same technique for several scientific generations, they become blind to it."

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier As work with wavelets progressed, it became clear that if Fourier analysis had limitations, wavelet analysis did also. As David Marr wrote in Vision, "Any particular representation makes certain information explicit at the expense of information that is pushed into the background and may be quite hard to recover." Very regular, periodic signals are more easily recognized, and more efficiently encoded, by a Fourier transform than by wavelets, for example. So Coifman, Meyer, and Wickerhauser developed an information-compression scheme to take advantage of the strengths of both Fourier and wavelet methods: the "Best Basis" algorithm. In Best Basis a signal enters a computer like a train entering a switchyard in a train station. The computer analyzes the signal and decides what basis could encode it most efficiently, with the smallest possible amount of information. At one extreme it might send the signal to Fourier analysis (for signals that resemble music, with repeating patterns). At the other extreme it might send it to a wavelet transform (irregular signals, fractals, signals with small but important details). Signals that don't fall clearly into either group are represented by "wavelet packets" that combine features of both Fourier analysis and wavelets. Loosely speaking, a wavelet packet is the product of a wavelet by a wiggle, an oscillating function. The wavelet itself can then react to abrupt changes, while the wiggle inside can react to regular oscillations. "The idea is that you are introducing a new freedom," Meyer said. Since the choice of wiggles is infinite, "it gives a family that is very rich." Working with the FBI, Wickerhauser and Coifman applied Best Basis to the problem of fingerprint compression, and in a test conducted by the FBI's Systems Technology Unit it outperformed other methods. (Because Best Basis was being patented, Wickerhauser said, the FBI did not adopt it but instead custom-made a similar technique.) So far, the wavelet technique is intended only to compress fingerprints for storage or transmission, reconstructing them before identification by people or machines. But the FBI plans to hold a competition for automatic identification systems. "Those who understand how to use wavelet coefficients to identify will probably win, on speed alone if nothing else, because the amount of data is so much less," Wickerhauser said. In studies with military helicopters, Best Basis has been used to simplify the calculations needed to decide, from radar signals, whether a possible target is a tank or perhaps just a boulder. In trials the Best Basis algorithm could compress the 64 original numbers produced by the radar system to 16 and still give "identical or better results than the original 64, especially in the presence of noise," Wickerhauser said.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier But probably the most unusual use of Best Basis has been in removing noise from a battered recording of Brahms playing his own work, recorded in 1889 on Thomas Edison's original phonograph machine, which used tinfoil and wax cylinders to record sound. The Yale School of Music had entrusted it to Coifman after all else had failed. "Brahms was recorded playing his music for Edison," Wickerhauser said. "It was played on the radio sometime in the 1920s—possibly using a wooden needle, and was recorded off the radio. Then it was converted to a 78 record. That was the condition in which Yale had it—beaten to death." Coifman's approach was to say that noise can be defined as everything that is not well structured and that "well structured" means easily expressed, with very few terms, with something like the Best Basis algorithm. So the idea is to use Best Basis to decompose the signal and to remove anything that is left over. The result was not musical—no one hoped for that, from a recording that contained perhaps 30 times as much noise as signal—but they were able to identify the music as variations on Hungarian dances. The project, with Jonathan Berger of the Yale School of Music, is still going on. "We don't know yet how far we can restore it," Coifman said. BEYOND WAVELETS For some purposes, however, Best Basis is not ideal. Because it treats the signal as a whole, it has trouble dealing with highly nonstationary signals—signals that change unpredictably. To deal with such signals Stéphane Mallat and Zhifeng Zhang have produced a more flexible system, called Matching Pursuits, which finds the best match for each section of the signal, out of "dictionaries" of waveforms. "Instead of trying to globally optimize the match for the signal, we're trying to find the right waveform for each feature," Mallat said. "It's as if we're trying to find the best match for each 'word' in the signal, while Best Basis is finding the best match for the whole sentence." Depending on the signal, Matching Pursuits uses one of two "dictionaries": one that contains wavelet packets and wavelets, another that contains wavelets and modified "windowed Fourier" waveforms. (While in standard windowed Fourier the size of the window is fixed and the number of oscillations within the window varies, in Matching Pursuits the size of the window is also allowed to vary.) First, the appropriate dictionary is scanned and the "word" chosen that best matches the signal; then that "word'' is subtracted out, and the best match is chosen for the remaining part of the signal, and so on. (To some

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier extent, the dictionaries can produce words on command, modifying waveforms to provide a better fit.) Because the waveforms used are not orthogonal to each other, the system is slower than Best Basis: n2 calculations compared to n log n for Best Basis. On the other hand, the lack of orthogonality means that it doesn't matter where on the signal you start encoding. This makes it better suited for pattern recognition, for encoding contours and textures, for example. But the quest for new ways to encode information is far from over. "When you speak, you have a huge dictionary of words and you pick the right words so that you can express yourself in a few words. If your dictionary is too small, you'll need a lot of words to express one idea," Mallat said. "I think the challenge we are facing right now is, when you have a problem, how are you going to learn the right representation? The Fourier transform is a tool, and the wavelet transform is another tool, but very often when you have complex signals like speech, you want some kind of hybrid scheme. How can we mathematically formalize this problem?" In some cases the task goes beyond mathematics; the ultimate judge of effective compression of a picture, or of speech, is the human eye or ear, and developing the right mathematical representation is often intimately linked to human perception. Information is not all equal. Even a young child can draw a recognizable outline of a cat, for example, while the very notion of a drawing without edges is perplexing, like the Cheshire cat who vanished, leaving only his smile. Other differences are less well understood. People have no trouble differentiating textures, for example, while "after 20 years of research on texture, we still don't really know what it is mathematically," Mallat said. Wavelets may help with this, especially since some wavelet-like techniques are used in human vision and hearing, but any illusions researchers may have had that wavelets will solve all problems unsuited to Fourier analysis have long since vanished; the field has become wide open. "Wavelets have gone off in many directions; it becomes a little bit of a scholastic question, what you call wavelets," Grossmann says. "Some of the most interesting very recent things would technically not be called wavelets, the scale is introduced in a somewhat different way—but who cares?" It may not be the least of the contributions made by wavelets that they have inspired both a closer and a broader look at mathematical languages for expressing information: a more judicious look at Fourier analysis, which was often used reflexively ("The first thing any engineer

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier does when he gets hold of a function is to Fourier transform it—it's an automatic reaction," one mathematician said) and a more free-ranging look at what else might be possible. "When you have only one way of expressing yourself, you have limits that you don't appreciate," Donoho says. "When you get a new way to express yourself, it teaches you that there could be a third or a fourth way. It opens up your eyes to a much broader universe." NOTES 1.   Herivel (1975), p.27 (letter to Villetard, 1795; original in the archives of the Académie des Sciences, Institut de France, Paris). 2.   Hugo, Les Misérables, edition folio, vol. 1, p.185 3.   Fourier (1888), p. 9 4.   Körner (1988), p. 42; original in "La logique et l'intuition dans la science mathématique et dans l'enseignement," in Oeuvres de Henri Poincaré, vol. 11. 5.   Delambre (1810), p. 125 6.   Lagrange (1882). Oeuvres de Lagrange, vol. 13, p. 368 7.   Pierce and Noll (1990), p. 55 8.   Pierce and Noll (1990), p. 79 9.   Meyer (1993), p. 86 10.   Farge (1993), p. 195 11.   Meyer (ed., 1992), p. 286 REFERENCES Cousin, V. 1831. Notes biographiques pour faire suite à l'éloge de M. Fourier (Biographical notes to follow praise of Mr. Fourier), Fourier file AdS, archives, Académie des Sciences, Institut de France, Paris. Delambre, Jean-Baptiste. 1810. Rapport historique sur le progrès des sciences mathématiques depuis 1789 (Historical report on the progress of mathematical sciences since 1789), part of Rapport à l'Empereur sur le progrès des sciences, des lettres et des arts depuis 1789, published by Belin, Paris, 1989. Encyclopedia Britannica, 11th ed. 1972. Harmonic analysis. Vol. 11, pp. 106–107. Farge, M., J.C.R. Hunt and J.C. Vassilicos (eds). 1993. Wavelets, Fractals, and Fourier Transforms . Clarendon Press, Oxford. Fourier, J. 1822. Théorie analytique de la chaleur (published in Oeuvres de Fourier, Vol. 1, Gauthier-Villars et fils, Paris 1888). Healy, D., Jr., and J. B. Weaver. 1992. Two Applications of Wavelets Transforms in Magnetic Resonance Imaging. IEEE Transactions on Information Theory, Vol. 38, No. 2, March 1992. Herivel, J. 1975. Joseph Fourier — the Man and the Physicist. Clarendon Press, Oxford. Körner, T.W. 1988. Fourier Analysis. Cambridge University Press, Cambridge. Lagrange, J.-L. Oeuvres de Lagrange, Gauthier-Villars, Paris, 1867–1892. Marr, D. 1982. Vision. W. H. Freeman, New York. Meyer, Y. (ed). 1992. Wavelets and Applications: Proceedings of the International Conference, Marseille, France. Masson and Springer-Verlag.

OCR for page 196
A Positron Named Priscilla: Scientific Discovery at the Frontier Meyer, Y. 1993. Wavelets: algorithms & applications. Society for Industrial and Applied Mathematics, Philadelphia. (This is an English translation of Les Ondelettes Algorithmes et Applications, Meyer, Y., Armond Colin, Paris, 1992.) Pierce, J. R., and A. M. Noll. 1990. Signals — The science of telecommunications. Scientific American Library, New York. Poincaré, H. 1956. Oeuvres de Henri Poincaré, vol. 11, Gauthier-Villars, Paris. Strichartz, R. 1993. How to make wavelets, American Mathematical Monthly, Vol. 100, no. 6, June-July 1993, pp. 539–556. Strömberg, J.-O. 1981. A modified Franklin system and higher-order spline systems on Rn as unconditional bases for Hardy spaces. Conference on Harmonic Analysis in Honor of Antoni Zygmund, vol. II, pp. 475–494; W. Beckner, A. Caldéron, R. Fefferman, and P. Jones, eds. University of Chicago, 1983. RECOMMENDED READING Books Accessible to the General Public Gratten-Guinness, I., and J.R. Ravetz. 1972. Joseph Fourier, 1768–1830. MIT Press, Cambridge, Mass. Herivel, John. 1975. Joseph Fourier—The Man and the Physicist. Clarendon Press, Oxford. Körner, T.W. 1988. Fourier Analysis. Cambridge University Press, Cambridge. (This is a book for mathematicians, but it includes delightful sections that require no mathematical background, such as the description of the laying of transatlantic cables, where "half a million pounds was being staked on the correctness of the solution of a partial differential equation." ) Pierce, John R., and A. Michael Noll. 1990. Signals—The Science of Telecommunications. Scientific American Library, New York. A Sampling Of Technical Books Benedetto, J., and M. Frazier (eds.) 1993. Wavelets: Mathematics and Applications. CRC Press, Boca Raton. Chui, C.K. (ed.). 1992. Wavelets-A Tutorial in Theory and Applications. Academic Press, Boston. Daubechies, I. 1992. Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics, Philadelphia. Farge, M., J.C.R. Hunt, and J.C. Vassilicos (eds.). 1993. Wavelets, Fractals, and Fourier Transforms. Clarendon Press, Oxford. Körner, T.W. 1988. Fourier Analysis. Cambridge University Press, Cambridge. Meyer, Y. 1990. Ondelettes et Opérateurs. Three volumes. Hermann, Paris. (English translation published by Cambridge University Press in 1992.) Meyer, Y. 1992 Wavelets and Operators, Cambridge University Press, Cambridge and New York. (This is a translation of Ondelettes et Operateurs, Hermann, Paris, 1990.) Meyer, Y. 1993. Wavelets: algorithms & applications. Society for Industrial and Applied Mathematics, Philadelphia. Ruskai, B. (ed.) 1992. Wavelets and Their Applications. Jones and Bartlett, Boston.