elsa problems

Problem

template<typename data_t = real_t>
class elsa::Problem : public elsa::Cloneable<Problem<real_t>>

Class representing a generic optimization problem consisting of data term and regularization term(s).

This class represents a generic optimization problem, which consists of a data term and (optionally) of one (or many) regularization terms,

\( \argmin_x D(x) + \sum_{i=1}^n \lambda_i R(x) \). Here, the data term \( D(x) \) is represented through a Functional (or it derivatives), the regularization terms are represented by RegularizationTerms, which encapsulate regularization parameters \( \lambda_i \) (scalar values) and the actual regularization terms \( R(x) \) (Functionals or its derivatives).
Author

Matthias Wieczorek - initial code

Author

Maximilian Hornung - modularization

Author

Tobias Lasser - rewrite, modernization

Template Parameters
  • data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

Problem(const Functional<data_t> &dataTerm, const std::vector<RegularizationTerm<data_t>> &regTerms, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data and multiple regularization terms, and an initial guess x0.

Parameters
  • [in] dataTerm: functional expressing the data term

  • [in] regTerms: vector of RegularizationTerms (weight and functional)

  • [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm, const std::vector<RegularizationTerm<data_t>> &regTerms)

Constructor for optimization problem, accepting a data and multiple regularization terms.

Parameters
  • [in] dataTerm: functional expressing the data term

  • [in] regTerms: vector of RegularizationTerms (weight and functional)

Problem(const Functional<data_t> &dataTerm, const RegularizationTerm<data_t> &regTerm, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data and one regularization term, and an initial guess x0.

Parameters
  • [in] dataTerm: functional expressing the data term

  • [in] regTerm: RegularizationTerm (weight and functional)

  • [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm, const RegularizationTerm<data_t> &regTerm)

Constructor for optimization problem, accepting a data and one regularization term.

Parameters
  • [in] dataTerm: functional expressing the data term

  • [in] regTerm: RegularizationTerm (weight and functional)

Problem(const Functional<data_t> &dataTerm, const DataContainer<data_t> &x0)

Constructor for optimization problem, accepting a data term and an initial guess x0.

Parameters
  • [in] dataTerm: functional expressing the data term

  • [in] x0: initial value for the current estimated solution

Problem(const Functional<data_t> &dataTerm)

Constructor for optimization problem, accepting a data term.

Parameters
  • [in] dataTerm: functional expressing the data term

~Problem() override = default

default destructor

const Functional<data_t> &getDataTerm() const

return the data term

const std::vector<RegularizationTerm<data_t>> &getRegularizationTerms() const

return the vector of regularization terms

const DataContainer<data_t> &getCurrentSolution() const

return the current estimated solution (const version)

DataContainer<data_t> &getCurrentSolution()

return the current estimated solution

data_t evaluate()

evaluate the problem at the current estimated solution

Please note: this method calls the method _evaluate that has to be overridden in derived classes.

Return

the value of the problem evaluated at the current estimated solution

DataContainer<data_t> getGradient()

return the gradient of the problem at the current estimated solution

Please note: this method used getGradient(result) to perform the actual operation.

Return

DataContainer (in the domain of the problem) containing the result of the gradient at the current solution

void getGradient(DataContainer<data_t> &result)

compute the gradient of the problem at the current estimated solution

Please note: this method calls the method _getGradient that has to be overridden in derived classes.

Parameters
  • [out] result: output DataContainer containing the gradient (in the domain of the problem)

LinearOperator<data_t> getHessian() const

return the Hessian of the problem at the current estimated solution

Please note: this method calls the method _getHessian that has to be overridden in derived classes.

Return

a LinearOperator (the Hessian)

data_t getLipschitzConstant(index_t nIterations = 5) const

return the Lipschitz Constant of the problem at the current estimated solution

Please note: this method calls the method getLipschitzConstantImpl that has to be overridden in derived classes which want to provide a more specific way of computing the Lipschitz constant, e.g. by not using power iteration or where the hessian is already approximated as a diagonal matrix.

Return

data_t (the Lipschitz Constant)

Parameters
  • [in] nIterations: number of iterations to compute the lipschitz constant using power iteration.

Protected Functions

Problem(const Problem<data_t> &problem)

protected copy constructor, simplifies cloning (of the subclasses primarily)

data_t evaluateImpl()

the evaluation of the optimization problem

void getGradientImpl(DataContainer<data_t> &result)

the getGradient method for the optimization problem

LinearOperator<data_t> getHessianImpl() const

the getHessian method for the optimization problem

data_t getLipschitzConstantImpl(index_t nIterations) const

the getLipschitzConstant method for the optimization problem

Problem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

bool isEqual(const Problem<data_t> &other) const override

implement the polymorphic comparison operation

Protected Attributes

std::unique_ptr<Functional<data_t>> _dataTerm = {}

the data term

std::vector<RegularizationTerm<data_t>> _regTerms = {}

the regularization terms

DataContainer<data_t> _currentSolution

the current estimated solution

RegularizationTerm

template<typename data_t = real_t>
class elsa::RegularizationTerm

Class representing a regularization term (a scalar parameter and a functional).

This class represents a regularization term, consisting of a regularization parameter (a scalar) and a term (represented as a

Functional). It is just a light-weight wrapper with no added functionality.
Author

Maximilian Hornung - initial code

Author

Tobias Lasser - modernization

Template Parameters
  • data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

RegularizationTerm(data_t weight, const Functional<data_t> &functional)

Constructor for the regularization term, accepting a weight and a functional.

Parameters
  • weight: the regularization parameter

  • functional: the actual term

RegularizationTerm(const RegularizationTerm<data_t> &other)

copy constructor

RegularizationTerm<data_t> &operator=(const RegularizationTerm<data_t> &other)

copy assignment

RegularizationTerm(RegularizationTerm<data_t> &&other) noexcept

move constructor

RegularizationTerm<data_t> &operator=(RegularizationTerm<data_t> &&other) noexcept

move assignment

~RegularizationTerm() = default

the default destructor

data_t getWeight() const

return the weight of the regularization term (the regularization parameter)

Functional<data_t> &getFunctional() const

return the functional of the regularization term

bool operator==(const RegularizationTerm<data_t> &other) const

comparison operator

bool operator!=(const RegularizationTerm<data_t> &other) const

negative comparison operator

Private Members

data_t _weight

the weight / regularization parameter

std::unique_ptr<Functional<data_t>> _functional

the functional of the regularization term

WLSProblem

template<typename data_t = real_t>
class elsa::WLSProblem : public elsa::Problem<real_t>

Class representing a weighted least squares problem.

This class represents a weighted least squares optimization problem, i.e.

\( \argmin_x \frac{1}{2} \| Ax - b \|_{W,2}^2 \), where \( W \) is a weighting (scaling) operator, \( A \) is a linear operator and \( b \) is a data vector.
Author

Jakob Vogel - initial code

Author

Matthias Wieczorek - rewrite

Author

Tobias Lasser - another rewrite, modernization

Author

Nikola Dinev - added conversion constructor

Template Parameters
  • data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

WLSProblem(const Scaling<data_t> &W, const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0)

Constructor for the wls problem, accepting W, A, b, and an initial guess x0.

Parameters
  • [in] W: scaling operator for weighting

  • [in] A: linear operator

  • [in] b: data vector

  • [in] x0: initial value for the current estimated solution

WLSProblem(const Scaling<data_t> &W, const LinearOperator<data_t> &A, const DataContainer<data_t> &b)

Constructor for the wls problem, accepting W, A, and b.

Parameters
  • [in] W: scaling operator for weighting

  • [in] A: linear operator

  • [in] b: data vector

WLSProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0)

Constructor for the (w)ls problem, accepting A, b, and an initial guess x0 (no weights)

Parameters
  • [in] A: linear operator

  • [in] b: data vector

  • [in] x0: initial value for the current estimated solution

WLSProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b)

