Chambolle-Pock algorithm

<h2 id="problem-statement">Problem statement</h2>
Let be 
 
 
 
 
 
 X
 
 
 ,
 
 
 Y
 
 
 
 
 {\displaystyle {\mathcal {X}},{\mathcal {Y}}}
 
 two real <a href="/facts/Vector_space/M1pxMLx2">vector spaces</a> equipped with an <a href="/facts/Inner_product_space/HoyjElEy">inner product</a> 
 
 
 
 ⟨
 ⋅
 ,
 ⋅
 ⟩
 
 
 {\displaystyle \langle \cdot ,\cdot \rangle }
 
 and a <a href="/facts/Norm_(mathematics)/xIbR4uE1">norm</a> 
 
 
 
 ‖
 
 ⋅
 
 ‖
 =
 ⟨
 ⋅
 ,
 ⋅
 
 ⟩
 
 
 1
 2
 
 
 
 
 
 {\displaystyle \lVert \,\cdot \,\rVert =\langle \cdot ,\cdot \rangle ^{\frac {1}{2}}}
 
. From up to now, a function 
 
 
 
 F
 
 
 {\displaystyle F}
 
 is called simple if its <a href="/facts/Proximal_operator/KHXpHWHC">proximal operator</a> 
 
 
 
 
 
 prox
 
 
 τ
 F
 
 
 
 
 {\displaystyle {\text{prox}}_{\tau F}}
 
 has a <a href="/facts/Closed-form_expression/y0xCXlSk">closed-form representation</a> or can be accurately computed, for 
 
 
 
 τ
 >
 0
 
 
 {\displaystyle \tau >0}
 
,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> where 
 
 
 
 
 
 prox
 
 
 τ
 F
 
 
 
 
 {\displaystyle {\text{prox}}_{\tau F}}
 
 is referred to

x
        =
        
          
            prox
          
          
            τ
            F
          
        
        (
        
          
            
              x
              ~
            
          
        
        )
        =
        
          arg 
        
        
          min
          
            
              x
              ′
            
            ∈
            
              
                X
              
            
          
        
        
          {
          
            
              
                
                  ‖
                  
                    x
                    ′
                  
                  −
                  
                    
                      
                        x
                        ~
                      
                    
                  
                  
                    ‖
                    
                      2
                    
                  
                
                
                  2
                  τ
                
              
            
            +
            F
            (
            
              x
              ′
            
            )
          
          }
        
      
    
    {\displaystyle x={\text{prox}}_{\tau F}({\tilde {x}})={\text{arg }}\min _{x'\in {\mathcal {X}}}\left\{{\frac {\lVert x'-{\tilde {x}}\rVert ^{2}}{2\tau }}+F(x')\right\}}

Consider the following constrained primal problem:<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

min
          
            x
            ∈
            
              
                X
              
            
          
        
        F
        (
        K
        x
        )
        +
        G
        (
        x
        )
      
    
    {\displaystyle \min _{x\in {\mathcal {X}}}F(Kx)+G(x)}

where 
 
 
 
 K
 :
 
 
 X
 
 
 →
 
 
 Y
 
 
 
 
 {\displaystyle K:{\mathcal {X}}\rightarrow {\mathcal {Y}}}
 
 is a <a href="/facts/Bounded_operator/LYmDTIqR">bounded linear operator</a>, 
 
 
 
 F
 :
 
 
 Y
 
 
 →
 [
 0
 ,
 +
 ∞
 )
 ,
 G
 :
 
 
 X
 
 
 →
 [
 0
 ,
 +
 ∞
 )
 
 
 {\displaystyle F:{\mathcal {Y}}\rightarrow [0,+\infty ),G:{\mathcal {X}}\rightarrow [0,+\infty )}
 
 are <a href="/facts/Convex_function/IbzG5SLF">convex</a>, <a href="/facts/Semi-continuity/4unJbWdW">lower semicontinuous</a> and simple.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
The minimization problem has its dual corresponding problem as<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

max
          
            y
            ∈
            
              
                Y
              
            
          
        
        −
        
          (
          
            
              G
              
                ∗
              
            
            (
            −
            
              K
              
                ∗
              
            
            y
            )
            +
            
              F
              
                ∗
              
            
            (
            y
            )
          
          )
        
      
    
    {\displaystyle \max _{y\in {\mathcal {Y}}}-\left(G^{*}(-K^{*}y)+F^{*}(y)\right)}

where 
 
 
 
 
 F
 
 ∗
 
 
 ,
 
 G
 
 ∗
 
 
 
 
 {\displaystyle F^{*},G^{*}}
 
 and 
 
 
 
 
 K
 
 ∗
 
 
 
 
 {\displaystyle K^{*}}
 
 are the dual map of 
 
 
 
 F
 ,
 G
 
 
 {\displaystyle F,G}
 
 and 
 
 
 
 K
 
 
 {\displaystyle K}
 
, respectively.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>
Assume that the primal and the dual problems have at least a solution 
 
 
 
 (
 
 
 
 x
 ^
 
 
 
 ,
 
 
 
 y
 ^
 
 
 
 )
 ∈
 
 
 X
 
 
 ×
 
 
 Y
 
 
 
 
 {\displaystyle ({\hat {x}},{\hat {y}})\in {\mathcal {X}}\times {\mathcal {Y}}}
 
, that means they satisfies<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

 
 
 
 
 
 
 
 K
 
 
 
 x
 ^
 
 
 
 
 
 
 ∈
 ∂
 
 F
 
 ∗
 
 
 (
 
 
 
 y
 ^
 
 
 
 )
 
 
 
 
 −
 (
 
 K
 
 ∗
 
 
 
 
 
 y
 ^
 
 
 
 )
 
 
 
 ∈
 ∂
 G
 (
 
 
 
 x
 ^
 
 
 
 )
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}K{\hat {x}}&\in \partial F^{*}({\hat {y}})\\-(K^{*}{\hat {y}})&\in \partial G({\hat {x}})\end{aligned}}}

