Fornew readers and those who request to be “好友 good friends” please read my 公告栏 first.

The US National Academy Pressrecently released a report with the following title

 Fueling Innovation and Discovery – The Mathematical Sciences in the21^st Century

 It is, in my opinion a model of popularscience writing. I reproduce below one short chapter both for illustration aswell as for learning.

 Chapter2. Compressed Sensing/Through the Kaleidoscope

In thelast two decades, two separate revolutions have brought digital media out of thepre-Internet age. Both revolutions were deeply grounded in the mathematical sciences.One of them is now mature, and you benefit whenever you go to a movie withcomputer-generated animation. The other revolution has just begun but isalready redefining the limits of feasibility in some areas of biologicalimaging, communication, remote sensing, and other fields of science.

The first could becalled the “wavelet revolution.”Wavelets are a mathematical method for isolating the most relevant pieces ofinformation in an image or in a signal of any kind (acoustic, seismic,infrared, etc.). There are coarse wavelets for identifying general features andfine wavelets for identifying particular details. Prior to wavelets,information was

represented in long,cumbersome strings of bits that did not distinguish importance. The centralidea of wavelets is that for most real-world images, we don’t need all the details(bytes) in order to learn something useful. In a 10-megapixel image of a face, forinstance, the vast majority of the pixels do not give us any usefulinformation. The human eye sees the general features that connote a face—anose, two eyes, a mouth— and then focuses on the places that convey the mostinformation, which tend to be edges of features. We don’t look at every hair inthe eyebrow, but we do look at its overall shape. We don’t look at every pixelin the skin, because most of the pixels will be very much like their neighbors.We do focus on a patch of pixels that contrast with their neighbors—which mightbe a freckle or a birthmark or an edge. Now much of this information can be representedmuch more compactly as the overlapping of a set of wavelets, each with adifferent coefficient to capture its weight or importance. In any typicalpicture, the weighting amplitude of most of the wavelets will be nearzero, reflecting the absence of features at that particular scale. If the model

in the photograph doesn’t have ablemish on a particular part of her skin, you won’t need the wavelet that wouldcapture such a blemish. Thus you can compress the image by ignoring all of thewavelets with small weighting coefficients and keeping only the others. Insteadof storing 10 million pixels, you may only need to store 100,000 or a millioncoefficients. The picture reconstructed from those coefficients will be indistinguishablefrom the original to the human eye.

Curiously, wavelets werediscovered and rediscovered more than a dozen times in the 20th century—forexample, by physicists trying to localize waves in time and frequency and bygeologists trying to interpret Earth movements from seismograms. In 1984, itwas discovered that all of these disparate, ad hoc techniques for decomposing asignal into its most informative pieces were really the same. This is typicalof the role of the mathematical sciences in science and engineering: Becausethey are independent of a particular scientific context, the mathematicalsciences can bridge disciplines. Once the mathematical foundation was laid,stronger versions of wavelets were developed and an explosion of applicationsoccurred. Some computer images could be compressed more effectively.Fingerprints could be digitized. The process could also be reversed: Animatedmovie characters could be built up out of wavelets. A company called Pixarturned wavelets (plus some pretty good story ideas) into a whole series of blockbustermovies.

In 2004, the central premise ofthe wavelet revolution was turned on its head with some simple questions: Whydo we even bother acquiring 10 million pixels of information if, as is commonlythe case, we are going to discard 90 percent or 99 percent of it with acompression algorithm? Why don’t we acquire only the most relevant 1 percent ofthe information to start with? This realization helped to start a secondrevolution, called compressed sensing.Answering these questions might appear almost impossible. After all, how can weknow which 1 percent of information is the most relevant until we have acquiredit all? A key insight came from the interesting application of how toreconstruct a magnetic resonance image (MRI) from insufficient data. MRIscanners are too slow to allow them

to capture dynamic images(videos) at a decent resolution, and they are not ideal for imaging patientssuch as children, who are unable to hold still and might not be good candidatesfor sedation. These challenges led to the discovery that MRI test images could,under certain conditions, be reconstructed perfectly—not approximately, but perfectly—froma too-short scan by a mathematical method called L1 (read as “ellone”) minimization.Essentially, random measurements of the image are taken, with each measurementbeing a randomly weighted average of many randomly selected pixels. Imaginereplacing your camera lens with a kaleidoscope. If you do this again and again,a million times, you can get a better image than you can from a camera thattakes a 10-megapixel photo through a perfect lens. Themagic lies, of course, in the mathematical sciences. Even though there maybe millions of scenes that would reproduce themillion pictures you took with your kaleidoscopiccamera, it is highly likely that there will be only one sparse scene thatdoes. Therefore, if you know the scene youphotographed is information-sparse (e.g., itcontains a heart and a kidney and nothing else) and measurement noise iscontrolled, you can reconstruct it perfectly.L1 minimization happens to be a good technique for zeroing in on that one sparse solution. Compressed sensingactually built on, and helped make coherent, ideas that had been applied ordeveloped in particular scientific contexts, such as geophysical imaging andtheoretical computer science, and even in mathematics itself (e.g., geometricfunctional analysis). Lots of other reconstruction algorithms are possible, anda hot area for current research is to find the ones that work best when the sceneis not quite so sparse.

As with wavelets,seeing is believing. Compressed sensing has the potential to cut down imagingtime with an MRI from 2 minutes to 40 seconds. Other researchers have usedcompressed sensing in wireless sensor networks that monitor a patient’sheartbeat without tethering him or her to an electrocardiograph. The sensorsstrap to the patient’s limbs and transmit their measurements to a remotereceiver. Because a heartbeat is information-sparse (it’s flat most of thetime, with a few spikes whose size and timing are the most importantinformation), it can be reconstructed perfectly from the sensors’ sporadicmeasurements.

Compressedsensing is already changing the way that scientists and engineers think aboutsignal acquisition in areas ranging from analog-to-digital conversion to digitaloptics and seismology. For instance, the country’s intelligence services have struggledwith the problem of eavesdropping on enemy transmissions that hop from one frequencyto another. When the frequency range is large, no analog-to-digital converter isfast enough to scan the full range in a reasonable time. However, compressedsensing ideas demonstrate that such signals can be acquired quickly enough toallow such scanning, and this has led to new analog-to-digital converterarchitectures. Ironically, the one place where you aren’t likely to findcompressed sensing used, now or ever, is digital photography. The reason isthat optical sensors are so cheap; they can be packed by the millions onto acomputer chip. Even though this may be a waste of sensors, it costs essentiallynothing. However, as soon as you start acquiring data at other wavelengths(such as radio or infrared) or in other forms (as in MRI scans), the savings incost and time offered by compressed sensing take on much greater importance.Thus compressed sensing is likely to continue to be fertile ground for dialoguebetween mathematicians and all kinds of scientists and engineers.

.

.