Constructor for the (w)ls problem, accepting A and b (no weights)

Parameters
  • [in] A: linear operator

  • [in] b: data vector

WLSProblem(const Problem<data_t> &problem)

Constructor for converting a general optimization problem to a WLS problem.

Only problems that consist exclusively of (Weighted)

L2NormPow2 terms can be converted. The (Weighted)L2NormPow2 should be acting on a LinearResidual.
Parameters
  • [in] problem: the problem to be converted

Acts as a copy constructor if the supplied optimization problem is a quadric problem.

~WLSProblem() override = default

default destructor

Protected Functions

WLSProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

Private Static Functions

std::unique_ptr<Functional<data_t>> wlsFromProblem(const Problem<data_t> &problem)

converts an optimization problem to a (Weighted)L2NormPow2 functional

TikhonovProblem

template<typename data_t = real_t>
class elsa::TikhonovProblem : public elsa::Problem<real_t>

Class representing a Tikhonov regularized weighted least squares problem.

This class represents a Tikhonov regularized weighted least squares problem. Some common examples are:

  • \( \argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| x \|_2^2 \)

  • \( \argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| x - x^* \|_2^2 \)

  • \( \argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| Lx \|_2^2 \)

  • \( \argmin_x \frac{1}{2} \| Ax - b \|_2^2 + \lambda \| L(x - x^*) \|_2^2 \), where \( A \) is a linear operator and \( b \) and \( x^* \) are data vectors, \( \lambda \) is the regularization weight, and \( L \) is a discretized differential operator.

Author

Nikola Dinev

Template Parameters
  • data_t: data type for the domain and range of the problem, defaulting to real_t