where 
 
 
 
 ∂
 
 F
 
 ∗
 
 
 
 
 {\displaystyle \partial F^{*}}
 
 and 
 
 
 
 ∂
 G
 
 
 {\displaystyle \partial G}
 
 are the <a href="/facts/Subderivative/IK3s3Cqw">subgradient</a> of the convex functions 
 
 
 
 
 F
 
 ∗
 
 
 
 
 {\displaystyle F^{*}}
 
 and 
 
 
 
 G
 
 
 {\displaystyle G}
 
, respectively.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
The Chambolle-Pock algorithm solves the so-called <a href="/facts/Saddle-point_theorem/ly7g2zST">saddle-point problem</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

min
          
            x
            ∈
            
              
                X
              
            
          
        
        
          max
          
            y
            ∈
            
              
                Y
              
            
          
        
        ⟨
        K
        x
        ,
        y
        ⟩
        +
        G
        (
        x
        )
        −
        
          F
          
            ∗
          
        
        (
        y
        )
      
    
    {\displaystyle \min _{x\in {\mathcal {X}}}\max _{y\in {\mathcal {Y}}}\langle Kx,y\rangle +G(x)-F^{*}(y)}

which is a <a href="/facts/Interior-point_method/prIIrceN">primal-dual</a> formulation of the nonlinear primal and dual problems stated before.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h2 id="algorithm">Algorithm</h2>
The Chambolle-Pock algorithm primarily involves iteratively alternating between ascending in the dual variable 
 
 
 
 y
 
 
 {\displaystyle y}
 
 and descending in the primal variable 
 
 
 
 x
 
 
 {\displaystyle x}
 
 using a <a href="/facts/Gradient_method/xwxAR6hM">gradient</a>-like approach, with step sizes 
 
 
 
 σ
 
 
 {\displaystyle \sigma }
 
 and 
 
 
 
 τ
 
 
 {\displaystyle \tau }
 
 respectively, in order to simultaneously solve the primal and the dual problem.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> Furthermore, an over-<a href="/facts/Relaxation_(iterative_method)/9tsBUvxs">relaxation</a> technique is employed for the primal variable with the parameter 
 
 
 
 θ
 
 
 {\displaystyle \theta }
 
.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
Algorithm Chambolle-Pock algorithm
Input: 
 
 
 
 F
 ,
 G
 ,
 K
 ,
 τ
 ,
 σ
 >
 0
 ,
 
 θ
 ∈
 [
 0
 ,
 1
 ]
 ,
 
 (
 
 x
 
 0
 
 
 ,
 
 y
 
 0
 
 
 )
 ∈
 
 
 X
 
 
 ×
 
 
 Y
 
 
 
 
 {\displaystyle F,G,K,\tau ,\sigma >0,\,\theta \in [0,1],\,(x^{0},y^{0})\in {\mathcal {X}}\times {\mathcal {Y}}}
 
 and set 
 
 
 
 
 
 
 x
 ¯
 
 
 
 0
 
 
 =
 
 x
 
 0
 
 
 
 
 {\displaystyle {\overline {x}}^{0}=x^{0}}
 
, stopping criterion.

k
        ←
        0
      
    
    {\displaystyle k\leftarrow 0}

do while stopping criterion not satisfied
 
 
 
 
 
 y
 
 n
 +
 1
 
 
 ←
 
 
 prox
 
 
 σ
 
 F
 
 ∗
 
 
 
 
 
 (
 
 
 y
 
 n
 
 
 +
 σ
 K
 
 
 
 x
 ¯
 
 
 
 n
 
 
 
 )
 
 
 
 {\displaystyle y^{n+1}\leftarrow {\text{prox}}_{\sigma F^{*}}\left(y^{n}+\sigma K{\overline {x}}^{n}\right)}

x
          
            n
            +
            1
          
        
        ←
        
          
            prox
          
          
            τ
            G
          
        
        
          (
          
            
              x
              
                n
              
            
            −
            τ
            
              K
              
                ∗
              
            
            
              y
              
                n
                +
                1
              
            
          
          )
        
      
    
    {\displaystyle x^{n+1}\leftarrow {\text{prox}}_{\tau G}\left(x^{n}-\tau K^{*}y^{n+1}\right)}

x
              ¯
            
          
          
            n
            +
            1
          
        
        ←
        
          x
          
            n
            +
            1
          
        
        +
        θ
        
          (
          
            
              x
              
                n
                +
                1
              
            
            −
            
              x
              
                n
              
            
          
          )
        
      
    
    {\displaystyle {\overline {x}}^{n+1}\leftarrow x^{n+1}+\theta \left(x^{n+1}-x^{n}\right)}

k
        ←
        k
        +
        1
      
    
    {\displaystyle k\leftarrow k+1}

end do

<ul><li>"←" denotes <a href="/facts/Assignment_(computer_science)/kLevAoyJ">assignment</a>. For instance, "largest ← item" means that the value of largest changes to the value of item.</li>
<li>"return" terminates the algorithm and outputs the following value.</li></ul>

Chambolle and Pock proved<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> that the algorithm converges if 
 
 
 
 θ
 =
 1
 
 
 {\displaystyle \theta =1}
 
 and 
 
 
 
 τ
 σ
 ‖
 K
 
 ‖
 
 2
 
 
 ≤
 1
 
 
 {\displaystyle \tau \sigma \lVert K\rVert ^{2}\leq 1}
 
