Explicit characterization of the convex envelope of the minimum of the horizontal and vertical total variations

In their 1997 study of total-variation-based image recovery, Chambolle and Lions proposed recovering a convex functional from the pointwise minimum of two convex regularizers by taking its convex envelope (biconjugate), equivalently its lower semicontinuous infimal convolution, and they computed explicit computable forms in several cases: the quadratic (Dirichlet-type, p=2) directional pair via a Fourier multiplier, total variation infimally convolved with a quadratic gradient penalty via a pointwise clipped formula, and total variation infimally convolved with second-order total variation via a splitting form. The case they left without an explicit form is the pair of directional total variations themselves. For the horizontal and vertical total variations on a bounded Lipschitz domain, the problem is to give an explicit, computable characterization of the convex envelope of their pointwise minimum, together with a computation scheme. No work in the subsequent literature computes this first-order directional envelope, and the problem remains open.

Background

Variational image recovery reconstructs an unknown image $u$ from data $u_0$ by minimizing a data discrepancy plus a regularizer. In the Rudin-Osher-Fatemi (ROF) model (Rudin, Osher and Fatemi 1992) the regularizer is the total variation: for $\Omega\subset\mathbb{R}^2$ a bounded Lipschitz domain, $BV(\Omega)$ is the space of functions of bounded variation, i.e. $L^1$ functions whose distributional gradient $Du$ is a vector-valued Radon measure of finite mass; the total variation is the mass $|Du|(\Omega)$, whose components $|D_xu|(\Omega)$ and $|D_yu|(\Omega)$ measure variation in the coordinate directions alone. For a bounded linear observation operator $A$ one minimizes $J(u)+\frac{\lambda}{2}\|Au-u_0\|_2^2$ over $L^2(\Omega)$; Chambolle and Lions (1997) established the basic well-posedness of such problems for one-homogeneous regularizers such as the total variation. Total variation favors piecewise-constant images (the staircasing effect), which motivates combining regularizers of different orders or different directions.

The pointwise minimum of two convex functionals is generally not convex. Chambolle and Lions (1997) proposed to convexify it in two equivalent ways. The infimal convolution of $J_1$ and $J_2$ is

$$(J_1\triangle J_2)(u)=\inf\{J_1(u_1)+J_2(u_2):\ u_1+u_2=u\},$$

and the convex envelope of the minimum is the biconjugate $(J_1\wedge J_2)^{**}$, where $^*$ denotes the Legendre-Fenchel conjugate on $L^2(\Omega)$ and $\wedge$ the pointwise minimum. For convex, lower semicontinuous, one-homogeneous $J_1$ and $J_2$ (seminorms), the two agree up to lower semicontinuous envelope, and

$$(J_1\wedge J_2)^{**}=(J_1^*+J_2^*)^*,$$

which for seminorms is the support function (the supremum of the linear pairing over a set) of the intersection of the two dual unit balls. For the directional case $J_x(u)=|D_xu|(\Omega)$ and $J_y(u)=|D_yu|(\Omega)$, this yields the variational representation

$$(J_x\wedge J_y)^{**}(u)=\sup\{\langle u,w\rangle:\ w=\partial_x\varphi=\partial_y\psi,\ |\varphi|\le 1,\ |\psi|\le 1\},$$

a direct consequence of the duality framework used in the source paper. This representation is an optimization, not an evaluation: no closed form for the supremum is known.

What is known. The source paper computed explicit computable forms for the neighboring instances: for the quadratic ($p=2$) directional pair, a Fourier-multiplier formula of the type $\int\frac{|\xi|^2|\eta|^2}{|\xi|^2+|\eta|^2}|\hat u|^2\,d\xi\,d\eta$; for total variation infimally convolved with a quadratic gradient penalty, a pointwise clipped formula of Huber type; and for total variation infimally convolved with second-order total variation, an alternating splitting form of the type $\int|\nabla u-\nabla v|+\alpha\,|\nabla(\nabla v)|$ (with a quadratic data term), which vanishes on affine functions. These instances set the standard of explicit and computable for the present problem. The paper left the $p=1$ directional pair, the horizontal and vertical total variations themselves, without such a form, while noting that the general infimal-convolution machinery (splitting minimizations, alternating algorithms) applies to it.

