BaseOptim#

deepinv.optim.BaseOptim(iterator, params_algo={'lambda': 1.0, 'stepsize': 1.0}, data_fidelity=None, prior=None, max_iter=100, crit_conv='residual', thres_conv=1e-05, early_stop=False, has_cost=False, backtracking=False, gamma_backtracking=0.1, eta_backtracking=0.9, custom_metrics=None, custom_init=None, get_output=<function BaseOptim.<lambda>>, anderson_acceleration=False, history_size=5, beta_anderson_acc=1.0, eps_anderson_acc=0.0001, verbose=False)[source]#

Class for optimization algorithms, consists in iterating a fixed-point operator.

Module solving the problem

\[\begin{equation} \label{eq:min_prob} \tag{1} \underset{x}{\arg\min} \quad \datafid{x}{y} + \lambda \reg{x}, \end{equation}\]

where the first term \(\datafidname:\xset\times\yset \mapsto \mathbb{R}_{+}\) enforces data-fidelity, the second term \(\regname:\xset\mapsto \mathbb{R}_{+}\) acts as a regularization and \(\lambda > 0\) is a regularization parameter. More precisely, the data-fidelity term penalizes the discrepancy between the data \(y\) and the forward operator \(A\) applied to the variable \(x\), as

\[\datafid{x}{y} = \distance{Ax}{y}\]

where \(\distance{\cdot}{\cdot}\) is a distance function, and where \(A:\xset\mapsto \yset\) is the forward operator (see deepinv.physics.Physics())

Optimization algorithms for minimising the problem above can be written as fixed point algorithms, i.e. for \(k=1,2,...\)

\[\qquad (x_{k+1}, z_{k+1}) = \operatorname{FixedPoint}(x_k, z_k, f, g, A, y, ...)\]

where \(x_k\) is a variable converging to the solution of the minimization problem, and \(z_k\) is an additional variable that may be required in the computation of the fixed point operator.

The optim_builder() function can be used to instantiate this class with a specific fixed point operator.

If the algorithm is minimizing an explicit and fixed cost function \(F(x) = \datafid{x}{y} + \lambda \reg{x}\), the value of the cost function is computed along the iterations and can be used for convergence criterion. Moreover, backtracking can be used to adapt the stepsize at each iteration. Backtracking consists in choosing the largest stepsize \(\tau\) such that, at each iteration, sufficient decrease of the cost function \(F\) is achieved. More precisely, Given \(\gamma \in (0,1/2)\) and \(\eta \in (0,1)\) and an initial stepsize \(\tau > 0\), the following update rule is applied at each iteration \(k\):

\[\text{ while } F(x_k) - F(x_{k+1}) < \frac{\gamma}{\tau} || x_{k-1} - x_k ||^2, \,\, \text{ do } \tau \leftarrow \eta \tau\]

The variable params_algo is a dictionary containing all the relevant parameters for running the algorithm. If the value associated with the key is a float, the algorithm will use the same parameter across all iterations. If the value is list of length max_iter, the algorithm will use the corresponding parameter at each iteration.

The variable data_fidelity is a list of instances of deepinv.optim.DataFidelity() (or a single instance). If a single instance, the same data-fidelity is used at each iteration. If a list, the data-fidelity can change at each iteration. The same holds for the variable prior which is a list of instances of deepinv.optim.Prior() (or a single instance).