, sequentially and with 
 
 
 
 
 
 O
 
 
 (
 1
 
 /
 
 N
 )
 
 
 {\displaystyle {\mathcal {O}}(1/N)}
 
 as rate of convergence for the primal-dual gap. This has been extended by S. Banert et al.<a class="footnote-ref" id="fnref:24" href="#fn:24">24</a> to hold whenever 
 
 
 
 θ
 >
 1
 
 /
 
 2
 
 
 {\displaystyle \theta >1/2}
 
 and 
 
 
 
 τ
 σ
 ‖
 K
 
 ‖
 
 2
 
 
 <
 4
 
 /
 
 (
 1
 +
 2
 θ
 )
 
 
 {\displaystyle \tau \sigma \lVert K\rVert ^{2}<4/(1+2\theta )}
 
. 
The semi-implicit Arrow-Hurwicz method<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> coincides with the particular choice of 
 
 
 
 θ
 =
 0
 
 
 {\displaystyle \theta =0}
 
 in the Chambolle-Pock algorithm.<a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>

<h2 id="acceleration">Acceleration</h2>
There are special cases in which the rate of convergence has a theoretical speed up.<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a> In fact, if 
 
 
 
 G
 
 
 {\displaystyle G}
 
, respectively 
 
 
 
 
 F
 
 ∗
 
 
 
 
 {\displaystyle F^{*}}
 
, is <a href="/facts/Convex_function/IbzG5SLF">uniformly convex</a> then 
 
 
 
 
 G
 
 ∗
 
 
 
 
 {\displaystyle G^{*}}
 
, respectively 
 
 
 
 F
 
 
 {\displaystyle F}
 
, has a <a href="/facts/Lipschitz_continuity/Hw20EPEU">Lipschitz continuous</a> gradient. Then, the rate of convergence can be improved to 
 
 
 
 
 
 O
 
 
 (
 1
 
 /
 
 
 N
 
 2
 
 
 )
 
 
 {\displaystyle {\mathcal {O}}(1/N^{2})}
 
, providing a slightly changes in the Chambolle-Pock algorithm. It leads to an accelerated version of the method and it consists in choosing iteratively 
 
 
 
 
 τ
 
 n
 
 
 ,
 
 σ
 
 n
 
 
 
 
 {\displaystyle \tau _{n},\sigma _{n}}
 
, and also 
 
 
 
 
 θ
 
 n
 
 
 
 
 {\displaystyle \theta _{n}}
 
, instead of fixing these values.<a class="footnote-ref" id="fnref:28" href="#fn:28">28</a>
In case of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 uniformly convex, with 
 
 
 
 γ
 >
 0
 
 
 {\displaystyle \gamma >0}
 
 the uniform-convexity constant, the modified algorithm becomes<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>

Algorithm Accelerated Chambolle-Pock algorithm
Input: 
 
 
 
 F
 ,
 G
 ,
 
 τ
 
 0
 
 
 ,
 
 σ
 
 0
 
 
 >
 0
 
 
 {\displaystyle F,G,\tau _{0},\sigma _{0}>0}
 
 such that 
 
 
 
 
 τ
 
 0
 
 
 
 σ
 
 0
 
 
 
 L
 
 2
 
 
 ≤
 1
 ,
 
 (
 
 x
 
 0
 
 
 ,
 
 y
 
 0
 
 
 )
 ∈
 
 
 X
 
 
 ×
 
 
 Y
 
 
 
 
 {\displaystyle \tau _{0}\sigma _{0}L^{2}\leq 1,\,(x^{0},y^{0})\in {\mathcal {X}}\times {\mathcal {Y}}}
 
 and set 
 
 
 
 
 
 
 x
 ¯
 
 
 
 0
 
 
 =
 
 x
 
 0
 
 
 .
 
 
 {\displaystyle {\overline {x}}^{0}=x^{0}.}
 
, stopping criterion.

k
        ←
        0
      
    
    {\displaystyle k\leftarrow 0}

do while stopping criterion not satisfied
 
 
 
 
 
 y
 
 n
 +
 1
 
 
 ←
 
 
 prox
 
 
 
 σ
 
 n
 
 
 
 F
 
 ∗
 
 
 
 
 
 (
 
 
 y
 
 n
 
 
 +
 
 σ
 
 n
 
 
 K
 
 
 
 x
 ¯
 
 
 
 n
 
 
 
 )
 
 
 
 {\displaystyle y^{n+1}\leftarrow {\text{prox}}_{\sigma _{n}F^{*}}\left(y^{n}+\sigma _{n}K{\overline {x}}^{n}\right)}

x
          
            n
            +
            1
          
        
        ←
        
          
            prox
          
          
            
              τ
              
                n
              
            
            G
          
        
        
          (
          
            
              x
              
                n
              
            
            −
            
              τ
              
                n
              
            
            
              K
              
                ∗
              
            
            
              y
              
                n
                +
                1
              
            
          
          )
        
      
    
    {\displaystyle x^{n+1}\leftarrow {\text{prox}}_{\tau _{n}G}\left(x^{n}-\tau _{n}K^{*}y^{n+1}\right)}

θ
          
            n
          
        
        ←
        
          
            1
            
              1
              +
              2
              γ
              
                τ
                
                  n
                
              
            
          
        
      
    
    {\displaystyle \theta _{n}\leftarrow {\frac {1}{\sqrt {1+2\gamma \tau _{n}}}}}