Later literature developed the program in other directions. The mixed-order instance became infimal convolutional TV (ICTV) and then total generalized variation (TGV), a tensor-valued higher-order regularizer with a full existence and duality theory (Bredies, Kunisch and Pock 2010), well-posedness for general linear inverse problems (Bredies and Holler 2014), and anisotropic and infimal-convolution variants for video and directional reconstruction (Holler and Kunisch 2014); the survey of Bredies and Holler (2020) records both the 1997 origin of the multi-order infimal-convolution model and the caution that infimal convolutions may or may not be exact and may or may not be lower semicontinuous. First-order splitting algorithms (Chambolle 2004; Goldstein and Osher 2009; Chambolle and Pock 2011; Setzer, Steidl and Teuber 2011) supply the numerics. The dependence of the ROF solution on the fidelity weight $\lambda$ was recast through dual norms and certificates (Aujol, Aubert, Blanc-Féraud and Chambolle 2005; Aujol and Chambolle 2005; Chambolle, Duval, Peyré and Poon 2016, whose minimal-norm certificate (the smallest-norm dual solution of the denoising problem), extended support (the region where that certificate attains its maximal norm) and calibrable sets - sets whose indicator functions are themselves TV minimizers - characterize exact recovery and stability). None of these lines computes the first-order directional envelope. One structural contrast positions the problem: $J_x$ vanishes on functions of $y$ alone and $J_y$ on functions of $x$ alone, so the envelope is expected to vanish on additively separable functions $f(x)+g(y)$ - it measures deviation from separable structure, whereas the mixed-order convolutions measure deviation from affine functions.

Problem Statement

Let $\Omega\subset\mathbb{R}^2$ be a bounded Lipschitz domain. For $u\in L^2(\Omega)$ set

$$J_x(u)=|D_xu|(\Omega),\qquad J_y(u)=|D_yu|(\Omega),$$

extended by $+\infty$ outside $BV(\Omega)$, where $D_xu$ and $D_yu$ are the components of the distributional derivative of $u$. Both functionals are convex, lower semicontinuous and one-homogeneous; their pointwise minimum $\min(J_x,J_y)$ is not convex.

Problem: produce an explicit, computable characterization of the convex envelope of this minimum on $L^2(\Omega)$,

$$(J_x\wedge J_y)^{**}=\big(\min(J_x,J_y)\big)^{**},$$

equivalently of the lower semicontinuous envelope of the infimal convolution $J_x\triangle J_y$. The predual variational form $(J_x^*+J_y^*)^*$ is known but is an optimization, not an evaluation.

Explicit and computable follows the standard set by the source paper's own computed instances (the Fourier-multiplier form for the quadratic directional pair, the pointwise clipped form for total variation with a quadratic gradient penalty). The kernel of the envelope, i.e. the set of functions on which it vanishes, is also at issue: $J_x$ vanishes on functions of $y$ alone and $J_y$ on functions of $x$ alone, so the kernel contains the additively separable functions $f(x)+g(y)$, and whether it equals the closure of that class is part of the question.

Together with the characterization, give a computation scheme: either an exact evaluation procedure or a provably convergent discretization of the envelope, stating the topology in which the biconjugate is taken and the boundary conventions for the dual potentials. The defining properties to establish are equality with the biconjugate in both inequality directions, convexity, one-homogeneity, lower semicontinuity, and the kernel identification.

Whether the infimal convolution $J_x\triangle J_y$ is itself exact and lower semicontinuous - equivalently, whether $(J_x\wedge J_y)^{**}$ coincides with it - is part of the question.

References

