L0-approximation algorithm, through reweighting. More...

#include <reweighted.h>

Classes
struct	ReweightedResult
	output from running reweighting scheme More...

Public Types
using	Algorithm = ALGORITHM
	Inner-loop algorithm. More...

using	Scalar = typename Algorithm::Scalar
	Scalar type. More...

using	Real = typename real_type< Scalar >::type
	Real type. More...

using	WeightVector = Vector< Real >
	Weight vector type. More...

using	XVector = typename Algorithm::t_Vector
	Type of then underlying vectors. More...

using	t_IsConverged = ConvergenceFunction< Scalar >
	Type of the convergence function. More...

using	t_Reweightee = std::function< XVector(const Algorithm &, const XVector &)>
	Type of the function that is subject to reweighting. More...

using	t_SetWeights = std::function< void(Algorithm &, const WeightVector &)>
	Type of the function to set weights. More...

using	t_DeltaUpdate = std::function< Real(Real)>
	Function to update delta at each turn. More...

Public Member Functions
	Reweighted (Algorithm const &algo, t_SetWeights const &setweights, t_Reweightee const &reweightee)

Algorithm &	algorithm ()
	Underlying "inner-loop" algorithm. More...

Algorithm const &	algorithm () const
	Underlying "inner-loop" algorithm. More...

Reweighted< Algorithm > &	algorithm (Algorithm const &algo)
	Sets the underlying "inner-loop" algorithm. More...

Reweighted< Algorithm > &	algorithm (Algorithm &&algo)
	Sets the underlying "inner-loop" algorithm. More...

t_SetWeights const &	set_weights () const
	Function to reset the weights in the algorithm. More...

Reweighted< Algorithm > &	set_weights (t_SetWeights const &setweights) const
	Function to reset the weights in the algorithm. More...

void	set_weights (Algorithm &algo, WeightVector const &weights) const
	Sets the weights on the underlying algorithm. More...

Reweighted< Algorithm > &	reweightee (t_Reweightee const &rw)

t_Reweightee const &	reweightee () const
	Function that needs to be reweighted. More...

XVector	reweightee (XVector const &x) const
	Forwards to the reweightee function. More...

t_uint	itermax () const
	Maximum number of reweighted iterations. More...

Reweighted &	itermax (t_uint i)

Real	min_delta () const
	Lower limit for delta. More...

Reweighted &	min_delta (Real min_delta)

t_IsConverged const &	is_converged () const
	Checks convergence of the reweighting scheme. More...

Reweighted &	is_converged (t_IsConverged const &convergence)

bool	is_converged (XVector const &x) const

template<typename INPUT >
std::enable_if< not(std::is_same< INPUT, typename Algorithm::DiagnosticAndResult >::value or std::is_same< INPUT, ReweightedResult >::value), ReweightedResult >::type	operator() (INPUT const &input) const
	Performs reweighting. More...

ReweightedResult	operator() () const
	Performs reweighting. More...

ReweightedResult	operator() (typename Algorithm::DiagnosticAndResult const &warm) const
	Reweighted algorithm, from prior call to inner-algorithm. More...

ReweightedResult	operator() (ReweightedResult const &warm) const
	Reweighted algorithm, from prior call to reweighting algorithm. More...

Real	update_delta (Real delta) const
	Updates delta. More...

t_DeltaUpdate const &	update_delta () const
	Updates delta. More...

Reweighted< Algorithm >	update_delta (t_DeltaUpdate const &ud) const
	Updates delta. More...

Detailed Description

template<typename ALGORITHM>
class sopt::algorithm::Reweighted< ALGORITHM >

L0-approximation algorithm, through reweighting.

This algorithm approximates \(min_x ||Ψ^Tx||_0 + f(x)\) by solving the set of problems \(j\), \(min_x ||W_jΨ^Tx||_1 + f(x)\) where the diagonal matrix \(W_j\) is set using the results from \(j-1\): \( δ_j W_j^{-1} = δ_j + ||W_{j-1}Ψ^T||_1\). \(δ_j\) prevents division by zero. It is a series which converges to zero. By default, \(δ_{j+1}=0.1δ_j\).

The algorithm proceeds needs three forms of input:

the inner algorithm, e.g. ImagingProximalADMM
a function returning Ψ^Tx given x
a function to modify the inner algorithm with new weights

Definition at line 34 of file reweighted.h.

Member Typedef Documentation

◆ Algorithm

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::Algorithm = ALGORITHM

Inner-loop algorithm.

Definition at line 37 of file reweighted.h.

◆ Real

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::Real = typename real_type<Scalar>::type

Real type.

Definition at line 41 of file reweighted.h.

◆ Scalar

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::Scalar = typename Algorithm::Scalar

Scalar type.

Definition at line 39 of file reweighted.h.

