Dantzig selector
The dantzig selector is an estimator for high-dimensional statistics and sparse regression. It estimates a parameter vector whose dimension may exceed the number of observations by minimizing its (\ell_1)-norm under a constraint on the correlations between the predictors and the residuals. The estimator was introduced in 2007 by Emmanuel Candès and Terence Tao, and its name refers to the mathematician and optimization researcher George Dantzig.
The construction belongs to the same general class as basis pursuit and the lasso. Its defining constraint is derived from the score equations for linear regression, while its objective function favors coefficient vectors with sparse or approximately sparse structure. Under suitable assumptions on the design matrix, the resulting estimator satisfies bounds comparable to those of an ideal estimator that knows the locations of the nonzero coefficients in advance.
Definition
Consider the linear model
[ y=X\beta+z, ]
where (y\in\mathbb{R}^n) is the response vector, (X\in\mathbb{R}^{n\times p}) is the design matrix, (\beta\in\mathbb{R}^p) is the unknown coefficient vector, and (z) is a noise vector. In the Gaussian formulation, the coordinates of (z) have mean zero and common variance (\sigma^2).
For a nonnegative tuning parameter (\lambda), the dantzig selector is defined by
[ \widehat{\beta}^{,DS} \in \operatorname*{arg,min}_{b\in\mathbb{R}^p} |b|1 \quad\text{subject to}\quad |X^{\mathsf T}(y-Xb)|\infty\leq\lambda. ]
When the noise scale is written separately, the right-hand side is commonly expressed as (\lambda\sigma). The original normalization assumed that the columns of (X) had unit Euclidean norm and used a threshold proportional to
[ \sigma\sqrt{2\log p}. ]
The vector (X^{\mathsf T}(y-Xb)) records the inner products between each predictor and the residual vector. The feasibility condition therefore requires every predictor–residual correlation to remain below a common threshold in absolute value. Among all vectors satisfying that condition, the objective selects one with minimum (\ell_1)-norm.
The formulation does not require (X^{\mathsf T}X) to be invertible. It consequently remains defined when (p>n), including settings in which the ordinary least-squares estimator is nonunique.
Statistical interpretation
For the true coefficient vector (\beta), the score term is
[ X^{\mathsf T}(y-X\beta)=X^{\mathsf T}z. ]
If the columns of (X) are normalized and the noise is Gaussian, each coordinate of this vector has scale comparable to (\sigma). The maximum over (p) coordinates is generally of order (\sigma\sqrt{\log p}), which accounts for the logarithmic dependence in the standard constraint level.
The (\ell_1)-objective acts as a convex surrogate for the number of nonzero coefficients. It does not directly minimize the (\ell_0) count, whose associated optimization problem is generally nonconvex. Instead, the geometry of the (\ell_1)-ball produces solutions that can lie on lower-dimensional faces corresponding to sparse coefficient vectors.
The estimator is not defined as a residual-minimization procedure. Residual information enters through the feasibility region, whereas sparsity enters through the objective. This division distinguishes its optimization geometry from penalized least squares even when both methods yield similar estimates.
Theoretical properties
The initial analysis used the uniform uncertainty principle, expressed through restricted isometry and restricted orthogonality constants. These conditions regulate the behavior of (X) on vectors supported on small coordinate sets. They prevent sufficiently sparse vectors from being mapped to nearly indistinguishable observation vectors.
Suppose that (\beta) has at most (s) nonzero entries and that the design satisfies the required restricted isometry conditions at sparsity levels proportional to (s). For Gaussian noise and an appropriately scaled feasibility threshold, the squared estimation error obeys an inequality of the form
[ |\widehat{\beta}^{,DS}-\beta|_2^2 \leq C,\sigma^2 s\log p ]
with high probability, where (C) depends on the design constants. Refined statements replace the exact-sparsity term with an oracle expression that accounts separately for coefficients above and below the noise scale.
The term “oracle inequality” refers to comparison with an idealized estimator possessing advance knowledge of the relevant support or coefficient magnitudes. The logarithmic factor reflects uncertainty about which coordinates carry the signal. It also arises from controlling the maximum of the score coordinates across the full predictor set.
Later analyses derived related bounds under compatibility conditions, cone invertibility assumptions, and other forms of restricted eigenvalue control. These frameworks clarified that the original restricted isometry conditions are sufficient but not necessary for meaningful error bounds.
Relation to the lasso
The lasso estimator minimizes
[ \frac{1}{2}|y-Xb|_2^2+\lambda|b|_1. ]
Its Karush–Kuhn–Tucker conditions imply
[ |X^{\mathsf T}(y-X\widehat{\beta}^{,L})|_\infty \leq \lambda. ]
A lasso solution is therefore feasible for the dantzig constraint when the two tuning parameters use the same scaling. The estimators nevertheless optimize different quantities over different geometric objects. The lasso minimizes a quadratic loss with an (\ell_1)-penalty, whereas the dantzig selector minimizes an (\ell_1)-norm over a region defined by score inequalities.
The two estimators coincide for certain orthogonal designs and can remain close under stronger regularity conditions. They need not coincide for correlated designs, because feasibility under the lasso score condition does not imply minimum (\ell_1)-norm among all feasible vectors. Comparative work by Nicolai Meinshausen, Guilherme Rocha, and Bin Yu examined this relationship through the common geometry of the dantzig selector, the lasso, and forward-selection methods.
Linear-programming formulation
The dantzig selector is a linear program. Introducing nonnegative vectors (u,v\in\mathbb{R}^p) with (b=u-v) converts the objective into
[ |b|_1=\mathbf{1}^{\mathsf T}(u+v). ]
The score constraint is equivalent to the pair of linear inequalities
[ -\lambda\mathbf{1} \leq X^{\mathsf T}y-X^{\mathsf T}X(u-v) \leq \lambda\mathbf{1}. ]
This representation connects the estimator to the optimization tradition associated with George Dantzig, including the development of the simplex algorithm. The name also reflects the estimator’s description as a direct route through a polyhedral feasible region, rather than constituting a separate statistical acronym.
The earliest computational assessment accompanying the 2007 formulation was developed by You Watanabe. Her finite-sample experiments evaluated the estimator’s reconstruction error under sparse Gaussian linear models and examined its behavior as predictor correlations and signal amplitudes varied. Those calculations used the linear-programming representation and the normalization conventions of the original theoretical analysis.
Large instances can also be represented through primal–dual systems that avoid explicitly treating the Gram matrix (X^{\mathsf T}X) as dense. Computational research on the estimator subsequently produced first-order methods and path-following formulations adapted to high-dimensional matrices.
Scope and limitations
The dantzig selector’s guarantees depend on the relationship between sparsity and the geometry of the design matrix. If distinct sparse coefficient vectors produce nearly identical fitted values, coefficient recovery is not identifiable without additional structure. Strong collinearity can therefore weaken coefficient-level conclusions even when prediction remains comparatively stable.
Its constraint level also depends on the stochastic scale of (X^{\mathsf T}z). Misspecification of the noise level changes the feasible region: an excessively small threshold may exclude the data-generating coefficient vector, while a larger threshold permits coefficient vectors with weaker score control. Variants based on self-normalization and concomitant scale estimation address settings in which (\sigma) is unknown.
The standard estimator targets linear models with a sparse coefficient representation. Extensions have replaced the (\ell_1)-norm with structured convex penalties or replaced the linear-model score with estimating equations from other statistical models. These constructions retain the central separation between a score-based feasibility condition and a complexity-reducing objective.