Emmanuel J. Candès

Stanford University

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Trends

Author Order

Document Type

Co-Authors

Rina Foygel Barber

University of Chicago

Chiara Sabatti

Stanford University

Matteo Sesia

Ludwig-Maximilians-Universität München

David L. Donoho

Stanford University

Ryan J. Tibshirani

Carnegie Mellon University

Weijie Su

California University of Pennsylvania

Aaditya Ramdas

Carnegie Mellon University

Terence Tao

University of California, Los Angeles

Małgorzata Bogdan

University of Wrocław

Stephen Bates

Massachusetts Institute of Technology

Cooperative Institutions

Stanford University

University of California, Berkeley

California Institute of Technology

Stanford Medicine

Harvard University

Centre National de la Recherche Scientifique

Palo Alto University

Georgia Institute of Technology

Massachusetts Institute of Technology

University of Southern California

Author Statistics

Papers

Citation

H-Index

i-10 index

Research Field

Compressive sampling

EMS Press eBooks (2007)

Emmanuel J. Candès

Conventional wisdom and common practice in acquisition and reconstruction of images from frequency data follow the basic principle of the Nyquist density sampling theory. This principle states that to reconstruct an image, the number of Fourier samples we need to acquire must match the desired resolution of the image, i.e. the number of pixels in the image. This paper surveys an emerging theory which goes by the name of “compressive sampling” or “compressed sensing,” and which says that this conventional wisdom is inaccurate. Perhaps surprisingly, it is possible to reconstruct images or signals of scientiﬁc interest accurately and sometimes even exactly from a number of samples which is far smaller than the desired resolution of the image/signal, e.g. the number of pixels in the image. It is believed that compressive sampling has far reaching implications. For example, it suggests the possibility of new data acquisition protocols that translate analog information into digital form with fewer sensors than what was considered necessary. This new sampling theory may come to underlie procedures for sampling and compressing data simultaneously. In this short survey, we provide some of the key mathematical insights underlying this new theory, and explain some of the interactions between compressive sampling and other ﬁelds such as statistics, information theory, coding theory, and theoretical computer science.

Nyquist–Shannon sampling theorem

Sampling theory

Information Theory

10.4171/022-3/69

Cite

Citations (544)

Conformal Prediction With Conditional Guarantees

arXiv (Cornell University) (2023)

Isaac Gibbs John J. Cherian Emmanuel J. Candès

We consider the problem of constructing distribution-free prediction sets with finite-sample conditional guarantees. Prior work has shown that it is impossible to provide exact conditional coverage universally in finite samples. Thus, most popular methods only provide marginal coverage over the covariates. This paper bridges this gap by defining a spectrum of problems that interpolate between marginal and conditional validity. We motivate these problems by reformulating conditional coverage as coverage over a class of covariate shifts. When the target class of shifts is finite dimensional, we show how to simultaneously obtain exact finite sample coverage over all possible shifts. For example, given a collection of protected subgroups, our algorithm outputs intervals with exact coverage over each group. For more flexible, infinite dimensional classes where exact coverage is impossible, we provide a simple procedure for quantifying the gap between the coverage of our algorithm and the target level. Moreover, by tuning a single hyperparameter, we allow the practitioner to control the size of this gap across shifts of interest. Our methods can be easily incorporated into existing split conformal inference pipelines, and thus can be used to quantify the uncertainty of modern black-box algorithms without distributional assumptions.

Conditional probability distribution

Hyperparameter

10.48550/arxiv.2305.12616

Cite

Citations (9)

A Power and Prediction Analysis for Knockoffs with Lasso Statistics

arXiv (Cornell University) (2017)

Asaf Weinstein Rina Foygel Barber Emmanuel J. Candès

Knockoffs is a new framework for controlling the false discovery rate (FDR) in multiple hypothesis testing problems involving complex statistical models. While there has been great emphasis on Type-I error control, Type-II errors have been far less studied. In this paper we analyze the false negative rate or, equivalently, the power of a knockoff procedure associated with the Lasso solution path under an i.i.d. Gaussian design, and find that knockoffs asymptotically achieve close to optimal power with respect to an omniscient oracle. Furthermore, we demonstrate that for sparse signals, performing model selection via knockoff filtering achieves nearly ideal prediction errors as compared to a Lasso oracle equipped with full knowledge of the distribution of the unknown regression coefficients. The i.i.d. Gaussian design is adopted to leverage results concerning the empirical distribution of the Lasso estimates, which makes power calculation possible for both knockoff and oracle procedures.

Lasso

False Discovery Rate

Leverage (statistics)

