Skip to main content

Quadratic Majorize-Minimize Python toolbox

Project description

Q-MM: A Python toolbox for Quadratic Majorization-Minimization

DOI licence pypi status version maintained Poetry Documentation Status

image

Q-MM is a Python implementation of Majorize-Minimize Quadratic optimization algorithms. Algorithms provided here come from

[1] C. Labat and J. Idier, “Convergence of Conjugate Gradient Methods with a
Closed-Form Stepsize Formula,” J Optim Theory Appl, p. 18, 2008.

and

[2] E. Chouzenoux, J. Idier, and S. Moussaoui, “A Majorize–Minimize Strategy
for Subspace Optimization Applied to Image Restoration,” IEEE Trans. on
Image Process., vol. 20, no. 6, pp. 1517–1528, Jun. 2011, doi:
10.1109/TIP.2010.2103083.

See documentation for more background. If you use this code, please cite the references above and a citation of this toolbox will also be appreciated, see below. You can also click ⭐ on the repo.

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) = ||² + μ ψ(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.

image

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.
  • Just one file if you like quick and dirty installation, but available with pip.
  • 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 Numpy array x and a unique return value (partial in the functools module in the standard library is usefull here). There is no constraints on the shape, everything is vectorized internally.

After import of qmm, user must instantiate Potential objects that implement φ and Objective objects that implement μ ψ(V·x - ω)

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]{.sourceCode} means that the two objective functions are summed. For more details, see documentation.

Contribute

Author

If you are having issues, please let us know

orieux AT l2s.centralesupelec.fr

More information about me here. F. Orieux and R. Abirizk are affiliated to the Signal and Systems Laboratory L2S.

Citation

Q-MM has a DOI with Zenodo DOI. Specific version can also be cited. Citation can be

François Orieux, & Ralph Abirizk. (2022). Q-MM: The Quadratic Majorize-Minimize
Python toolbox (v0.12.0). Zenodo. https://doi.org/10.5281/zenodo.6373070

A example of bibtex is

@software{francois_orieux_2022_6373070,
  author       = {François Orieux and Ralph Abirizk},
  title        = {Q-MM: The Quadratic Majorize-Minimize Python toolbox},
  month        = mar,
  year         = 2022,
  publisher    = {Zenodo},
  version      = {0.12.0},
  doi          = {10.5281/zenodo.6373069},
  url          = {https://doi.org/10.5281/zenodo.6373069}
}

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.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

qmm-0.18.2.tar.gz (32.4 kB view details)

Uploaded Source

Built Distribution

qmm-0.18.2-py3-none-any.whl (44.0 kB view details)

Uploaded Python 3

File details

Details for the file qmm-0.18.2.tar.gz.

File metadata

  • Download URL: qmm-0.18.2.tar.gz
  • Upload date:
  • Size: 32.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: poetry/1.8.3 CPython/3.10.12 Linux/6.5.0-41-generic

File hashes

Hashes for qmm-0.18.2.tar.gz
Algorithm Hash digest
SHA256 06db4ca73c713a835eeca3bab4b98ca2551b434e50bf249c3372f5aaebf3441a
MD5 a890c73848536fd91a081d3d40192939
BLAKE2b-256 92f297fc257003b781e410e4d960d614ca22b1bb8cbddf6a21e4bf8720e368ed

See more details on using hashes here.

File details

Details for the file qmm-0.18.2-py3-none-any.whl.

File metadata

  • Download URL: qmm-0.18.2-py3-none-any.whl
  • Upload date:
  • Size: 44.0 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: poetry/1.8.3 CPython/3.10.12 Linux/6.5.0-41-generic

File hashes

Hashes for qmm-0.18.2-py3-none-any.whl
Algorithm Hash digest
SHA256 39bc7eacc2ef161475da4c9d1a29d5ff9b5503c6b99c1a3e23dfab9f35efdcbf
MD5 0c55c694f230dca8997848b4fd10d9af
BLAKE2b-256 66b10e6f7a602e71202869fbacdea93cde799b96ac4856dde644347ef4559fe0

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page