This class supports a wider range of problems - any problem of the form \( \argmin_x \frac{1}{2} \| Ax - b \|_{W,2}^2 + \sum_{i=1}^n \lambda_i \| B_ix - x^*_i \|_{V_i,2}^2 \) is considered a Tikhonov problem. Here \( A \) and \( B_i \) are linear operators, \( b \) and \( x^*_i \) are data vectors, \( \lambda_i \) are the regularization weights, and \( W \) and \( V_i \) are scaling operators.

Public Functions

TikhonovProblem(const WLSProblem<data_t> &wlsProblem, const std::vector<RegularizationTerm<data_t>> &regTerms)

Constructor for a Tikhonov problem.

Parameters
  • [in] wlsProblem: a wls problem specifying the data term and the initial solution

  • [in] regTerms: the regularization terms, all should be of type L2NormPow2 or WeightedL2NormPow2

TikhonovProblem(const WLSProblem<data_t> &wlsProblem, const RegularizationTerm<data_t> &regTerm)

Constructor for a Tikhonov problem.

Parameters
  • [in] wlsProblem: a wls problem specifying the data term and the initial solution

  • [in] regTerm: the regularization term, should be of type L2NormPow2 or WeightedL2NormPow2

~TikhonovProblem() override = default

default destructor

Protected Functions

TikhonovProblem(const TikhonovProblem<data_t>&) = default

default copy constructor, hidden from non-derived classes to prevent potential slicing

TikhonovProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

QuadricProblem

template<typename data_t = real_t>
class elsa::QuadricProblem : public elsa::Problem<real_t>

Class representing a quadric problem.

This class represents a quadric problem, i.e.

\( \argmin_x \frac{1}{2} x^tAx - x^tb \) where \( A \) is a symmetric positive-definite operator and \( b \) is a data vector.
Author

Nikola Dinev

Template Parameters
  • data_t: data type for the domain and range of the problem, defaulting to real_t

Public Functions

QuadricProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, const DataContainer<data_t> &x0, bool spdA)

Constructor for the quadric problem accepting A, b, and an initial guess x0.

Sets up the quadric problem

\( \argmin_x \frac{1}{2} x^tAx - x^tb \) if \( A \) is spd, and \( \argmin_x \frac{1}{2} x^tA^tAx - x^tA^tb \) if \( A \) is not spd
Parameters
  • [in] A: linear operator

  • [in] b: data vector

  • [in] x0: initial value for the current estimated solution

  • [in] spdA: flag whether A is symmetric positive-definite

Please note: For a general complex operator

\( A \), it does not necessarily hold that \( A^*A \) is spd. Therefore, QuadricProblem is restricted to the non-complex variants.
Warning

A must be nonsingular even if it is not spd.

QuadricProblem(const LinearOperator<data_t> &A, const DataContainer<data_t> &b, bool spdA)

Constructor for the quadric problem accepting A and b.

Sets up the quadric problem

\( \argmin_x \frac{1}{2} x^tAx - x^tb \) if \( A \) is spd, and \( \argmin_x \frac{1}{2} x^tA^tAx - x^tA^tb \) if \( A \) is not spd
Parameters
  • [in] A: linear operator

  • [in] b: data vector

  • [in] spdA: flag whether A is symmetric positive-definite

Please note: For a general complex operator

\( A \), it does not necessarily hold that \( A^*A \) is spd. Therefore, QuadricProblem is restricted to the non-complex variants.
Warning

A must be nonsingular even if it is not spd.

QuadricProblem(const Quadric<data_t> &quadric, const DataContainer<data_t> &x0)

Constructor for the quadric problem accepting a quadric and an initial guess x0.

Parameters
  • [in] quadric: a Quadric containing the entire problem formulation

  • [in] x0: initial value for the current estimated solution

QuadricProblem(const Quadric<data_t> &quadric)

Constructor for the quadric problem accepting a quadric.

Parameters
  • [in] quadric: a Quadric containing the entire problem formulation

QuadricProblem(const Problem<data_t> &problem)

Constructor for converting a general optimization problem to a quadric one.

Only problems that consist exclusively of

Quadric and (Weighted)L2NormPow2 terms can be converted. If (Weighted)L2NormPow2 terms are present, they should be acting on a LinearResidual.
Parameters
  • [in] problem: the problem to be converted

Acts as a copy constructor if the supplied optimization problem is a quadric problem.

Protected Functions

QuadricProblem<data_t> *cloneImpl() const override

implement the polymorphic clone operation

Private Static Functions

LinearResidual<data_t> getGradientExpression(const RegularizationTerm<data_t> &regTerm)

returns an expression for calculating the gradient of the regularization term

std::unique_ptr<Quadric<data_t>> quadricFromProblem(const Problem<data_t> &problem)

converts an optimization problem to a quadric