Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include "Solver.h"
       4             : #include "RepresentationProblem.h"
       5             : 
       6             : namespace elsa
       7             : {
       8             :     /**
       9             :      * @brief Class representing the Orthogonal Matching Pursuit.
      10             :      *
      11             :      * @author Jonas Buerger - initial code
      12             :      *
      13             :      * @tparam data_t data type for the domain and range of the problem, defaulting to real_t
      14             :      *
      15             :      * Orthogonal Matching Pursuit is a greedy algorithm to find a sparse representation. It starts
      16             :      * with the 0-vector and adds one non-zero entry per iteration. The algorithm works in the
      17             :      * following manner:
      18             :      * -# Find the next atom that should be used in the representation. This done by finding the
      19             :      * atom that is correlated the most with the current residual.
      20             :      * -# Construct a dictionary that only contains the atoms that are being used, defined as \f$
      21             :      * D_S \f$ (dictionary restricted to the support).
      22             :      * -# The representation is the solution to the least square problem \f$ min_x \|y-D_S*x\| \f$
      23             :      *
      24             :      */
      25             :     template <typename data_t = real_t>
      26             :     class OrthogonalMatchingPursuit : public Solver<data_t>
      27             :     {
      28             :     public:
      29             :         /// Scalar alias
      30             :         using Scalar = typename Solver<data_t>::Scalar;
      31             : 
      32             :         /**
      33             :          * @brief Constructor for OrthogonalMatchingPursuit, accepting a dictionary representation
      34             :          * problem and, optionally, a value for epsilon
      35             :          *
      36             :          * @param[in] problem the representation problem that is supposed to be solved
      37             :          * @param[in] epsilon affects the stopping condition
      38             :          */
      39             :         OrthogonalMatchingPursuit(const RepresentationProblem<data_t>& problem, data_t epsilon);
      40             : 
      41             :         /// make copy constructor deletion explicit
      42             :         OrthogonalMatchingPursuit(const OrthogonalMatchingPursuit<data_t>&) = delete;
      43             : 
      44             :         /// default destructor
      45           3 :         ~OrthogonalMatchingPursuit() override = default;
      46             : 
      47             :     private:
      48             :         /// The representation optimization problem
      49             :         RepresentationProblem<data_t> _problem;
      50             : 
      51             :         /// variable affecting the stopping condition
      52             :         data_t _epsilon;
      53             : 
      54             :         /// helper method to find the index of the atom that is most correlated with the residual
      55             :         index_t mostCorrelatedAtom(const Dictionary<data_t>& dict,
      56             :                                    const DataContainer<data_t>& evaluatedResidual);
      57             : 
      58             :         /**
      59             :          * @brief Solve the representation problem, i.e. apply iterations number of iterations of
      60             :          * matching pursuit
      61             :          *
      62             :          * @param[in] iterations number of iterations to execute. As OrthogonalMatchingPursuit is a
      63             :          * greedy algorithm, this corresponds to the desired sparsity level
      64             :          *
      65             :          * @returns a reference to the current solution
      66             :          */
      67             :         DataContainer<data_t>& solveImpl(index_t iterations) override;
      68             : 
      69             :         /// implement the polymorphic clone operation
      70             :         OrthogonalMatchingPursuit<data_t>* cloneImpl() const override;
      71             : 
      72             :         /// implement the polymorphic comparison operation
      73             :         bool isEqual(const Solver<data_t>& other) const override;
      74             :     };
      75             : } // namespace elsa