◆ t_DeltaUpdate

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::t_DeltaUpdate = std::function<Real (Real)>

Function to update delta at each turn.

Definition at line 54 of file reweighted.h.

◆ t_IsConverged

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::t_IsConverged = ConvergenceFunction<Scalar>

Type of the convergence function.

Definition at line 47 of file reweighted.h.

◆ t_Reweightee

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::t_Reweightee = std::function<XVector (const Algorithm &, const XVector &)>

Type of the function that is subject to reweighting.

E.g. \(Ψ^Tx\). Note that l1-norm is not applied here.

Definition at line 50 of file reweighted.h.

◆ t_SetWeights

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::t_SetWeights = std::function<void (Algorithm &, const WeightVector &)>

Type of the function to set weights.

Definition at line 52 of file reweighted.h.

◆ WeightVector

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::WeightVector = Vector<Real>

Weight vector type.

Definition at line 43 of file reweighted.h.

◆ XVector

template<typename ALGORITHM >

using sopt::algorithm::Reweighted< ALGORITHM >::XVector = typename Algorithm::t_Vector

Type of then underlying vectors.

Definition at line 45 of file reweighted.h.

Constructor & Destructor Documentation

◆ Reweighted()

template<typename ALGORITHM >

sopt::algorithm::Reweighted< ALGORITHM >::Reweighted	(	Algorithm const &	algo,
		t_SetWeights const &	setweights,
		t_Reweightee const &	reweightee
	)

inline

Definition at line 70 of file reweighted.h.

       : algo_(algo),
         setweights_(setweights),
         reweightee_(reweightee),
         itermax_(std::numeric_limits<t_uint>::max()),
         min_delta_(0e0),
         is_converged_(),
         update_delta_([](Real delta) { return 1e-1 * delta; }) {}

Member Function Documentation

◆ algorithm() [1/4]

template<typename ALGORITHM >

Algorithm& sopt::algorithm::Reweighted< ALGORITHM >::algorithm ( )

inline

Underlying "inner-loop" algorithm.

Definition at line 80 of file reweighted.h.

80 { return algo_; }

Referenced by sopt::algorithm::reweighted(), and sopt::algorithm::Reweighted< ALGORITHM >::reweightee().

◆ algorithm() [2/4]

template<typename ALGORITHM >

Algorithm const& sopt::algorithm::Reweighted< ALGORITHM >::algorithm ( ) const

inline

Underlying "inner-loop" algorithm.

Definition at line 82 of file reweighted.h.

82 { return algo_; }

◆ algorithm() [3/4]

template<typename ALGORITHM >

Reweighted<Algorithm>& sopt::algorithm::Reweighted< ALGORITHM >::algorithm ( Algorithm && algo )

inline

Sets the underlying "inner-loop" algorithm.

Definition at line 89 of file reweighted.h.

                                                      {
     algo_ = std::move(algo);
     return *this;
   }

◆ algorithm() [4/4]

template<typename ALGORITHM >

Reweighted<Algorithm>& sopt::algorithm::Reweighted< ALGORITHM >::algorithm ( Algorithm const & algo )

inline

Sets the underlying "inner-loop" algorithm.

Definition at line 84 of file reweighted.h.

                                                           {
     algo_ = algo;
     return *this;
   }

◆ is_converged() [1/3]

template<typename ALGORITHM >

t_IsConverged const& sopt::algorithm::Reweighted< ALGORITHM >::is_converged ( ) const

inline

Checks convergence of the reweighting scheme.

Definition at line 130 of file reweighted.h.

130 { return is_converged_; }

◆ is_converged() [2/3]

template<typename ALGORITHM >

Reweighted& sopt::algorithm::Reweighted< ALGORITHM >::is_converged ( t_IsConverged const & convergence )

inline

Definition at line 131 of file reweighted.h.

                                                              {
     is_converged_ = convergence;
     return *this;
   }

◆ is_converged() [3/3]

template<typename ALGORITHM >

bool sopt::algorithm::Reweighted< ALGORITHM >::is_converged ( XVector const & x ) const

inline

Definition at line 135 of file reweighted.h.

135 { return is_converged() ? is_converged()(x) : false; }

sopt::algorithm::Reweighted::is_converged

t_IsConverged const & is_converged() const

Checks convergence of the reweighting scheme.

Definition: reweighted.h:130

References sopt::algorithm::Reweighted< ALGORITHM >::is_converged().

Referenced by sopt::algorithm::Reweighted< ALGORITHM >::is_converged().

◆ itermax() [1/2]

template<typename ALGORITHM >

t_uint sopt::algorithm::Reweighted< ALGORITHM >::itermax ( ) const

inline

Maximum number of reweighted iterations.

Definition at line 118 of file reweighted.h.

118 { return itermax_; }

◆ itermax() [2/2]

template<typename ALGORITHM >

