Basis pursuit

The minimization problem

\[\min_z \| z \|_1 \text{ such that } A z = b,\]

is referred to as basis pursuit and is well-known to promote sparse solutions.

The following functions were inspired by a simple basis pursuit ADMM implementation due to Boyd et al. Elemental’s implementations use parallel (dense) linear algebra and allows the user to choose between either directly computing a (thresholded-)pseudoinverse or an LQ factorization. The return value is the number of performed ADMM iterations.

C++ API

Int BasisPursuit(const Matrix<F> &A, const Matrix<F> &b, Matrix<F> &z, Base<F> rho = 1, Base<F> alpha = 1.2, Int maxIter = 500, Base<F> absTol = 1e-6, Base<F> relTol = 1e-4, bool usePinv = false, Base<F> pinvTol = 0, bool progress = true)

Int BasisPursuit(const AbstractDistMatrix<F> &A, const AbstractDistMatrix<F> &b, AbstractDistMatrix<F> &z, Base<F> rho = 1, Base<F> alpha = 1.2, Int maxIter = 500, Base<F> absTol = 1e-6, Base<F> relTol = 1e-4, bool usePinv = false, Base<F> pinvTol = 0, bool progress = true)

Implementation

Example driver

Parameters	Input/Output	Explanation
A	Input	part of constraint \(Ax=b\)
b	Input	part of constraint \(Ax=b\)
z	Output	primal solution (second term)
rho	Input	augmented-Lagrangian parameter
alpha	Input	over-relaxation parameter (usually in \([1,1.8]\))
maxIter	Input	maximum number of ADMM iterations
absTol	Input	absolute convergence tolerance
relTol	Input	relative convergence tolerance
usePinv	Input	directly compute a pseudoinverse?
pinvTol	Input	the pseudoinverse inversion tolerance
progress	Input	display detailed progress information?

C API

ElError ElBasisPursuit_s(ElConstMatrix_s A, ElConstMatrix_s b, ElMatrix_s z, ElInt* numIts)

ElError ElBasisPursuit_d(ElConstMatrix_d A, ElConstMatrix_d b, ElMatrix_d z, ElInt* numIts)

ElError ElBasisPursuit_c(ElConstMatrix_c A, ElConstMatrix_c b, ElMatrix_c z, ElInt* numIts)

ElError ElBasisPursuit_z(ElConstMatrix_z A, ElConstMatrix_z b, ElMatrix_z z, ElInt* numIts)

ElError ElBasisPursuitDist_s(ElConstMatrix_s A, ElConstMatrix_s b, ElMatrix_s z, ElInt* numIts)

ElError ElBasisPursuitDist_d(ElConstMatrix_d A, ElConstMatrix_d b, ElMatrix_d z, ElInt* numIts)

ElError ElBasisPursuitDist_c(ElConstMatrix_c A, ElConstMatrix_c b, ElMatrix_c z, ElInt* numIts)

ElError ElBasisPursuitDist_z(ElConstMatrix_z A, ElConstMatrix_z b, ElMatrix_z z, ElInt* numIts)

TODO: Expert versions