τ
          
            n
            +
            1
          
        
        ←
        
          θ
          
            n
          
        
        
          τ
          
            n
          
        
      
    
    {\displaystyle \tau _{n+1}\leftarrow \theta _{n}\tau _{n}}

σ
          
            n
            +
            1
          
        
        ←
        
          
            
              σ
              
                n
              
            
            
              θ
              
                n
              
            
          
        
      
    
    {\displaystyle \sigma _{n+1}\leftarrow {\frac {\sigma _{n}}{\theta _{n}}}}

x
              ¯
            
          
          
            n
            +
            1
          
        
        ←
        
          x
          
            n
            +
            1
          
        
        +
        
          θ
          
            n
          
        
        
          (
          
            
              x
              
                n
                +
                1
              
            
            −
            
              x
              
                n
              
            
          
          )
        
      
    
    {\displaystyle {\overline {x}}^{n+1}\leftarrow x^{n+1}+\theta _{n}\left(x^{n+1}-x^{n}\right)}

k
        ←
        k
        +
        1
      
    
    {\displaystyle k\leftarrow k+1}

end do

Moreover, the convergence of the algorithm slows down when 
 
 
 
 L
 
 
 {\displaystyle L}
 
, the norm of the operator 
 
 
 
 K
 
 
 {\displaystyle K}
 
, cannot be estimated easily or might be very large. Choosing proper <a href="/facts/Preconditioner/MUvFta7g">preconditioners</a> 
 
 
 
 T
 
 
 {\displaystyle T}
 
 and 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
, modifying the proximal operator with the introduction of the <a href="/facts/Inner_product_space/HoyjElEy">induced norm</a> through the operators 
 
 
 
 T
 
 
 {\displaystyle T}
 
 and 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
, the convergence of the proposed preconditioned algorithm will be ensured.<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a>

<h2 id="application">Application</h2>

A typical application of this algorithm is in the image <a href="/facts/Noise_reduction/9jrDQnAN">denoising</a> framework, based on total variation.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a> 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.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a> 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,<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a> consider 
 
 
 
 
 
 X
 
 
 =
 
 
 R
 
 
 N
 M
 
 
 
 
 {\displaystyle {\mathcal {X}}=\mathbb {R} ^{NM}}
 
, where an element 
 
 
 
 u
 ∈
 
 
 X
 
 
 
 
 {\displaystyle u\in {\mathcal {X}}}
 
 represents an image with the pixels values collocated in a Cartesian grid 
 
 
 
 N
 ×
 M
 
 
 {\displaystyle N\times M}
 
.<a class="footnote-ref" id="fnref:34" href="#fn:34">34</a> 
Define the inner product on 
 
 
 
 
 
 X
 
 
 
 
 {\displaystyle {\mathcal {X}}}
 
 as<a class="footnote-ref" id="fnref:35" href="#fn:35">35</a>

⟨
        u
        ,
        v
        
          ⟩
          
            
              X
            
          
        
        =
        
          ∑
          
            i
            ,
            j
          
        
        
          u
          
            i
            ,
            j
          
        
        
          v
          
            i
            ,
            j
          
        
        ,
        
        u
        ,
        v
        ∈
        
          
            X
          
        
      
    
    {\displaystyle \langle u,v\rangle _{\mathcal {X}}=\sum _{i,j}u_{i,j}v_{i,j},\quad u,v\in {\mathcal {X}}}

that induces an 
 
 
 
 
 L
 
 2
 
 
 
 
 {\displaystyle L^{2}}
 
 norm on 
 
 
 
 
 
 X
 
 
 
 
 {\displaystyle {\mathcal {X}}}
 
, denoted as 
 
 
 
 ‖
 
 ⋅
 
 
 ‖
 
 2
 
 
 
 
 {\displaystyle \lVert \,\cdot \,\rVert _{2}}
 
.<a class="footnote-ref" id="fnref:36" href="#fn:36">36</a>
Hence, the gradient of 
 
 
 
 u
 
 
 {\displaystyle u}
 
 is computed with the standard <a href="/facts/Finite_difference/aY1txFhj">finite differences</a>,

(
            
              ∇
              u
            
            )
          
          
            i
            ,
            j
          
        
        =
        
          (
          
            
              
                
                  
                    
                      (
                      
                        ∇
                        u
                      
                      )
                    
                    
                      i
                      ,
                      j
                    
                    
                      1
                    
                  
                
              
              
                
                  
                    
                      (
                      
                        ∇
                        u
                      
                      )
                    
                    
                      i
                      ,
                      j
                    
                    
                      2
                    
                  
                
              
            
          
          )
        
      
    
    {\displaystyle \left(\nabla u\right)_{i,j}=\left({\begin{aligned}\left(\nabla u\right)_{i,j}^{1}\\\left(\nabla u\right)_{i,j}^{2}\end{aligned}}\right)}

which is an element of the space 
 
 
 
 
 
 Y
 
 
 =
 
 
 X
 
 
 ×
 
 
 X
 
 
 
 
 {\displaystyle {\mathcal {Y}}={\mathcal {X}}\times {\mathcal {X}}}
 
, where<a class="footnote-ref" id="fnref:37" href="#fn:37">37</a>

