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