Reweighted& sopt::algorithm::Reweighted< ALGORITHM >::itermax ( t_uint i )

inline

Definition at line 119 of file reweighted.h.

                                 {
     itermax_ = i;
     return *this;
   }

◆ min_delta() [1/2]

template<typename ALGORITHM >

Real sopt::algorithm::Reweighted< ALGORITHM >::min_delta ( ) const

inline

Lower limit for delta.

Definition at line 124 of file reweighted.h.

124 { return min_delta_; }

Referenced by sopt::algorithm::Reweighted< ALGORITHM >::min_delta().

◆ min_delta() [2/2]

template<typename ALGORITHM >

Reweighted& sopt::algorithm::Reweighted< ALGORITHM >::min_delta ( Real min_delta )

inline

Definition at line 125 of file reweighted.h.

                                         {
     min_delta_ = min_delta;
     return *this;
   }

References sopt::algorithm::Reweighted< ALGORITHM >::min_delta().

◆ operator()() [1/4]

template<typename ALGORITHM >

Reweighted< ALGORITHM >::ReweightedResult sopt::algorithm::Reweighted< ALGORITHM >::operator()

Performs reweighting.

This overload will compute an initial result without initial weights set to one.

Definition at line 190 of file reweighted.h.

                                                                                        {
   Algorithm algo = algorithm();
   set_weights(algo, WeightVector::Ones(1));
   return operator()(algo());
 }

◆ operator()() [2/4]

template<typename ALGORITHM >

template<typename INPUT >

std::enable_if< not(std::is_same< INPUT, typename ALGORITHM::DiagnosticAndResult >::value or std::is_same< INPUT, typename Reweighted< ALGORITHM >::ReweightedResult >::value), typename Reweighted< ALGORITHM >::ReweightedResult >::type sopt::algorithm::Reweighted< ALGORITHM >::operator() ( INPUT const & input ) const

Performs reweighting.

This overload will compute an initial result without initial weights set to one.

Definition at line 183 of file reweighted.h.

                                                           {
   Algorithm algo = algorithm();
   set_weights(algo, WeightVector::Ones(1));
   return operator()(algo(input));
 }

◆ operator()() [3/4]

template<typename ALGORITHM >

Reweighted< ALGORITHM >::ReweightedResult sopt::algorithm::Reweighted< ALGORITHM >::operator() ( ReweightedResult const & warm ) const

Reweighted algorithm, from prior call to reweighting algorithm.

Definition at line 206 of file reweighted.h.

                                         {
   SOPT_HIGH_LOG("Starting reweighted scheme");
   // Copies inner algorithm, so that operator() can be constant
   Algorithm algo(algorithm());
   ReweightedResult result(warm);
  
   auto delta = std::max(standard_deviation(reweightee(warm.algo.x)), min_delta());
   SOPT_LOW_LOG("-   Initial delta: {}", delta);
   for (result.niters = 0; result.niters < itermax(); ++result.niters) {
     SOPT_LOW_LOG("Reweigting iteration {}/{} ", result.niters, itermax());
     SOPT_LOW_LOG("  - delta: {}", delta);
     result.weights = delta / (delta + reweightee(result.algo.x).array().abs());
     set_weights(algo, result.weights);
     result.algo = algo(result.algo);
     if (is_converged(result.algo.x)) {
       SOPT_MEDIUM_LOG("Reweighting scheme did converge in {} iterations", result.niters);
       result.good = true;
       break;
     }
     delta = std::max(min_delta(), update_delta(delta));
   }
   // result is always good if no convergence function is defined
   if (not is_converged())
     result.good = true;
   else if (not result.good)
     SOPT_ERROR("Reweighting scheme did *not* converge in {} iterations", itermax());
   return result;
 }

References sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::algo, sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::good, sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::niters, SOPT_ERROR, SOPT_HIGH_LOG, SOPT_LOW_LOG, SOPT_MEDIUM_LOG, sopt::standard_deviation(), and sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::weights.

◆ operator()() [4/4]

template<typename ALGORITHM >

Reweighted< ALGORITHM >::ReweightedResult sopt::algorithm::Reweighted< ALGORITHM >::operator() ( typename Algorithm::DiagnosticAndResult const & warm ) const

Reweighted algorithm, from prior call to inner-algorithm.

Definition at line 197 of file reweighted.h.

                                                              {
   ReweightedResult result;
   result.algo = warm;
   result.weights = WeightVector::Ones(1);
   return operator()(result);
 }

References sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::algo, and sopt::algorithm::Reweighted< ALGORITHM >::ReweightedResult::weights.

◆ reweightee() [1/3]

template<typename ALGORITHM >

t_Reweightee const& sopt::algorithm::Reweighted< ALGORITHM >::reweightee ( ) const

inline

Function that needs to be reweighted.

Definition at line 113 of file reweighted.h.

