Content deleted Content added
Fixing links |
Citation bot (talk | contribs) Alter: url, pmc, pages. URLs might have been anonymized. Add: jstor, doi, arxiv, bibcode, isbn, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Category:CS1 maint: PMC format | #UCB_Category 4/11 |
||
Line 11:
| caption2 = Example of application of the Chambolle-Pock algorithm to image reconstruction.
}}
In [[mathematics]], the '''Chambolle-Pock algorithm''' is an [[algorithm]] used to solve [[convex optimization]] problems. It was introduced by Antonin Chambolle and Thomas Pock<ref name=":0">{{Cite journal |
The Chambolle-Pock algorithm is specifically designed to efficiently solve convex optimization problems that involve the minimization of a non-smooth [[Loss function|cost function]] composed of a data fidelity term and a regularization term.<ref name=":0" /> This is a typical configuration that commonly arises in ill-posed imaging [[Inverse problem|inverse problems]] such as [[image reconstruction]],<ref name=":1">{{Cite journal |
The algorithm is based on a primal-dual formulation, which allows for simultaneous updates of primal and [[Duality (mathematics)|dual]] variables. By employing the [[proximal operator]], the Chambolle-Pock algorithm efficiently handles non-smooth and non-convex regularization terms, such as the [[total variation]], specific in imaging framework.<ref name=":0" />
Line 32:
where <math>F^*, G^*</math> and <math> K^*</math> are the dual map of <math> F, G </math> and <math> K </math>, respectively.<ref name=":0" />
Assume that the primal and the dual problems have at least a solution <math> (\hat{x}, \hat{y}) \in \mathcal{X}\times \mathcal{Y} </math>, that means they satisfies<ref name=":4">{{Cite book |
<math display="block">
Line 61:
{{nowrap|<math>k\leftarrow k+1</math>}}
'''end do'''
{{algorithm-end}}To ensure the convergence of the algorithm, it is advisable to select the step size parameters such that <math>\tau \sigma \leq \lVert L \rVert</math>, where <math> L = \lVert K \rVert </math>. This straightforward selection guarantees the convergence of the algorithm.<ref name=":0" /> Moreover, with these hypotheses it is proved that for <math>\theta = 1</math> the proposed algorithm has <math> \mathcal{O}(1/N)</math> as rate of convergence for the primal-dual gap<ref name=":0" />, that [[Yurii Nesterov|Nesterov]] showed it is optimal for the class of known structured convex optimization problems.<ref>{{Cite journal |last=Nesterov |first=Yu. |date=2005-05-01 |title=Smooth minimization of non-smooth functions |url=https://doi.org/10.1007/s10107-004-0552-5 |journal=Mathematical Programming |language=en |volume=103 |issue=1 |pages=127–152 |doi=10.1007/s10107-004-0552-5 |s2cid=2391217 |issn=1436-4646}}</ref>
The semi-implicit Arrow-Hurwicz method<ref>{{cite book |first=H. |last=Uzawa |chapter=Iterative methods for concave programming |editor1-first=K. J. |editor1-last=Arrow |editor2-first=L. |editor2-last=Hurwicz |editor3-first=H. |editor3-last=Uzawa |title=Studies in linear and nonlinear programming |url=https://archive.org/details/studiesinlinearn0000arro |url-access=registration |publisher=Stanford University Press |year=1958 }}</ref> coincides with the particular choice of <math>\theta = 0</math> in the Chambolle-Pock algorithm.<ref name=":0" />
Line 84:
'''end do'''
{{algorithm-end}}
Moreover, the convergence of the algorithm slows down when <math>L</math>, the norm of the operator <math>K</math>, cannot be estimated easily or might be very large. Choosing proper [[Preconditioner|preconditioners]] <math>T</math> and <math>\Sigma</math>, modifying the proximal operator with the introduction of the [[Inner product space#Euclidean vector space|induced norm]] through the operators <math>T</math> and <math>\Sigma</math>, the convergence of the proposed preconditioned algorithm will be ensured.<ref>{{Cite journal |
==Application==
Line 99:
| caption2 = Application of the Chambolle-Pock algorithm to the test image with noise.
}}
A typical application of this algorithm is in the image denoising framework, based on total variation<ref name=":2" />. It operates on the concept that signals containing excessive and potentially erroneous details exhibit a high total variation, which represents the integral of the absolute value gradient of the image.<ref name=":2" /> By adhering to this principle, the process aims to decrease the total variation of the signal while maintaining its similarity to the original signal, effectively eliminating unwanted details while preserving crucial features like edges. In the classical bi-dimensional discrete setting<ref>{{Cite journal |last=Chambolle |first=Antonin |date=2004-01-01 |title=An Algorithm for Total Variation Minimization and Applications |url=https://doi.org/10.1023/B:JMIV.0000011325.36760.1e |journal=Journal of Mathematical Imaging and Vision |language=en |volume=20 |issue=1 |pages=89–97 |doi=10.1023/B:JMIV.0000011325.36760.1e |s2cid=207622122 |issn=1573-7683}}</ref>, consider <math>\mathcal{X} = \mathbb{R}^{NM}</math>, where an element <math> u\in\mathcal{X} </math> represents an image with the pixels values collocated in a Cartesian grid <math>N\times M</math>.<ref name=":0" />
Define the inner product on <math> \mathcal{X} </math> as<ref name=":0" />
Line 175:
\tilde{u}_{i,j}+\tau\lambda g_{i,j}}{1+\tau \lambda}
\end{align}
</math>The image total-variation denoising problem can be also treated with other algorithms<ref>{{Cite journal |
== Implementation ==
| |||