10.48550/arxiv.1712.06465

Cite

Citations (13)

Interpretable Classification of Bacterial Raman Spectra With Knockoff Wavelets

IEEE Journal of Biomedical and Health Informatics (2021)

Charmaine Chia Matteo Sesia Chi-Sing Ho Stefanie S. Jeffrey Jennifer A. Dionne

Deep neural networks and other sophisticated machine learning models are widely applied to biomedical signal data because they can detect complex patterns and compute accurate predictions. However, the difficulty of interpreting such models is a limitation, especially for applications involving high-stakes decision, including the identification of bacterial infections. In this paper, we consider fast Raman spectroscopy data and demonstrate that a logistic regression model with carefully selected features achieves accuracy comparable to that of neural networks, while being much simpler and more transparent. Our analysis leverages wavelet features with intuitive chemical interpretations, and performs controlled variable selection with knockoffs to ensure the predictors are relevant and non-redundant. Although we focus on a particular data set, the proposed approach is broadly applicable to other types of signal data for which interpretability may be important.

Interpretability

Identification

Data set

10.1109/jbhi.2021.3094873

Cite

Citations (9)

A Nonuniform Sampler for Wideband Spectrally-Sparse Environments

IEEE Journal on Emerging and Selected Topics in Circuits and Systems (2012)

Michael B. Wakin Stephen Becker Eric Nakamura Michael C. Grant E.A. Sovero

We present a wide bandwidth, compressed sensing based nonuniform sampling (NUS) system with a custom sample-and-hold chip designed to take advantage of a low average sampling rate. By sampling signals nonuniformly, the average sample rate can be more than a magnitude lower than the Nyquist rate, provided that these signals have a relatively low information content as measured by the sparsity of their spectrum. The hardware design combines a wideband Indium-Phosphide heterojunction bipolar transistor sample-and-hold with a commercial off-the-shelf analog-to-digital converter to digitize an 800 MHz to 2 GHz band (having 100 MHz of noncontiguous spectral content) at an average sample rate of 236 Ms/s. Signal reconstruction is performed via a nonlinear compressed sensing algorithm, and the challenges of developing an efficient implementation are discussed. The NUS system is a general purpose digital receiver. As an example of its real signal capabilities, measured bit-error-rate data for a GSM channel is presented, and comparisons to a conventional wideband 4.4 Gs/s ADC are made.

Wideband

Nyquist rate

Analog-to-digital converter

10.1109/jetcas.2012.2214635

Cite

Citations (130)

Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

IEEE Transactions on Information Theory (2006)

Emmanuel J. Candès Justin Romberg Terence Tao

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.

Signal reconstruction

10.1109/tit.2005.862083

Cite

Citations (15,453)

Simple Bounds for Low-complexity Model Reconstruction

Emmanuel J. Candès Benjamin Recht

Source

Cite

Citations (18)

JMM 2019 Lecture Sampler

Notices of the American Mathematical Society (2018)

Jesús A. De Loera Amanda Folsom Emmanuel J. Candès Edray Herber Goins Bryna Kra

10.1090/noti1783

Cite

Citations (0)

PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

arXiv (Cornell University) (2011)

Emmanuel J. Candès Thomas Strohmer Vladislav Voroninski

Suppose we wish to recover a signal x in C^n from m intensity measurements of the form | |^2, i = 1, 2,..., m; that is, from data in which phase information is missing. We prove that if the vectors z_i are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program---a trace-norm minimization problem; this holds with large probability provided that m is on the order of n log n, and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis a vis additive noise.

Semidefinite Programming

Unit sphere

SIGNAL (programming language)

Minification

Source

Cite

Citations (29)

NESTA: A Fast and Accurate First-Order Method for Sparse Recovery

SIAM Journal on Imaging Sciences (2011)

Stephen Becker J. Bobin Emmanuel J. Candès

Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. Inspired by recent breakthroughs in the development of novel first-order methods in convex optimization, most notably Nesterov's smoothing technique, this paper introduces a fast and accurate algorithm for solving common recovery problems in signal processing. In the spirit of Nesterov's work, one of the key ideas of this algorithm is a subtle averaging of sequences of iterates, which has been shown to improve the convergence properties of standard gradient-descent algorithms. This paper demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as 1) it is computationally efficient, 2) it is accurate and returns solutions with several correct digits, 3) it is flexible and amenable to many kinds of reconstruction problems, and 4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization, and convex programs seeking to minimize the l1 norm of Wx under constraints, in which W is not diagonal.

Smoothing

Code (set theory)

Minification

10.1137/090756855

Cite

Citations (954)