>>> import deepinv as dinv
>>> # This minimal example shows how to use the BaseOptim class to solve the problem
>>> #                min_x 0.5  ||Ax-y||_2^2 + \lambda ||x||_1
>>> # with the PGD algorithm, where A is the identity operator, lambda = 1 and y = [2, 2].
>>>
>>> # Create the measurement operator A
>>> A = torch.tensor([[1, 0], [0, 1]], dtype=torch.float64)
>>> A_forward = lambda v: A @ v
>>> A_adjoint = lambda v: A.transpose(0, 1) @ v
>>>
>>> # Define the physics model associated to this operator
>>> physics = dinv.physics.LinearPhysics(A=A_forward, A_adjoint=A_adjoint)
>>>
>>> # Define the measurement y
>>> y = torch.tensor([2, 2], dtype=torch.float64)
>>>
>>> # Define the data fidelity term
>>> data_fidelity = dinv.optim.data_fidelity.L2()
>>>
>>> # Define the prior
>>> prior = dinv.optim.Prior(g = lambda x, *args: torch.norm(x, p=1))
>>>
>>> # Define the parameters of the algorithm
>>> params_algo = {"stepsize": 0.5, "lambda": 1.0}
>>>
>>> # Define the fixed-point iterator
>>> iterator = dinv.optim.optim_iterators.PGDIteration()
>>>
>>> # Define the optimization algorithm
>>> optimalgo = dinv.optim.BaseOptim(iterator,
...                     data_fidelity=data_fidelity,
...                     params_algo=params_algo,
...                     prior=prior)
>>>
>>> # Run the optimization algorithm
>>> with torch.no_grad(): xhat = optimalgo(y, physics)
>>> print(xhat)
tensor([1., 1.], dtype=torch.float64)

Parameters:

iterator (deepinv.optim.optim_iterators.OptimIterator) – Fixed-point iterator of the optimization algorithm of interest.
params_algo (dict) – dictionary containing all the relevant parameters for running the algorithm, e.g. the stepsize, regularisation parameter, denoising standard deviation. Each value of the dictionary can be either Iterable (distinct value for each iteration) or a single float (same value for each iteration). Default: {“stepsize”: 1.0, “lambda”: 1.0}. See Parameters for more details.
deepinv.optim.DataFidelity (list,) – data-fidelity term. Either a single instance (same data-fidelity for each iteration) or a list of instances of deepinv.optim.DataFidelity() (distinct data-fidelity for each iteration). Default: None.
deepinv.optim.Prior (list,) – regularization prior. Either a single instance (same prior for each iteration) or a list of instances of deepinv.optim.Prior() (distinct prior for each iteration). Default: None.
max_iter (int) – maximum number of iterations of the optimization algorithm. Default: 100.
crit_conv (str) – convergence criterion to be used for claiming convergence, either "residual" (residual of the iterate norm) or “cost” (on the cost function). Default: "residual"
thres_conv (float) – value of the threshold for claiming convergence. Default: 1e-05.
early_stop (bool) – whether to stop the algorithm once the convergence criterion is reached. Default: True.
has_cost (bool) – whether the algorithm has an explicit cost function or not. Default: False.
custom_metrics (dict) – dictionary containing custom metrics to be computed at each iteration.
backtracking (bool) – whether to apply a backtracking strategy for stepsize selection. Default: False.
gamma_backtracking (float) – \(\gamma\) parameter in the backtracking selection. Default: 0.1.
eta_backtracking (float) – \(\eta\) parameter in the backtracking selection. Default: 0.9.
custom_init (function) – initializes the algorithm with custom_init(y, physics). If None (default value), the algorithm is initialized with the adjoint \(A^{\top}y\) when the adjoint is defined, and with the observation y if the adjoint is not defined. Default: None.
get_output (function) – get the image output given the current dictionary update containing primal and auxiliary variables X = {('est' : (primal, aux)}. Default : X['est'][0].
anderson_acceleration (bool) – whether to use Anderson acceleration for accelerating the forward fixed-point iterations. Default: False.
history_size (int) – size of the history of iterates used for Anderson acceleration. Default: 5.
beta_anderson_acc (float) – momentum of the Anderson acceleration step. Default: 1.0.
eps_anderson_acc (float) – regularization parameter of the Anderson acceleration step. Default: 1e-4.
verbose (bool) – whether to print relevant information of the algorithm during its run, such as convergence criterion at each iterate. Default: False.

Returns: