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

2005/06/05 by Emmanuel J. Candès, Emmanuel Candes, Terence Tao +2 · 183 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Combinatorics #Estimator #Geometry #Mathematics #Quantum Information and Cryptography #Quantum Mechanics and Applications #Random Matrices and Applications #Scalar (mathematics) #Sparse and Compressive Sensing Techniques #Statistical Mechanics and Entropy #Statistical Methods and Inference #Statistics #math.ST #msc:62C05 #msc:62G05 #msc:94A08 #msc:94A12 #stat.TH

paper · pdf · doi:10.1214/009053606000001523

published in The Annals of Statistics 35(6), 83-84 (Institute of Mathematical Statistics) · This paper discussed in: [arXiv:0803.3124], [arXiv:0803.3126], [arXiv:0803.3127], [arXiv:0803.3130], [arXiv:0803.3134], [arXiv:0803.3135]. Rejoinder in [arXiv:0803.3136]. Published in at http://dx.doi.org/10.1214/009053606000001523 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

openalex publication_date 2007/12/01 · arxiv created 2008/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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? To estimate β, we introduce a new estimator—we call it the Dantzig selector—which is a solution to the ℓ1-regularization problem min_β\inR^p‖β‖_ℓ₁\quadsubject to ‖X^*r‖_ℓ_∞≤(1+t^-1)√(2log p)⋅σ, where r is the residual vector y−Xβ̃ and t is a positive scalar. We show that if X obeys a uniform uncertainty principle (with unit-normed columns) and if the true parameter vector β is sufficiently sparse (which here roughly guarantees that the model is identifiable), then with very large probability, ‖β̂−β‖ℓ22≤C2⋅2log p⋅(σ2+∑imin(βi2, σ2)). Our results are nonasymptotic and we give values for the constant C. Even though n may be much smaller than p, our estimator achieves a loss within a logarithmic factor of the ideal mean squared error one would achieve with an oracle which would supply perfect information about which coordinates are nonzero, and which were above the noise level. In multivariate regression and from a model selection viewpoint, our result says that it is possible nearly to select the best subset of variables by solving a very simple convex program, which, in fact, can easily be recast as a convenient linear program (LP).

Citations

• Ideal spatial adaptation by wavelet shrinkage
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Discussion: The Dantzig selector: Statistical estimation when p is much larger than n
• Discussion: The Dantzig selector: Statistical estimation when p is much larger than n
• Discussion: The Dantzig selector: Statistical estimation when p is much larger than n
• Discussion: The Dantzig selector: statistical estimation when p is much larger than n
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• Discussion: The Dantzig selector: Statistical estimation when p is much larger than n
• Rejoinder: The Dantzig selector: Statistical estimation when p is much larger than n

Cited by

• Debiased Inference for High-Dimensional Regression Models Based on Profile M-Estimation
• Sparse Linear Regression is Easy on Random Supports
• Constructing Large Orthogonal Minimally Aliased Response Surface Designs by Concatenating Two Definitive Screening Designs
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
• An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
• Optimal RIP bounds for sparse signals recovery via ℓ minimization
• Sparse estimation for the drift of high-dimensional Ornstein--Uhlenbeck processes with i.i.d. paths
• A novel predefined-time neurodynamic approach for mixed variational inequality problems and applications
• Optimality and computational barriers in variable selection under dependence
• Closed-form ℓ_r norm scaling with data for overparameterized linear regression and diagonal linear networks under ℓ_p bias
• An adaptive subsampling method for large-sample feature screening
• SSNCVX: A primal-dual semismooth Newton method for convex composite optimization problem
• Quantifying and testing dependence to categorical variables
• Functional Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
• Generalisation and benign over-fitting for linear regression onto random functional covariates
• High-dimensional Longitudinal Inference via a De-sparsified Dantzig-Selector
• Lasso Penalization for High-Dimensional Beta Regression Models: Computation, Analysis, and Inference
• Guidelines for LASSO and derivatives use under different dependence and scale structures
• CoMMiT: Co-informed inference of microbiome-metabolome interactions via transfer learning
• Knockoff-Guided Compressive Sensing: A Statistical Machine Learning Framework for Support-Assured Signal Recovery
• A note on the improved sparse Hanson-Wright inequalities
• A new measure of dependence: Integrated R²
• From L-domination maximal inequalities to infinite-dimensional martingales, towards high-dimensional statistics
• On the conditions used to prove oracle results for the Lasso
• Reconstruction of Multidimensional Signals From Irregular Noisy Samples
• Debiasing the Lasso under Weaker Tail Assumptions
• Variational Multiscale Nonparametric Regression: Algorithms and Implementation
• Spatial Sign based Direct Sparse Linear Discriminant Analysis for High Dimensional Data

Related

• Parallelism, Uniqueness, and Large-Sample Asymptotics for the Dantzig Selector
• Simultaneous analysis of Lasso and Dantzig selector
• Generalized Dantzig Selector: Application to the k-support norm
• Thresholded Lasso for high dimensional variable selection and statistical estimation
• Thresholded Lasso for high dimensional variable selection