(
 
 ∇
 u
 
 )
 
 
 i
 ,
 j
 
 
 1
 
 
 =
 
 {
 
 
 
 
 
 
 
 
 
 u
 
 i
 +
 1
 ,
 j
 
 
 −
 
 u
 
 i
 ,
 j
 
 
 
 h
 
 
 
 
 
  if 
 
 i
 <
 M
 
 
 
 
 
 0
 
 
 
  if 
 
 i
 =
 M
 
 
 
 
 
 
 ,
 
 
 
 
 
 
 
 (
 
 ∇
 u
 
 )
 
 
 i
 ,
 j
 
 
 2
 
 
 =
 
 {
 
 
 
 
 
 
 
 
 
 u
 
 i
 ,
 j
 +
 1
 
 
 −
 
 u
 
 i
 ,
 j
 
 
 
 h
 
 
 
 
 
  if 
 
 j
 <
 N
 
 
 
 
 
 0
 
 
 
  if 
 
 j
 =
 N
 
 
 
 
 
 
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}&\left(\nabla u\right)_{i,j}^{1}=\left\{{\begin{aligned}&{\frac {u_{i+1,j}-u_{i,j}}{h}}&{\text{ if }}i<M\\&0&{\text{ if }}i=M\end{aligned}}\right.,\\&\left(\nabla u\right)_{i,j}^{2}=\left\{{\begin{aligned}&{\frac {u_{i,j+1}-u_{i,j}}{h}}&{\text{ if }}j<N\\&0&{\text{ if }}j=N\end{aligned}}\right.\end{aligned}}}

On 
 
 
 
 
 
 Y
 
 
 
 
 {\displaystyle {\mathcal {Y}}}
 
 is defined an <a href="/facts/Square-integrable_function/IASblcJJ">
 
 
 
 
 L
 
 1
 
 
 −
 
 
 {\displaystyle L^{1}-}
 
 based norm</a> as<a class="footnote-ref" id="fnref:38" href="#fn:38">38</a>

‖
        p
        
          ‖
          
            1
          
        
        =
        
          ∑
          
            i
            ,
            j
          
        
        
          
            
              
                (
                
                  p
                  
                    i
                    ,
                    j
                  
                  
                    1
                  
                
                )
              
              
                2
              
            
            +
            
              
                (
                
                  p
                  
                    i
                    ,
                    j
                  
                  
                    2
                  
                
                )
              
              
                2
              
            
          
        
        ,
        
        p
        ∈
        
          
            Y
          
        
        .
      
    
    {\displaystyle \lVert p\rVert _{1}=\sum _{i,j}{\sqrt {\left(p_{i,j}^{1}\right)^{2}+\left(p_{i,j}^{2}\right)^{2}}},\quad p\in {\mathcal {Y}}.}

Then, the primal problem of the <a href="/facts/Total_variation_denoising/rKa5n2wI">ROF model</a>, proposed by Rudin, <a href="/facts/Stanley_Osher/WUpFSKbd">Osher</a>, and Fatemi,<a class="footnote-ref" id="fnref:39" href="#fn:39">39</a> is given by<a class="footnote-ref" id="fnref:40" href="#fn:40">40</a>

h
          
            2
          
        
        
          min
          
            u
            ∈
            
              
                X
              
            
          
        
        ‖
        ∇
        u
        
          ‖
          
            1
          
        
        +
        
          
            λ
            2
          
        
        ‖
        u
        −
        g
        
          ‖
          
            2
          
          
            2
          
        
      
    
    {\displaystyle h^{2}\min _{u\in {\mathcal {X}}}\lVert \nabla u\rVert _{1}+{\frac {\lambda }{2}}\lVert u-g\rVert _{2}^{2}}

where 
 
 
 
 u
 ∈
 
 
 X
 
 
 
 
 {\displaystyle u\in {\mathcal {X}}}
 
 is the unknown solution and 
 
 
 
 g
 ∈
 
 
 X
 
 
 
 
 {\displaystyle g\in {\mathcal {X}}}
 
 the given noisy data, instead 
 
 
 
 λ
 
 
 {\displaystyle \lambda }
 
 describes the trade-off between regularization and data fitting.<a class="footnote-ref" id="fnref:41" href="#fn:41">41</a>
The primal-dual formulation of the ROF problem is formulated as follow<a class="footnote-ref" id="fnref:42" href="#fn:42">42</a>

min
          
            u
            ∈
            
              
                X
              
            
          
        
        
          max
          
            p
            ∈
            
              
                Y
              
            
          
        
        −
        ⟨
        u
        ,
        
          div
        
        
        p
        
          ⟩
          
            
              X
            
          
        
        +
        
          
            λ
            2
          
        
        ‖
        u
        −
        g
        
          ‖
          
            2
          
          
            2
          
        
        −
        
          δ
          
            P
          
        
        (
        p
        )
      
    
    {\displaystyle \min _{u\in {\mathcal {X}}}\max _{p\in {\mathcal {Y}}}-\langle u,{\text{div}}\,p\rangle _{\mathcal {X}}+{\frac {\lambda }{2}}\lVert u-g\rVert _{2}^{2}-\delta _{P}(p)}

where the indicator function is defined as<a class="footnote-ref" id="fnref:43" href="#fn:43">43</a>

δ
          
            P
          
        
        (
        p
        )
        =
        
          {
          
            
              
                
                
                  0
                  ,
                
                
                  
                    if 
                  
                  p
                  ∈
                  P
                
              
              
                
                
                  
                  +
                  ∞
                  ,
                
                
                  
                    if 
                  
                  p
                  ∉
                  P
                
              
            
          
          
        
      
    
    {\displaystyle \delta _{P}(p)=\left\{{\begin{aligned}&0,&{\text{if }}p\in P\\&+\infty ,&{\text{if }}p\notin P\end{aligned}}\right.}

on the convex set 
 
 
 
 P
 =
 
 {
 
 p
 ∈
 
 
 Y
 
 
 
 :
 
 
 max
 
 i
 ,
 j
 
 
 
 
 
 
 (
 
 p
 
 i
 ,
 j
 
 
 1
 
 
 )
 
 
 2
 
 
 +
 
 
 (
 
 p
 
 i
 ,
 j
 
 
 2
 
 
 )
 
 
 2
 
 
 
 
 ≤
 1
 
 }
 
 ,
 
 
 {\displaystyle P=\left\{p\in {\mathcal {Y}}\,:\,\max _{i,j}{\sqrt {\left(p_{i,j}^{1}\right)^{2}+\left(p_{i,j}^{2}\right)^{2}}}\leq 1\right\},}
 
 which can be seen as 
 
 
 
 
 L
 
 ∞
 
 
 
 
 {\displaystyle L^{\infty }}
 
 unitary balls with respect to the defined norm on 
 
 
 
 
 
 Y
 
 
 
 
 {\displaystyle {\mathcal {Y}}}
 
.<a class="footnote-ref" id="fnref:44" href="#fn:44">44</a> 
Observe that the functions involved in the stated primal-dual formulation are simple, since their proximal operator can be easily computed<a class="footnote-ref" id="fnref:45" href="#fn:45">45</a>
 
 
 
 
 
 
 
 p
 
 
 
 =
 
 
 prox
 
 
 σ
 
 F
 
 ∗
 
 
 
 
 (
 
 
 
 p
 ~
 
 
 
 )
 
 
 
 ⟺
 
 
 p
 
 i
 ,
 j
 
 
 
 
 
 =
 
 
 
 
 
 
 p
 ~
 
 
 
 
 i
 ,
 j
 
 
 
 max
 {
 1
 ,
 
 |
 
 
 
 
 
 p
 ~
 
 
 
 
 i
 ,
 j
 
 
 
 |
 
 }
 
 
 
 
 
 
 
 u
 
 
 
 =
 
 
 prox
 
 
 τ
 G
 
 
 (
 
 
 
 u
 ~
 
 
 
 )
 
 
 
 ⟺
 
 
 u
 
 i
 ,
 j
 
 
 
 
 
 =
 
 
 
 
 
 
 
 u
 ~
 
 
 
 
 i
 ,
 j
 
 
 +
 τ
 λ
 
 g
 
 i
 ,
 j
 
 
 
 
 1
 +
 τ
 λ
 
 
 
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}p&={\text{prox}}_{\sigma F^{*}}({\tilde {p}})&\iff p_{i,j}&={\frac {{\tilde {p}}_{i,j}}{\max\{1,|{\tilde {p}}_{i,j}|\}}}\\u&={\text{prox}}_{\tau G}({\tilde {u}})&\iff u_{i,j}&={\frac {{\tilde {u}}_{i,j}+\tau \lambda g_{i,j}}{1+\tau \lambda }}\end{aligned}}}
 