113 { return reweightee_; }

◆ reweightee() [2/3]

template<typename ALGORITHM >

Reweighted<Algorithm>& sopt::algorithm::Reweighted< ALGORITHM >::reweightee ( t_Reweightee const & rw )

inline

Function that needs to be reweighted

E.g. \(Ψ^Tx\). Note that l1-norm is not applied here.

Definition at line 108 of file reweighted.h.

                                                             {
     reweightee_ = rw;
     return *this;
   }

◆ reweightee() [3/3]

template<typename ALGORITHM >

XVector sopt::algorithm::Reweighted< ALGORITHM >::reweightee ( XVector const & x ) const

inline

Forwards to the reweightee function.

Definition at line 115 of file reweighted.h.

115 { return reweightee()(algorithm(), x); }

References sopt::algorithm::Reweighted< ALGORITHM >::algorithm(), and sopt::algorithm::Reweighted< ALGORITHM >::reweightee().

Referenced by sopt::algorithm::Reweighted< ALGORITHM >::reweightee().

◆ set_weights() [1/3]

template<typename ALGORITHM >

t_SetWeights const& sopt::algorithm::Reweighted< ALGORITHM >::set_weights ( ) const

inline

Function to reset the weights in the algorithm.

Definition at line 95 of file reweighted.h.

95 { return setweights_; }

Referenced by sopt::algorithm::Reweighted< ALGORITHM >::set_weights().

◆ set_weights() [2/3]

template<typename ALGORITHM >

void sopt::algorithm::Reweighted< ALGORITHM >::set_weights	(	Algorithm &	algo,
		WeightVector const &	weights
	)		const

inline

Sets the weights on the underlying algorithm.

Definition at line 102 of file reweighted.h.

                                                                        {
     return set_weights()(algo, weights);
   }

References sopt::algorithm::Reweighted< ALGORITHM >::set_weights().

◆ set_weights() [3/3]

template<typename ALGORITHM >

Reweighted<Algorithm>& sopt::algorithm::Reweighted< ALGORITHM >::set_weights ( t_SetWeights const & setweights ) const

inline

Function to reset the weights in the algorithm.

Definition at line 97 of file reweighted.h.

                                                                            {
     setweights_ = setweights;
     return *this;
   }

◆ update_delta() [1/3]

template<typename ALGORITHM >

t_DeltaUpdate const& sopt::algorithm::Reweighted< ALGORITHM >::update_delta ( ) const

inline

Updates delta.

Definition at line 155 of file reweighted.h.

155 { return update_delta_; }

◆ update_delta() [2/3]

template<typename ALGORITHM >

Real sopt::algorithm::Reweighted< ALGORITHM >::update_delta ( Real delta ) const

inline

Updates delta.

Definition at line 153 of file reweighted.h.

153 { return update_delta()(delta); }

References sopt::algorithm::Reweighted< ALGORITHM >::update_delta().

Referenced by sopt::algorithm::Reweighted< ALGORITHM >::update_delta().

◆ update_delta() [3/3]

template<typename ALGORITHM >

Reweighted<Algorithm> sopt::algorithm::Reweighted< ALGORITHM >::update_delta ( t_DeltaUpdate const & ud ) const

inline

Updates delta.

Definition at line 157 of file reweighted.h.

157 { return update_delta_ = ud; }

The documentation for this class was generated from the following file:

/home/runner/work/sopt/sopt/cpp/sopt/reweighted.h

Classes

Public Types

Public Member Functions

Detailed Description

template<typename ALGORITHM> class sopt::algorithm::Reweighted< ALGORITHM >

Member Typedef Documentation

◆ Algorithm

◆ Real

◆ Scalar

◆ t_DeltaUpdate

◆ t_IsConverged

◆ t_Reweightee

◆ t_SetWeights

◆ WeightVector

◆ XVector

Constructor & Destructor Documentation

◆ Reweighted()

Member Function Documentation

◆ algorithm() [1/4]

◆ algorithm() [2/4]

◆ algorithm() [3/4]

◆ algorithm() [4/4]

◆ is_converged() [1/3]

◆ is_converged() [2/3]

◆ is_converged() [3/3]

◆ itermax() [1/2]

◆ itermax() [2/2]

◆ min_delta() [1/2]

◆ min_delta() [2/2]

◆ operator()() [1/4]

◆ operator()() [2/4]

◆ operator()() [3/4]

◆ operator()() [4/4]

◆ reweightee() [1/3]

◆ reweightee() [2/3]

◆ reweightee() [3/3]

◆ set_weights() [1/3]

◆ set_weights() [2/3]

◆ set_weights() [3/3]

◆ update_delta() [1/3]

◆ update_delta() [2/3]

◆ update_delta() [3/3]

template<typename ALGORITHM>
class sopt::algorithm::Reweighted< ALGORITHM >