Basis pursuit denoising / Lasso¶

Basis pursuit denoising (BPDN) seeks the solution to the problem

\[\min_x \frac{1}{2} \| b - A x \|_2^2 + \lambda \| x \|_1,\]

which, for a particular value of \(\lambda\), is equivalent to the Least absolute shrinkage and selection operator (Lasso).

Real instances of the problem are expressable as a Quadratic Program by decomposing \(x\) into its positive and negative parts, say \(x = u - v\), and posing the problem

\[\begin{split}\min_{u,v,r} \{\; \frac{1}{2} r^T r + \lambda^T \begin{pmatrix} u \\ v \end{pmatrix} \; | \; \begin{pmatrix} A & -A \end{pmatrix} \begin{pmatrix} u \\ v \end{pmatrix} + r = b \; \wedge \; \begin{pmatrix} u \\ v \end{pmatrix} \ge 0 \; \}.\end{split}\]

By default, Elemental solves this quadratic program via a Mehrotra Predictor-Corrector primal-dual Interior Point Method.

Python API¶

BPDN(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 – penalty on the one-norm of the solution vector
ctrl – (optional) BPDNCtrl_s or BPDNCtrl_d instance, depending upon whether the data is single-precision or double-precision

Return type

dense solution vector (with type matching that of b)

C++ API¶

void BPDN(const Matrix<Real> &A, const Matrix<Real> &b, Real lambda, Matrix<Real> &x, const BPDNCtrl<Real> &ctrl = BPDNCtrl<Real>())¶

void BPDN(const ElementalMatrix<Real> &A, const ElementalMatrix<Real> &b, Real lambda, ElementalMatrix<Real> &x, const BPDNCtrl<Real> &ctrl = BPDNCtrl<Real>())¶

void BPDN(const SparseMatrix<Real> &A, const Matrix<Real> &b, Real lambda, Matrix<Real> &x, const BPDNCtrl<Real> &ctrl = BPDNCtrl<Real>())¶

void BPDN(const DistSparseMatrix<Real> &A, const DistMultiVec<Real> &b, Real lambda, DistMultiVec<Real> &x, const BPDNCtrl<Real> &ctrl = BPDNCtrl<Real>())¶

C API¶

Single-precision¶

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

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

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

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

Double-precision¶

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

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

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

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

Expert interface¶

Single-precision¶

ElError ElBPDNX_s(ElConstMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x, ElBPDNCtrl_s ctrl)¶

ElError ElBPDNXDist_s(ElConstDistMatrix_s A, ElConstDistMatrix_s b, float lambda, ElDistMatrix_s x, ElBPDNCtrl_s ctrl)¶

ElError ElBPDNXSparse_s(ElConstSparseMatrix_s A, ElConstMatrix_s b, float lambda, ElMatrix_s x, ElBPDNCtrl_s ctrl)¶

ElError ElBPDNXDistSparse_s(ElConstDistSparseMatrix_s A, ElConstDistMultiVec_s b, float lambda, ElDistMultiVec_s x, ElBPDNCtrl_s ctrl)¶

Double-precision¶

ElError ElBPDNX_d(ElConstMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x, ElBPDNCtrl_d ctrl)¶

ElError ElBPDNXDist_d(ElConstDistMatrix_d A, ElConstDistMatrix_d b, double lambda, ElDistMatrix_d x, ElBPDNCtrl_d ctrl)¶

ElError ElBPDNXSparse_d(ElConstSparseMatrix_d A, ElConstMatrix_d b, double lambda, ElMatrix_d x, ElBPDNCtrl_d ctrl)¶

ElError ElBPDNXDistSparse_d(ElConstDistSparseMatrix_d A, ElConstDistMultiVec_d b, double lambda, ElDistMultiVec_d x, ElBPDNCtrl_d ctrl)¶