The image total-variation denoising problem can be also treated with other algorithms<a class="footnote-ref" id="fnref:46" href="#fn:46">46</a> such as the <a href="/facts/Augmented_Lagrangian_method/8zamSYrl">alternating direction method of multipliers</a> (ADMM),<a class="footnote-ref" id="fnref:47" href="#fn:47">47</a> <a href="/facts/Proximal_gradient_methods_for_learning/G2zt3d09">projected (sub)-gradient</a><a class="footnote-ref" id="fnref:48" href="#fn:48">48</a> or fast iterative shrinkage thresholding.<a class="footnote-ref" id="fnref:49" href="#fn:49">49</a>

<h2 id="implementation">Implementation</h2>
<ul><li>The Manopt.jl<a class="footnote-ref" id="fnref:50" href="#fn:50">50</a> package implements the algorithm in <a href="/facts/Julia_(programming_language)/AoB0PJ9C">Julia</a></li>
<li><a href="/facts/Gabriel_Peyr%C3%A9/pgA2gDwb">Gabriel Peyré</a> implements the algorithm in <a href="/facts/MATLAB/qPjLISCk">MATLAB</a>,<a class="footnote-ref" id="fnref:51" href="#fn:51">51</a> Julia, <a href="/facts/R_(programming_language)/LSrkr8K8">R</a> and <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a><a class="footnote-ref" id="fnref:52" href="#fn:52">52</a></li>
<li>In the Operator Discretization Library (ODL),<a class="footnote-ref" id="fnref:53" href="#fn:53">53</a> a Python library for inverse problems, chambolle_pock_solver implements the method.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Augmented_Lagrangian_method/8zamSYrl">Alternating direction method of multipliers</a></li>
<li><a href="/facts/Convex_optimization/7D6U4MTN">Convex optimization</a></li>
<li><a href="/facts/Proximal_operator/KHXpHWHC">Proximal operator</a></li>
<li><a href="/facts/Total_variation_denoising/rKa5n2wI">Total variation denoising</a></li></ul>
<h2 id="notes">Notes</h2>

