Total variation denoising

Total variation denoising (TV) seeks the solution to the problem

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

where \(b \in \mathbb{R}^n\) is the original (1D) signal and \(D : \mathbb{R}^n \rightarrow \mathbb{R}^{n-1}\) is the upper-bidiagonal difference operator which maps a vector \(x\) to

\[(D x)_i = x_i - x_{i+1}.\]

Real instances of the problem are expressable as a Quadratic Program, and Elemental follows the formulation used within CVXOPT:

\[\begin{split}& \min_{x,t} \frac{1}{2} \| x - b \|_2^2 + \lambda 1^T t \\ & \text{s.t. } -t \le D x \le t.\end{split}\]

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

Python API

TV(b, lambd[, ctrl=None])

C++ API

void TV(const Matrix<Real> &b, Real lambda, Matrix<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

void TV(const ElementalMatrix<Real> &b, Real lambda, ElementalMatrix<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

void TV(const DistMultiVec<Real> &b, Real lambda, DistMultiVec<Real> &x, const qp::affine::Ctrl<Real> &ctrl = qp::affine::Ctrl<Real>())

C API

Single-precision

ElError ElTV_s(ElConstMatrix_s b, float lambda, ElMatrix_s x)

ElError ElTVDist_s(ElConstDistMatrix_s b, float lambda, ElDistMatrix_s x)

ElError ElTVSparse_s(ElConstMatrix_s b, float lambda, ElMatrix_s x)

ElError ElTVDistSparse_s(ElConstDistMultiVec_s b, float lambda, ElDistMultiVec_s x)

Double-precision

ElError ElTV_d(ElConstMatrix_d b, double lambda, ElMatrix_d x)

ElError ElTVDist_d(ElConstDistMatrix_d b, double lambda, ElDistMatrix_d x)

ElError ElTVSparse_d(ElConstMatrix_d b, double lambda, ElMatrix_d x)

ElError ElTVDistSparse_d(ElConstDistMultiVec_d b, double lambda, ElDistMultiVec_d x)

Expert interface

Single-precision

ElError ElTVX_s(ElConstMatrix_s b, float lambda, ElMatrix_s x, ElQPAffineCtrl_s ctrl)

ElError ElTVXDist_s(ElConstDistMatrix_s b, float lambda, ElDistMatrix_s x, ElQPAffineCtrl_s ctrl)

ElError ElTVXSparse_s(ElConstMatrix_s b, float lambda, ElMatrix_s x, ElQPAffineCtrl_s ctrl)

ElError ElTVXDistSparse_s(ElConstDistMultiVec_s b, float lambda, ElDistMultiVec_s x, ElQPAffineCtrl_s ctrl)

Double-precision

ElError ElTVX_d(ElConstMatrix_d b, double lambda, ElMatrix_d x, ElQPAffineCtrl_d ctrl)

ElError ElTVXDist_d(ElConstDistMatrix_d b, double lambda, ElDistMatrix_d x, ElQPAffineCtrl_d ctrl)

ElError ElTVXSparse_d(ElConstMatrix_d b, double lambda, ElMatrix_d x, ElQPAffineCtrl_d ctrl)

ElError ElTVXDistSparse_d(ElConstDistMultiVec_d b, double lambda, ElDistMultiVec_d x, ElQPAffineCtrl_d ctrl)