Line data    Source code

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