<h2 id="further-reading">Further reading</h2>
<ul><li>Boyd, Stephen; Vandenberghe, Lieven (2004). <a href="https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf">Convex Optimization</a> (PDF). Cambridge University Press.</li>
<li>Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-89871-382-4.</li>
<li>Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-98793-4.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.stanford.edu/class/ee364b/">EE364b</a>, a Stanford course homepage.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Sidky, Emil Y; Jørgensen, Jakob H; Pan, Xiaochuan (2012-05-21). "Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm". Physics in Medicine and Biology. 57 (10): 3065–3091. arXiv:1111.5632. Bibcode:2012PMB....57.3065S. doi:10.1088/0031-9155/57/10/3065. ISSN 0031-9155. PMC 3370658. PMID 22538474. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). "Single Image Dehazing and Denoising: A Fast Variational Approach". SIAM Journal on Imaging Sciences. 7 (2): 969–996. doi:10.1137/130919696. ISSN 1936-4954. <a href="http://epubs.siam.org/doi/10.1137/130919696" target="_blank">http://epubs.siam.org/doi/10.1137/130919696</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Allag, A.; Benammar, A.; Drai, R.; Boutkedjirt, T. (2019-07-01). "Tomographic Image Reconstruction in the Case of Limited Number of X-Ray Projections Using Sinogram Inpainting". Russian Journal of Nondestructive Testing. 55 (7): 542–548. doi:10.1134/S1061830919070027. ISSN 1608-3385. S2CID 203437503. <a href="https://doi.org/10.1134/S1061830919070027" target="_blank">https://doi.org/10.1134/S1061830919070027</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Pock, Thomas; Cremers, Daniel; Bischof, Horst; Chambolle, Antonin (2009). "An algorithm for minimizing the Mumford-Shah functional". 2009 IEEE 12th International Conference on Computer Vision. pp. 1133–1140. doi:10.1109/ICCV.2009.5459348. ISBN 978-1-4244-4420-5. S2CID 15991312. <a href="978-1-4244-4420-5" target="_blank">978-1-4244-4420-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"A Generic Proximal Algorithm for Convex Optimization—Application to Total Variation Minimization". IEEE Signal Processing Letters. 21 (8): 985–989. 2014. Bibcode:2014ISPL...21..985.. doi:10.1109/LSP.2014.2322123. ISSN 1070-9908. S2CID 8976837. <a href="https://ieeexplore.ieee.org/document/6810809" target="_blank">https://ieeexplore.ieee.org/document/6810809</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Sidky, Emil Y; Jørgensen, Jakob H; Pan, Xiaochuan (2012-05-21). "Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm". Physics in Medicine and Biology. 57 (10): 3065–3091. arXiv:1111.5632. Bibcode:2012PMB....57.3065S. doi:10.1088/0031-9155/57/10/3065. ISSN 0031-9155. PMC 3370658. PMID 22538474. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). "Single Image Dehazing and Denoising: A Fast Variational Approach". SIAM Journal on Imaging Sciences. 7 (2): 969–996. doi:10.1137/130919696. ISSN 1936-4954. <a href="http://epubs.siam.org/doi/10.1137/130919696" target="_blank">http://epubs.siam.org/doi/10.1137/130919696</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Allag, A.; Benammar, A.; Drai, R.; Boutkedjirt, T. (2019-07-01). "Tomographic Image Reconstruction in the Case of Limited Number of X-Ray Projections Using Sinogram Inpainting". Russian Journal of Nondestructive Testing. 55 (7): 542–548. doi:10.1134/S1061830919070027. ISSN 1608-3385. S2CID 203437503. <a href="https://doi.org/10.1134/S1061830919070027" target="_blank">https://doi.org/10.1134/S1061830919070027</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Ekeland, Ivar; Témam, Roger (1999). Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics. p. 61. doi:10.1137/1.9781611971088. ISBN 978-0-89871-450-0. <a href="978-0-89871-450-0" target="_blank">978-0-89871-450-0</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Ekeland, Ivar; Témam, Roger (1999). Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics. p. 61. doi:10.1137/1.9781611971088. ISBN 978-0-89871-450-0. <a href="978-0-89871-450-0" target="_blank">978-0-89871-450-0</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Sidky, Emil Y; Jørgensen, Jakob H; Pan, Xiaochuan (2012-05-21). "Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm". Physics in Medicine and Biology. 57 (10): 3065–3091. arXiv:1111.5632. Bibcode:2012PMB....57.3065S. doi:10.1088/0031-9155/57/10/3065. ISSN 0031-9155. PMC 3370658. PMID 22538474. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3370658</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Banert, Sebastian; Upadhyaya, Manu; Giselsson, Pontus (2023). "The Chambolle-Pock method converges weakly with 
 
 
 
 θ
 >
 1
 
 /
 
 2
 
 
 {\displaystyle \theta >1/2}
 
 and 
 
 
 
 τ
 σ
 ‖
 L
 
 ‖
 
 2
 
 
 <
 4
 
 /
 
 (
 1
 +
 2
 θ
 )
 
 
 {\displaystyle \tau \sigma \lVert L\rVert ^{2}<4/(1+2\theta )}
 
