Academic Press is an imprint of Elsevier
30 Corporate Drive, Suite 400
Burlington, MA 01803
This book is printed on acid-free paper.
⬁
Copyr ight © 2009 by Elsevier Inc. All rights reserved.
Designations used by companies to distinguish their products are often claimed as trade-marks or
registered trademarks. In all instances in which Academic Press is aware of a claim, the product
names appear in initial capital or all capital letters. Readers, however, should contact the appropriate
companies for more complete information regarding trademarks and registration.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form
or by any means, electronic, mechanical, photocopying, scanning, or otherwise, without prior written
permission of the publisher.
Permissions may be sought directly from Elsevier’s Science & Technology Rights Department in
Oxford, UK: phone: (+44) 1865 843830, fax: (+44) 1865 853333, e-mail: permissions@elsevier.com.
You may also complete your request on-line via the Elsevier homepage (http://elsevier.com), by
selecting “Support & Contact” then “Copyright and Permission” and then “Obtaining Permissions.”
Library of Congress Cataloging-in-Publication Data
Application submitted
ISBN 13: 978-0-12-374370-1
For information on all Academic Press publications,
visit our Website at www.books.elsevier.com
Printed in the United States
0809101112 10987654321
À la mémoire de mon père, Alexandre.
Pour ma mère, Francine.
Preface to the Sparse Edition
I cannot help but find striking resemblances between scientific communities and
schools of fish. We interact in conferences and through articles, and we move
together while a global trajectory emerges from individual contributions. Some of
us like to be at the center of the school, others prefer to wander around, and a few
swim in multiple directions in front. To avoid dying by starvation in a progressively
narrower and specialized domain, a scientific community needs also to move on.
Computational harmonic analysis is still very much alive because it went beyond
wavelets. Writing such a book is a bout decoding the trajectory of the school and
gathering the pearls that have been uncovered on the way. Wavelets are no longer
the central topic, despite the previous edition’s original title. It is just an important
tool, as the Fourier transform is. Sparse representation and processing are now at
the core.
In the 1980s,many researchers were focused on building time-frequency decom-
positions,trying to avoid the uncertainty barrier,and hoping to discover the ultimate
representation. Along the way came the construction of wavelet orthogonal bases,
which opened new perspectives through colla borations with physicists and math-
ematicians. Designing orthogonal bases with Xlets became a popular sport with
compression and noise-reduction applications. Connections with approximations
and sparsity also became more apparent. The search for sparsity has taken over,
leading to new grounds where orthonormal bases are replaced by redundant dictio-
naries of waveforms.
During these last seven years, I also encountered the industrial world. With
a lot of naiveness, some bandlets, and more mathematics, I cofounded a start-up
with Christophe Bernard, Jérome Kalifa, and Erwan Le Pennec. It took us some
time to learn that in three months good engineering should produce robust algo-
rithms that operate in real time, as opposed to the three years we were used
to having for writing new ideas with promising perspectives. Yet, we survived
because mathematics is a major source of industrial innovations for signal process-
ing. Semiconductor technology offers amazing computational power and flexibility.
However, ad hoc algorithms often do not scale easily and mathematics accelerates
the trial-and-error development process. Sparsity decreases computations,memor y,
and data communications. Although it brings beauty, mathematical understanding
is not a luxury. It is required by increasingly sophisticated information-processing
devices.
New Additions
Putting sparsity at the center of the book implied rewriting many parts and
adding sections. Chapters 12 and 13 are new. They introduce sparse represen-
tations in redundant dictionaries, and inverse problems, super-resolution, and
xv
xvi Preface to the Sparse Edition
compressive sensing. Here is a small catalog of new elements in this third
edition:
■ Radon transform and tomography
■ Lifting for wavelets on surfaces, bounded domains, and fast computations
■ JPEG-2000 image compression
■ Block thresholding for denoising
■ Geometric representations with adaptive triangulations, curvelets, and
bandlets
■ Sparse approximations in redundant dictionaries with pursuit algorithms
■ Noise reduction with model selection in redundant dictionaries
■ Exact recovery of sparse approximation suppor ts in dictionaries
■ Multichannel signal representations and processing
■ Dictionary learning
■ Inverse problems and super-resolution
■ Compressive sensing
■ Source separation
Teaching
This book is intended as a graduate-level textbook. Its evolution is also the result
of teaching courses in electrical engineering and applied mathematics. A new
website provides software for reproducible experimentations, exercise solutions,
together with teaching material such as slides with figures and MATLAB software
for numerical classes of http://wavelet-tour.com.
More exercises have been added at the end of each chapter, ordered by level
of difficulty. Level
1
exercises are direct applications of the course. Level
2
exercises
requires more thinking. Level
3
includes some technical der ivation exercises. Level
4
are projects at the interface of research that are possible topics for a final course
project or independent study. More exercises and projects can be found in the
website.
Sparse Course Programs
The Fourier transform and analog-to-digital conversion through linear sampling
approximations provide a common ground for all courses (Chapters 2 and 3).
It introduces basic signal representations and reviews important mathematical
and algorithmic tools needed afterward. Many trajectories are then possible to
explore and teach sparse signal processing. The following list notes several top-
ics that can orient a course’s structure with elements that can be covered along
the way.