1. A. Chambolle and P.-L. Lions, Image recovery via total variation minimization and related problems. Numerische Mathematik 76(2):167-188, 1997. DOI: 10.1007/s002110050258; https://doi.org/10.1007/s002110050258
2. L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena 60(1-4):259-268, 1992. DOI: 10.1016/0167-2789(92)90242-F; https://doi.org/10.1016/0167-2789(92)90242-F
3. A. Chambolle, An algorithm for total variation minimization and applications. Journal of Mathematical Imaging and Vision 20(1-2):89-97, 2004. DOI: 10.1023/B:JMIV.0000011325.36760.1e; https://doi.org/10.1023/B:JMIV.0000011325.36760.1e
4. T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems. SIAM Journal on Imaging Sciences 2(2):323-343, 2009. DOI: 10.1137/080725891; https://doi.org/10.1137/080725891
5. A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40(1):120-145, 2011. DOI: 10.1007/s10851-010-0251-1; https://doi.org/10.1007/s10851-010-0251-1
6. S. Setzer, G. Steidl and T. Teuber, Infimal convolution regularizations with discrete l1-type functionals. Communications in Mathematical Sciences 9(3):797-827, 2011. DOI: 10.4310/CMS.2011.V9.N3.A7; https://doi.org/10.4310/CMS.2011.V9.N3.A7
7. K. Bredies, K. Kunisch and T. Pock, Total generalized variation. SIAM Journal on Imaging Sciences 3(3):492-526, 2010. DOI: 10.1137/090769521; https://doi.org/10.1137/090769521
8. K. Bredies and M. Holler, Regularization of linear inverse problems with total generalized variation. Journal of Inverse and Ill-Posed Problems 22(6):871-913, 2014. DOI: 10.1515/jip-2013-0068; https://doi.org/10.1515/jip-2013-0068
9. M. Holler and K. Kunisch, On infimal convolution of TV-type functionals and applications to video and image reconstruction. SIAM Journal on Imaging Sciences 7(4):2258-2300, 2014. DOI: 10.1137/130948793; https://doi.org/10.1137/130948793
10. K. Bredies and M. Holler, Higher-order total variation approaches and generalisations. Inverse Problems 36(12):123001, 2020. DOI: 10.1088/1361-6420/ab8f80; https://doi.org/10.1088/1361-6420/ab8f80 (preprint arXiv:1912.01587; https://arxiv.org/abs/1912.01587)
11. J.-F. Aujol, G. Aubert, L. Blanc-Féraud and A. Chambolle, Image decomposition into a bounded variation component and an oscillating component. Journal of Mathematical Imaging and Vision 22(1):71-88, 2005. DOI: 10.1007/s10851-005-4783-8; https://doi.org/10.1007/s10851-005-4783-8
12. J.-F. Aujol and A. Chambolle, Dual norms and image decomposition models. International Journal of Computer Vision 63(1):85-104, 2005. DOI: 10.1007/s11263-005-4948-3; https://doi.org/10.1007/s11263-005-4948-3
13. A. Chambolle, V. Duval, G. Peyré and C. Poon, Geometric properties of solutions to the total variation denoising problem. Inverse Problems 33(1):015002, 2016. DOI: 10.1088/0266-5611/33/1/015002; https://doi.org/10.1088/0266-5611/33/1/015002; https://arxiv.org/abs/1602.00087
14. R. Cristoferi, Exact solutions for the total variation denoising problem of piecewise constant images in dimension one. Journal of Applied Analysis 27(1):13-33, 2021. DOI: 10.1515/jaa-2020-2031; https://doi.org/10.1515/jaa-2020-2031
15. M. A. T. Figueiredo and J. M. Bioucas-Dias, Restoration of Poissonian images using alternating direction optimization. IEEE Transactions on Image Processing 19(12):3133-3145, 2010. DOI: 10.1109/TIP.2010.2053941; https://doi.org/10.1109/TIP.2010.2053941
16. L. Calatroni, J. C. De Los Reyes and C.-B. Schönlieb, Infimal convolution of data discrepancies for mixed noise removal. SIAM Journal on Imaging Sciences 10(3):1196-1233, 2017. DOI: 10.1137/16M1101684; https://doi.org/10.1137/16M1101684; https://arxiv.org/abs/1611.00690
17. M. Bergounioux, Mathematical analysis of a inf-convolution model for image processing. Journal of Optimization Theory and Applications 168(1):1-21, 2016. DOI: 10.1007/s10957-015-0734-8; https://doi.org/10.1007/s10957-015-0734-8