Dantzig selector¶

The Dantzig selector (DS) attempts to balance the approximate satisfaction of a highly underdetermined system of equations with a sparsity-promoting \(\ell_1\) penalty on the solution using only linear programming:

\[\min_x \| x \|_1 \text{ such that } \| A^T (b - A x) \|_{\infty} \le \lambda.\]

In addition to the specific LP formulation in Candes and Tao’s original paper, Friedlander and Saunders proposed two mappings, (DS1):

\[\begin{split}\min_{u,v,t} \{\;1^T (u+v) \; | \; \begin{pmatrix} A^T A & -A^T A & I \end{pmatrix} \begin{pmatrix} u \\ v \\ t \end{pmatrix} = A^T b \; \wedge \; u,v \ge 0 \; \wedge \; \| t \|_{\infty} \le \lambda \;\}, \; \text{and}\end{split}\]

(DS2):

\[\begin{split}\min_{u,v,r,t} \{\; 1^T (u+v) \; | \; \begin{pmatrix} A & -A & I & 0 \\ 0 & 0 & A^T & I \end{pmatrix} \begin{pmatrix} u \\ v \\ r \\ t \end{pmatrix} = \begin{pmatrix} b \\ 0 \end{pmatrix} \; \wedge \; u,v \ge 0 \; \wedge \; \| t \|_{\infty} \le \lambda \;\},\end{split}\]

which they argued to be superior in performance and conditioning. Elemental defaults to (DS1) for dense matrices and (DS2) for sparse matrices and applies a Mehrotra Predictor-Corrector primal-dual Interior Point Method.

Python API¶

DS(A, b, lambd[, ctrl=None])¶

Parameters

A – dense or sparse, sequential or distributed matrix
b – dense right-hand side vector (with type compatible to A)
lambd – bound on the maximum absolute value of \(A^T (b-Ax)\)
ctrl – (optional) LPAffineCtrl instance

Return type

dense solution vector (with type matching that of b)

C++ API¶

void DS(const Matrix<Real> &A, const Matrix<Real> &b, Real lambda, Matrix<Real> &x, const lp::affine::Ctrl<Real> &ctrl = lp::affine::Ctrl<Real>())¶

void DS(const ElementalMatrix<Real> &A, const ElementalMatrix<Real> &b, Real lambda, ElementalMatrix<Real> &x, const lp::affine::Ctrl<Real> &ctrl = lp::affine::Ctrl<Real>())¶

void DS(const SparseMatrix<Real> &A, const Matrix<Real> &b, Real lambda, Matrix<Real> &x, const lp::affine::Ctrl<Real> &ctrl = lp::affine::Ctrl<Real>())¶

void DS(const DistSparseMatrix<Real> &A, const DistMultiVec<Real> &b, Real lambda, DistMultiVec<Real> &x, const lp::affine::Ctrl<Real> &ctrl = lp::affine::Ctrl<Real>())¶

C API¶

Single-precision¶

ElError ElDS_s(ElConstMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x)¶

ElError ElDSDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s b, float lambda, ElDistMatrix_s x)¶

ElError ElDSSparse_s(ElConstSparseMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x)¶

ElError ElDSDistSparse_s(ElConstDistSparseMatrix_s A, ElConstDistMultiVec_s b, float lambda, ElDistMultiVec_s x)¶

Double-precision¶

ElError ElDS_d(ElConstMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x)¶

ElError ElDSDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d b, double lambda, ElDistMatrix_d x)¶

ElError ElDSSparse_d(ElConstSparseMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x)¶

ElError ElDSDistSparse_d(ElConstDistSparseMatrix_d A, ElConstDistMultiVec_d b, double lambda, ElDistMultiVec_d x)¶

Expert interface¶

Single-precision¶

ElError ElDSX_s(ElConstMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x, ElLPAffineCtrl_s ctrl)¶

ElError ElDSXDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s b, float lambda, ElDistMatrix_s x, ElLPAffineCtrl_s ctrl)¶

ElError ElDSXSparse_s(ElConstSparseMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x, ElLPAffineCtrl_s ctrl)¶

ElError ElDSXDistSparse_s(ElConstDistSparseMatrix_s A, ElConstDistMultiVec_s b, float lambda, ElDistMultiVec_s x, ElLPAffineCtrl_s ctrl)¶

Double-precision¶

ElError ElDSX_d(ElConstMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x, ElLPAffineCtrl_d ctrl)¶

ElError ElDSXDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d b, double lambda, ElDistMatrix_d x, ElLPAffineCtrl_d ctrl)¶

ElError ElDSXSparse_d(ElConstSparseMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x, ElLPAffineCtrl_d ctrl)¶

ElError ElDSXDistSparse_d(ElConstDistSparseMatrix_d A, ElConstDistMultiVec_d b, double lambda, ElDistMultiVec_d x, ElLPAffineCtrl_d ctrl)¶