The Quadratic Majorize-Minimize toolbox
Project description
Q-MM is a Python implementation of Majorize-Minimize Quadratic optimization algorithms. Algorithms provided here come from
See documentation for more background. If you use this code, please cite the references above. A citation of this toolbox will also be appreciated.
@software{qmm, title = {Q-MM: The Quadratic Majorize-Minimize Python toolbox}, author = {Orieux, Fran\c{c}ois}, url = {https://github.com/forieux/qmm}, }
Quadratic Majorize-Minimize
The Q-MM optimization algorithms compute the minimizer of objective function like
J(x) = ∑ₖ μₖ ψₖ(Vₖ·x - ωₖ)
where x is the unknown vector, Vₖ a linear operator, ωₖ a fixed data, μₖ a scalar, ψₖ(u) = ∑ᵢφₖ(uᵢ), and φₖ a function that must be differentiable, even, coercive, φ(√·) concave, and 0 < φ’(u) / u < +∞.
The optimization is done thanks to quadratic sugorate function. In particular, no linesearch or sub-iteration is necessary, and close form formula for the step are used with guaranteed convergence.
A classical example, like in the figure below that show an image deconvolution problem, is the resolution of an inverse problem with the minimization of
J(x) = ||y - H·x||² + μ ψ(V·x)
where H is a low-pass forward model, V a regularization operator that approximate gradient (kind of high-pass filter) and ψ an edge preserving function like Huber. The above objective is obtained with k ∈ {1, 2}, ψ₁(·) = ||·||², V₁ = H, ω₁ = y, and ω₂ = 0.
Features
The mmmg, Majorize-Minimize Memory Gradient algorithm. See documentation and [2] for details.
The mmcg, Majorize-Minimize Conjugate Gradient algorithm. See documentation and [1] for details.
No linesearch: the step is obtained from a close form formula without sub-iteration.
No conjugacy choice: a conjugacy strategy is not necessary thanks to the subspace nature of the algorithms. The mmcg algorithm use a Polak-Ribière formula.
Generic and flexible: there is no restriction on the number of regularizer, their type, .., as well as for data adequacy.
Provided base class for objectives and losses allowing easy and fast implementation.
Comes with examples of implemented linear operator.
Installation and documentation
Q-MM is essentially just one file qmm.py. We recommend using poetry for installation
poetry add qmm
The package can also be installed with pip. More options are described in the documentation.
Q-MM only depends on numpy and Python 3.6.
Example
The demo.py presents an example on image deconvolution. The first step is to implement the operators V and the adjoint Vᵗ as callable (function or methods). The user is in charge of these operators and these callable must accept a unique parameter x and a unique return value. There is no constraints on the shape, everything is vectorized internally.
After import of qmm, user must instantiate Potential objects that implement φ and Objective object that implements μ ψ(V·x - ω)
from qmm import qmm
phi = qmm.Huber(delta=10) # φ
data_adeq = qmm.QuadObjective(H, Ht, HtH, data=data) # ||y - H·x||²
prior = qmm.Objective(V, Vt, phi, hyper=0.01) # μ ψ(V·x) = μ ∑ᵢ φ(vᵢᵗ·x)
Then you can run the algorithm
res = qmm.mmmg([data_adeq, prior], init, max_iter=200)
where [data_adeq, prior]
means that the two objective functions are
summed. For more details, see documentation.
Contribute
Source code: https://github.com/forieux/qmm
Issue tracker: https://github.com/forieux/qmm/issues
Acknowledgement
Author would like to thanks J. Idier, S. Moussaoui and É. Chouzenoux. É. Chouzenoux has also a Matlab package that implements 3MG for image deconvolution that can be found on her webpage.
License
The project is licensed under the GPLv3 license.
TODO
Add preconditionner to mmmg.
Logo ?
Changelog
v0.3.2
rename Criterion to Objective.
rename Potential to Loss.
add lastv attribut to BaseObjv that equals to the objective value after last gradient evaluation.
add calc_fun flag to compute criterion value with low overhead.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.