# From Wavelets to Compressed Sensing and Beyond

By Gail Corbett

On September 23, in formal ceremonies in Hong Kong, David Donoho of Stanford University received the 2013 Shaw Prize in Mathematical Sciences. Citing “his profound contributions to modern mathematical statistics,” the selection committee mentioned in particular his “development of optimal algorithms for statistical estimation in the presence of noise and of efficient techniques for sparse representation and recovery in large data-sets."

For more than two decades, according to the selection committee for the 2013 Shaw Prize in Mathematical Sciences, David Donoho of Stanford University has been a leading figure in mathematical statistics. Donoho, shown here (left) with Hong Kong Chief Executive C.Y. Leung, was cited by the committee for novel mathematical tools and ideas that have helped shape both the theoretical and applied sides of modern statistics. His work is characterized by the development of fast computational algorithms, together with rigorous mathematical analysis for a wide range of statistical and engineering problems. See page 3. Photo courtesy of David Donoho.

Within the sweeping citation are references to some of the most important mathematical/statistical research advances of recent years, many rooted in the latter half of the 1980s. Mathematicians at that time, Donoho’s Stanford colleague Iain Johnstone recalls, were crystallizing the theoretical and algorithmic possibilities of wavelets. Donoho, Johnstone says, “quickly saw implications of wavelets for statistical theory and statistical signal processing, where the presence of noisy and some-times indirect observation is a defining feature.”

He and Johnstone proposed thresholding algorithms that were both efficient and amenable to “detailed and elegant theoretical study using a blend of statistical decision theory, harmonic analysis, and approximation theory.” In estimation theory, Johnstone says, “Donoho changed the paradigm from ‘smoothness’ to ‘sparsity’ by showing that sparsity was the more powerful concept. When sparsity reduced to smoothness, traditional linear methods of estimation such as splines, kernels and spectral cut-off were provably optimal. By contrast, when sparsity could be identified in non-smooth settings, suitable nonlinear methods were demonstrably superior.”

Many in the SIAM community heard about Donoho’s subsequent interests in his invited talk at ICIAM 2003 and in his 2001 SIAM John von Neumann Lecture: “What Lies Beyond Wavelets? Explorations in Multiscale Thinking . . . .” Variants of multiscale thinking woven into the lecture ranged from Fourier integral operators to “ridgelets and curvelets for representation of edges in images, to beamlet detectors for filaments in noisy images.” Applications abounded, in data compression, statistical estimation, and pattern analysis.

Recommended reading for those interested in these research areas, or in the trajectory of such a successful research career, is the “Autobiography” Donoho wrote for the Shaw Prize website. In it, he paid tribute to a very early influence on his career: John Tukey, his undergraduate thesis adviser at Princeton, who advocated “robust statistical methods, such as fitting equations by minimizing the \(\ell_1\) norm of residuals rather than the \(\ell_2\) norm.” Tukey, Donoho wrote, “criticized ‘classical’ mathematical statistics as searching for polished answers to yesterday’s problems.”

Joining David Donoho (center) in Hong Kong during the 2013 Shaw Prize festivities were, from left, C.N. Yang, a 1957 Nobel laureate in physics; Miriam Donoho; Tony Chan, president of the Hong Kong University of Science and Technology; and Pak-Chung Ching, pro-vice-chancellor/vice-president of the Chinese University of Hong Kong. Donoho gave the prize lecture for the mathematical sciences, titled “Compressed Sensing: Past, Present, Future," at HKUST on September 24. Photo courtesy of David Donoho.

In the course of his career, Donoho has worked with many colleagues and more than twenty-five PhD students, who have derived both practical and theoretical results in related work. Prominent among exciting recent directions is “compressed sensing,” a term coined by Donoho for an area that he described in a 2004 paper of the same name. “Because the wavelet transform sparsifies images,” he explained in the paper, “images can be recovered from relatively few random measurements via \(\ell_1\) -minimization.”

In a concluding twist to his autobiographical statement, Donoho commented on a new approach to the sparsity/undersampling tradeoff that he and colleagues had developed: “Solving random underdetermined systems by \(\ell_1\)-minimization was revealed as identical to denoising of sparse signals embedded in noise [his emphasis]. Two separate threads of my research life became unified.”

In the statement, Donoho credited many people, both mathematical forebears and colleagues and students. Sure to play a role in any future autobiographical statement is Run Run Shaw, Hong Kong philanthropist, entertainment tycoon, and co-founder of Shaw Brothers, one of the world’s largest film studios. In 2002 he established the Shaw Prizes, which honor outstanding work in research and applications in the mathematical sciences, life science and medicine, and astronomy; presented annually, the prize in each field carries a cash award of U.S. $1 million. Shaw died in January 2014, at the age of 106.

Gail Corbett is the managing editor of *SIAM News*.