The Dantzig selector: Statistical estimation when P is much larger than n

By E.J. Candes, Terence Tao. 2005

3,737 citations recorded by the source corpus.

In many important statistical applications, the number of variables or parameters p is much larger than the number of observations n. Suppose then that we have observations y=Xβ+z, where β∈Rp is a parameter vector of interest, X is a data matrix with possibly far fewer rows than columns, n≪p, and the zi’s are i.i.d. N(0, σ^2). Is it possible to estimate β reliably based on the noisy data y?

Subfields: Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Analysis of a Random Forests Model (2010, background): “For example, if S = 1 and d = 25, (d/S) − 1 = 24 and, as there are 2524 such partial derivatives in R25, we note immediately the potential benefit of recovering the “true” dimension S. Remark 2 The reduced-dimensional rate n −0.75 S log 2+0.75 is strictly larger than the S-dimensional optimal rate n”
Sparse Partially Linear Additive Models (2014, background): “…such results (and others of its kind) make potentially strong (and unverifiable) assumptions on the design matrix (e.g., the restricted isometry property, Candes and Tao 2007; the compatibility condition, Bühlmann and van de Geer 2011; van de Geer 2007; small coherence, Candès and Plan 2009, etc.”
Double/De-Biased Machine Learning of Global and Local Parameters Using Regularized Riesz Representers (2018, methodology): “Estimation will be carried out using the following Dantzig selector-type estimators (Candes and Tao (2007)).”
Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, neutral): “Many other sparse estimators for regression could be considered, for example, `1-penalized alternatives to the lasso, like the Dantzig selector (Candes and Tao, 2007) and square-root lasso (Belloni et al., 2011); greedy alternatives to forward stepwise algorithm, like matching pursuit (Mallat and…”
Regularization Paths for Generalized Linear Models via Coordinate Descent (2010, background): “The Dantzig selector (Candes and Tao 2007, and discussion), a slightly modiﬁed version of the lasso.”
A Singular Value Thresholding Algorithm for Matrix Completion (2008, methodology): “Inspired by the work on the Dantzig selector [18], which was originally developed for estimating sparse parameter vectors from noisy data, another approach is to set a constraint on the spectral norm of A∗(r)—recall that r is the residual vector b−A(X)—and solve”
Stability selection (2008, methodology): “We illustrate the results on the randomized lasso with a small simulation example: p=n=200 and the predictor variables are sampled from an N .0, Σ/ distribution, where Σ is the identity matrix, except for the entries Σ13 =Σ23 =ρ and their symmetrical counterparts.”
Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming (2010, neutral): “at the oracle knows the identity T of signiﬁcant regressors, and so it can achieve the rate of σ p s/n.) The result above was demonstrated by [2], and closely related results were given in [7], [19], [4], and [16]. [3], [20], [5], [6], and [18] contain other fundamental results obtained for related ”
Nearly unbiased variable selection under minimax concave penalty (2010, methodology): “However, while the Dantzig selector and LASSO have been found to perform similarly in simulation studies [Efron, Hastie and Tibshirani (2007), Meinshausen, Rocha and Yu (2007) and Candés and Tao (2007), page 2401], little is known about the selection consistency of the Dantzig selector.”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, background): “Accordingly, there have been various lines of work on high dimensional inference based on imposing different types of structure constraints such as sparsity and group sparsity [15] [5] [21].”
On asymptotically optimal confidence regions and tests for high-dimensional models (2013, background): “The vast majority of work has been pursued for point estimation such as consistency for prediction [21, 7], oracle inequalities and estimation of a high-dimensional parameter [12, 11, 50, 45, 33, 6, 34, 24] or variable selection [30, 53, 17, 48].”
High-dimensional additive modeling (2008, neutral): “5 | i − j | ; i, j = 1 , . . . , p .”
High-dimensional Ising model selection using ℓ1-regularized logistic regression (2010, background): “The Annals of Statistics 2010, Vol. 38, No. 3, 1287–1319 DOI: 10.1214/09-AOS691 © Institute of Mathematical Statistics, 2010 HIGH-DIMENSIONAL ISING MODEL SELECTION USING 1-REGULARIZED LOGISTIC REGRESSION”
On the conditions used to prove oracle results for the Lasso (2009, methodology): “Such oracle results have been derived by, among others, [4, 19, 21, 2, 16], and for the related Dantzig selector by [11] and [13].”
A Class of Three-Level Designs for Definitive Screening in the Presence of Second-Order Effects (2011, methodology): “We refer the reader to Hartley (1959), Westlake (1965), Draper (1985), Draper and Lin (1990), and Angelopoulos et al.”
Pivotal estimation via square-root Lasso in nonparametric regression (2011, background): “In particular, 1-penalization has played a central role [14, 15, 18, 35, 40, 47, 52, 54].”