Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <optional>
       4             : 
       5             : #include "DataContainer.h"
       6             : #include "LinearOperator.h"
       7             : #include "Solver.h"
       8             : #include "StrongTypes.h"
       9             : #include "ProximalOperator.h"
      10             : 
      11             : namespace elsa
      12             : {
      13             :     /**
      14             :      * Aссelerated Linearized Bregman converges faster than Linearized Bregman and solves problems
      15             :      * of form:
      16             :      * @f[
      17             :      * \min_{x} \frac{1}{2\mu} || A x - b ||_2^2 + |x|
      18             :      * @f]
      19             :      *
      20             :      * by iteratively solving:
      21             :      *
      22             :      * @f[
      23             :      * \begin{aligned}
      24             :      * x^{k+1} & =\mu \cdot \operatorname{prox}\left(\tilde{v}^k, 1\right) \\
      25             :      * v^{k+1} & =\tilde{v}^k+\beta A^T\left(b-A x^{k+1}\right) \\
      26             :      * \tilde{v}^{k+1} & :=\alpha_k v^{k+1}+\left(1-\alpha_k\right) v^k
      27             :      * \end{aligned}
      28             :      * @f]
      29             :      *
      30             :      * where @f$ a_k = \frac{2k + 3}{k + 3} @f$
      31             :      *
      32             :      * References:
      33             :      * - https://arxiv.org/pdf/1106.5413.pdf
      34             :      */
      35             :     template <typename data_t = real_t>
      36             :     class ALB : public Solver<data_t>
      37             :     {
      38             :     public:
      39             :         /// Construct Linearized Bregman
      40             :         ALB(const LinearOperator<data_t>& A, const DataContainer<data_t>& b,
      41             :             const ProximalOperator<data_t> prox, data_t mu = 5,
      42             :             std::optional<data_t> beta = std::nullopt, data_t epsilon = 1e-5);
      43             : 
      44             :         /// make copy constructor deletion explicit
      45             :         ALB(const ALB<data_t>&) = delete;
      46             : 
      47             :         /// default destructor
      48           4 :         ~ALB() override = default;
      49             : 
      50             :         /// Setup variables to default values
      51             :         DataContainer<data_t> setup(std::optional<DataContainer<data_t>> x) override;
      52             : 
      53             :         /// Perform single step of the algorithm
      54             :         DataContainer<data_t> step(DataContainer<data_t> x) override;
      55             : 
      56             :         /// Check if the L2 distance between the residual and b is below a certain threshold
      57             :         bool shouldStop() const override;
      58             : 
      59             :         std::string formatHeader() const override;
      60             : 
      61             :         std::string formatStep(const DataContainer<data_t>& x) const override;
      62             : 
      63             :     protected:
      64             :         /// implement the polymorphic clone operation
      65             :         auto cloneImpl() const -> ALB<data_t>* override;
      66             : 
      67             :         /// implement the polymorphic comparison operation
      68             :         auto isEqual(const Solver<data_t>& other) const -> bool override;
      69             : 
      70             :     private:
      71             :         /// The LASSO optimization problem
      72             :         std::unique_ptr<LinearOperator<data_t>> A_;
      73             : 
      74             :         DataContainer<data_t> b_;
      75             : 
      76             :         DataContainer<data_t> v_;
      77             : 
      78             :         DataContainer<data_t> vPrev_;
      79             : 
      80             :         DataContainer<data_t> vTilda_;
      81             : 
      82             :         DataContainer<data_t> residual_;
      83             : 
      84             :         ProximalOperator<data_t> prox_;
      85             : 
      86             :         /// wage of fidelity term
      87             :         data_t mu_;
      88             : 
      89             :         /// step size
      90             :         data_t beta_;
      91             : 
      92             :         /// variable affecting the stopping condition
      93             :         data_t epsilon_;
      94             :     };
      95             : } // namespace elsa