". arXiv:2309.03998 [math.OC]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Uzawa, H. (1958). "Iterative methods for concave programming". In Arrow, K. J.; Hurwicz, L.; Uzawa, H. (eds.). Studies in linear and nonlinear programming. Stanford University Press. <a href="https://archive.org/details/studiesinlinearn0000arro" target="_blank">https://archive.org/details/studiesinlinearn0000arro</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Pock, Thomas; Chambolle, Antonin (2011-11-06). "Diagonal preconditioning for first order primal-dual algorithms in convex optimization". 2011 International Conference on Computer Vision. pp. 1762–1769. doi:10.1109/ICCV.2011.6126441. ISBN 978-1-4577-1102-2. S2CID 17485166. <a href="978-1-4577-1102-2" target="_blank">978-1-4577-1102-2</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). "Single Image Dehazing and Denoising: A Fast Variational Approach". SIAM Journal on Imaging Sciences. 7 (2): 969–996. doi:10.1137/130919696. ISSN 1936-4954. <a href="http://epubs.siam.org/doi/10.1137/130919696" target="_blank">http://epubs.siam.org/doi/10.1137/130919696</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). "Single Image Dehazing and Denoising: A Fast Variational Approach". SIAM Journal on Imaging Sciences. 7 (2): 969–996. doi:10.1137/130919696. ISSN 1936-4954. <a href="http://epubs.siam.org/doi/10.1137/130919696" target="_blank">http://epubs.siam.org/doi/10.1137/130919696</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Chambolle, Antonin (2004-01-01). "An Algorithm for Total Variation Minimization and Applications". Journal of Mathematical Imaging and Vision. 20 (1): 89–97. Bibcode:2004JMIV...20...89C. doi:10.1023/B:JMIV.0000011325.36760.1e. ISSN 1573-7683. S2CID 207622122. <a href="https://doi.org/10.1023/B:JMIV.0000011325.36760.1e" target="_blank">https://doi.org/10.1023/B:JMIV.0000011325.36760.1e</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
<li id="fn:34">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></li>
<li id="fn:35">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></li>
<li id="fn:36">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></li>
<li id="fn:37">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></li>
<li id="fn:38">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:38" class="footnote-back-ref">↩</a></li>
<li id="fn:39">Getreuer, Pascal (2012). "Rudin–Osher–Fatemi Total Variation Denoising using Split Bregman" (PDF). <a href="https://www.ipol.im/pub/art/2012/g-tvd/article_lr.pdf" target="_blank">https://www.ipol.im/pub/art/2012/g-tvd/article_lr.pdf</a> <a href="#fnref:39" class="footnote-back-ref">↩</a></li>
<li id="fn:40">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:40" class="footnote-back-ref">↩</a></li>
<li id="fn:41">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:41" class="footnote-back-ref">↩</a></li>
<li id="fn:42">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:42" class="footnote-back-ref">↩</a></li>
<li id="fn:43">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:43" class="footnote-back-ref">↩</a></li>
<li id="fn:44">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:44" class="footnote-back-ref">↩</a></li>
<li id="fn:45">Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. Bibcode:2011JMIV...40..120C. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707. <a href="https://doi.org/10.1007/s10851-010-0251-1" target="_blank">https://doi.org/10.1007/s10851-010-0251-1</a> <a href="#fnref:45" class="footnote-back-ref">↩</a></li>
<li id="fn:46">Esser, Ernie; Zhang, Xiaoqun; Chan, Tony F. (2010). "A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science". SIAM Journal on Imaging Sciences. 3 (4): 1015–1046. doi:10.1137/09076934X. ISSN 1936-4954. <a href="http://epubs.siam.org/doi/10.1137/09076934X" target="_blank">http://epubs.siam.org/doi/10.1137/09076934X</a> <a href="#fnref:46" class="footnote-back-ref">↩</a></li>
<li id="fn:47">Lions, P. L.; Mercier, B. (1979). "Splitting Algorithms for the Sum of Two Nonlinear Operators". SIAM Journal on Numerical Analysis. 16 (6): 964–979. Bibcode:1979SJNA...16..964L. doi:10.1137/0716071. ISSN 0036-1429. JSTOR 2156649. <a href="https://www.jstor.org/stable/2156649" target="_blank">https://www.jstor.org/stable/2156649</a> <a href="#fnref:47" class="footnote-back-ref">↩</a></li>
<li id="fn:48">Beck, Amir; Teboulle, Marc (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM Journal on Imaging Sciences. 2 (1): 183–202. doi:10.1137/080716542. ISSN 1936-4954. S2CID 3072879. <a href="http://epubs.siam.org/doi/10.1137/080716542" target="_blank">http://epubs.siam.org/doi/10.1137/080716542</a> <a href="#fnref:48" class="footnote-back-ref">↩</a></li>
<li id="fn:49">Nestorov, Yu.E. "A method of solving a convex programming problem with convergence rate 
 
 
 
 O
 
 
 (
 
 
 
 
 1
 
 k
 
 2
 
 
 
 
 
 
 )
 
 
 
 
 {\displaystyle O{\bigl (}{\frac {1}{k^{2}}}{\bigr )}}
 
". Dokl. Akad. Nauk SSSR. 269 (3): 543–547. <a href="https://www.mathnet.ru/eng/dan46009" target="_blank">https://www.mathnet.ru/eng/dan46009</a> <a href="#fnref:49" class="footnote-back-ref">↩</a></li>
<li id="fn:50">"Chambolle-Pock · Manopt.jl". docs.juliahub.com. Retrieved 2023-07-07. <a href="https://docs.juliahub.com/Manopt/h1Pdc/0.3.8/solvers/ChambollePock.html" target="_blank">https://docs.juliahub.com/Manopt/h1Pdc/0.3.8/solvers/ChambollePock.html</a> <a href="#fnref:50" class="footnote-back-ref">↩</a></li>
<li id="fn:51">These codes were used to obtain the images in the article. <a href="#fnref:51" class="footnote-back-ref">↩</a></li>
<li id="fn:52">"Numerical Tours - A Numerical Tour of Data Science". www.numerical-tours.com. Retrieved 2023-07-07. <a href="http://www.numerical-tours.com/" target="_blank">http://www.numerical-tours.com/</a> <a href="#fnref:52" class="footnote-back-ref">↩</a></li>
<li id="fn:53">"Chambolle-Pock solver — odl 0.6.1.dev0 documentation". odl.readthedocs.io. Retrieved 2023-07-07. <a href="https://odl.readthedocs.io/guide/chambolle_pock_guide.html#chambolle-pock-guide" target="_blank">https://odl.readthedocs.io/guide/chambolle_pock_guide.html#chambolle-pock-guide</a> <a href="#fnref:53" class="footnote-back-ref">↩</a></li>
</ol>

Chambolle-Pock algorithm open-in-new

Chambolle-Pock algorithm