Compressed Sensing
Compressed sensing is an exciting, rapidly growing field which has attracted consid-
erable attention in electrical engineering, applied mathematics, statistics, and computer
science. Since its initial introduction several years ago an avalanche of results have
been obtained both of a theoretical as well as practical nature, and various conferences,
workshops, and special sessions have been dedicated to this growing research field. This
book provides the first detailed introduction to the subject, highlighting recent theoretical
advances and a range of applications, as well as outlining numerous remaining research
challenges. After a thorough review of the basic theory, many cutting-edge advances
in the field are presented, including advanced signal modeling, sub-Nyquist sampling
of analog signals, hardware prototypes, non-asymptotic analysis of random matrices,
adaptive sensing, greedy algorithms, the use of graphical models, and the separation of
morphologically distinct data components. Each chapter is written by leading researchers
in the field, and consistent style and notation are utilized throughout. An extended intro-
ductory chapter summarizes the basics of the field so that no prior knowledge is required.
Key background information and clear definitions make this book an ideal resource for
researchers, graduate students, and practitioners wanting to join this exciting research
area. It can also serve as a supplementary textbook for courses on computer vision,
coding theory, signal processing, image processing, and algorithms for efficient data
processing.
Yonina C. Eldar is a Professor in the Department of Electrical Engineering at the Tech-
nion, Israel Institute of Technology, a Research Affiliate with the Research Laboratory
of Electronics at the Massachusetts Institute of Technology, and a Visiting Professor
at Stanford University. She has received numerous awards for excellence in research
and teaching, including the Wolf Foundation Krill Prize for Excellence in Scientific
Research, the Hershel Rich Innovation Award, the Weizmann Prize for Exact Sciences,
the Michael Bruno Memorial Award from the Rothschild Foundation, and the Muriel &
David Jacknow Award for Excellence in Teaching. She is an Associate Editor for sev-
eral journals in the areas of signal processing and mathematics and a Signal Processing
Society Distinguished Lecturer.
Gitta Kutyniok is an Einstein Professor in the Department of Mathematics at the Tech-
nische Universität Berlin, Germany. She has been a Postdoctoral Fellow at Princeton,
Stanford, and Yale Universities, and a Full Professor at the Universität Osnabrück,
Germany. Her research and teaching have been recognized by various awards, including
a Heisenberg Fellowship and the von Kaven Prize by the German Research Founda-
tion, an Einstein Chair by the Einstein Foundation Berlin, awards by the Universität
Paderborn and the Justus–Liebig Universität Gießen for Excellence in Research, as well
as the Weierstraß Prize for Outstanding Teaching. She is an Associate Editor and also
Corresponding Editor for several journals in the area of applied mathematics.
Compressed Sensing
Theory and Applications
Edited by
YONINA C. ELDAR
Technion-Israel Institute of Technology, Haifa, Israel
GITTA KUTYNIOK
Technische Universität Berlin, Germany
cambridge university press
Cambridge, New York, Melbourne, Madrid, Cape Town,
Singapore, São Paulo, Delhi, Mexico City
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9781107005587
© Cambridge University Press 2012
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First published 2012
Reprinted 2012
Printed and bound in the United Kingdom by the MPG Books Group
A catalogue record for this publication is available from the British Library
Library of Congress Cataloguing in Publication data
Compressed sensing : theory and applications / edited by Yonina C. Eldar, Gitta Kutyniok.
p.
cm.
Includes bibliographical references and index.
ISBN 978-1-107-00558-7
1. Signal processing.
QA601.C638 2012
621.382
2011040519
2–dc23
2. Wavelets (Mathematics)
I. Eldar, Yonina C.
II. Kutyniok, Gitta.
ISBN 978-1-107-00558-7 Hardback
Cambridge University Press has no responsibility for the persistence or
accuracy of URLs for external or third-party internet websites referred to
in this publication, and does not guarantee that any content on such
websites is, or will remain, accurate or appropriate.
Contents
List of contributors
Preface
Introduction to compressed sensing
MARK A. DAVENPORT, MARCO F. DUARTE, YONINA C. ELDAR,
AND GITTA KUTYNIOK
Second-generation sparse modeling: structured and
collaborative signal analysis
ALEXEY CASTRODAD,
PABLO SPRECHMANN, AND GUOSHEN YU
IGNACIO RAMIREZ, GUILLERMO SAPIRO,
Xampling: compressed sensing of analog signals
MOSHE MISHALI AND YONINA C. ELDAR
Sampling at the rate of innovation: theory and applications
JOSE ANTONIO URIGÜEN, YONINA C. ELDAR, PIER LUIGI DRAGOTTI,
AND ZVIKA BEN-HAIM
Introduction to the non-asymptotic analysis of random matrices
ROMAN VERSHYNIN
Adaptive sensing for sparse recovery
JARVIS HAUPT AND ROBERT NOWAK
Fundamental thresholds in compressed sensing:
a high-dimensional geometry approach
WEIYU XU AND BABAK HASSIBI
Greedy algorithms for compressed sensing
THOMAS BLUMENSATH, MICHAEL E. DAVIES, AND GABRIEL RILLING
1
2
3
4
5
6
7
8
page vii
ix
1
65
88
148
210
269
305
348
vi
9
10
11
12
Contents
Graphical models concepts in compressed sensing
ANDREA MONTANARI
Finding needles in compressed haystacks
ROBERT CALDERBANK AND SINA JAFARPOUR
Data separation by sparse representations
GITTA KUTYNIOK
Face recognition by sparse representation
ARVIND GANESH, ANDREW WAGNER, ZIHAN ZHOU, ALLEN Y. YANG, YI MA,
AND JOHN WRIGHT
Index
394
439
485
515
540