Iterative thresholding meets free-discontinuity problems

DOI10.1007/S10208-010-9071-3MaRDI QIDQ707746zbMATH OpenOpenAlexFDO

Publication date 8 October 2010

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.2605

\(\Gamma\) - approximating discrete functional Constrained optimization Convergence analysis Energy functional Free-discontinuity problems Inverse problems Iterative thresholding Stability of equilibria

Mathematics Subject Classification ID

Convex functions and convex programs in convex geometry (52A41) Numerical solution to inverse problems in abstract spaces (65J22) Numerical methods for wavelets (65T60) Computing methodologies for image processing (68U10)

Abstract: Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower dimensional set consisting of the discontinuities of the function. Hence, the derivative of the solution is assumed to be a `small' function almost everywhere except on sets where it concentrates as a singular measure. This is the case, for instance, in crack detection from fracture mechanics or in certain digital image segmentation problems. If we discretize such situations for numerical purposes, the free-discontinuity problem in the discrete setting can be re-formulated as that of finding a derivative vector with small components at all but a few entries that exceed a certain threshold. This problem is similar to those encountered in the field of `sparse recovery', where vectors with a small number of dominating components in absolute value are recovered from a few given linear measurements via the minimization of related energy functionals. Several iterative thresholding algorithms that intertwine gradient-type iterations with thresholding steps have been designed to recover sparse solutions in this setting. It is natural to wonder if and/or how such algorithms can be used towards solving discrete free-discontinuity problems. The current paper explores this connection, and, by establishing an iterative thresholding algorithm for discrete free-discontinuity problems, provides new insights on properties of minimizing solutions thereof.

Review text

This very important and useful paper is devoted to the study of iterative thresholding meets free-discontinuity problems. It is the first one in this consideration. Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower-dimensional set consisting of the discontinuities of the function. The proposed terminology was introduced by \textit{E. De Giorgi} [in: Frontiers in pure and applied mathematics, Coll. Pap. Ded. J.-L. Lions Occas. 60th Birthday, 55--62 (1991; Zbl 0758.49002)] to indicate a class of variational problems that pertain to the minimization of a functional, involving both volume and surface energies, depending on a closed set \(K \subset \mathbb{R}^d\), and a function \(u\) on \(\mathbb{R}^d\) usually smooth outside \(K\) (\(K\) is not fixed a priori and is an unknown of the problem, or \(K\) is not a boundary in general, but a free-surface inside the domain of the problem). Here a free-discontinuity problem is the one modeled by the so-called Mumford-Shah functional,which is defined by: \[ J(u,K): = \int_{\Omega \backslash K}[| \nabla u|^2 + \alpha (u-g)^2]dx + \beta \mathcal{H}^{d-1}(K \cap \Omega) \] (The set \(\Omega\) is a bounded open subset of \(\mathbb{R}^d\), \(\alpha, \beta >0\) are fixed constants and \(g \in L^\infty (\Omega)\), \(\mathcal{H}^N\) denotes the \(N\)-dimensional Hausdorff measure, \(d=1,2\).) The minimizing function \(u \in W^{1,2} (\Omega \backslash K)\) approximate a given noisy image \(g\). The problem of minimization of \(J\) with respect to \(u\) (for fixed \(K\)) is equivalent to solving the system of equations: \( \Delta u = \alpha (u-g)\) in \(\Omega \backslash K\), \(\frac{\partial u}{\partial \nu}=0\) on \(\partial \Omega \cap K\) (\(\nu\) is the outward - pointing normal vector at any \(x \in \partial \Omega \cup K\). The relevant unknown in free-discontinuity problem is the set \(K\). Because there is no topology on the closed sets, ensures compactness of the minimizing sequences and the lower semicontinuity of the Hausdorff measure, the existence of minimizers \((u, K)\) of \(J\) is a very difficult problem. Main result: The authors show that discretizations of regularized functionals of the type: \[ J(u) = \alpha \|Ku-g\|^2_{L_2(\Omega)} + MS(u)\tag{1} \] where \(K: L_2 (\Omega) \rightarrow L_2 (\Omega)\) is bounded operator which is not boundedly invertible, and \(g=K \overline{u} + n\) (\(n\) is a stochastic noise), \(MS (u) = \int_{\Omega \backslash S_u}| \nabla u|^2 + \beta \mathcal{H}^{d-1}(S_u)\) (\(S_u\) is the well-defined discontinuity set of \(u\)). The authors show that discretizations of the type (1) always have minimizers. Here, these discretizations correspond to functionals of the form \[ \mathcal{T}_h (u): \alpha h^2 \|Ku - g\|^2_{l_2} + h^2 \sum_{(hi,hj) \in \Omega_h} [W_h (\frac{u_{i+1,j}- u_{i,j}} {h} + W_h (\frac{U_{i,j+1}- u_{i,j}}{h})],\tag{2} \] with \(W_h(t)= \min \{t^2, \frac{\beta}{h}\}\), and that such functionals admit minimizers, is proved. The discrete Mumford-Shah approximation \[ \begin{multlined} J_h(u) := h^2 \sum_{(hi,hj)} W_h (\frac{u_{i+1,j} - u_{i,j}} {h}) + h^2 \sum_{(hi,hj)\in \Omega_h} W_h (\frac{u_{i,j+1} - u_{i,j}} {h}) + \\ \alpha h^2 \sum_{(hi,hj) \in \Omega_h} (u_{i,j} - g_{i,j})^2 \end{multlined} \] can be written in the form (2). Moreover in the one-dimensional situation the authors show that such minimizers, along with fixed points of proposed algorithm, will have components that fall either below on threshold in absolute value, or fall above a second, strictly larger threshold, which depend only on the parameters \(\alpha\) and \(\beta\), and not on the data \((K,g)\). Any a priori information concerning these thresholds may thus be incorporated towards selection of the parameters \((\alpha, \beta)\). As a consequence of these achievements, the authors prove that global minimizers are always isolated, although not necessarily unique, whereas local minimizers may constitute a continuum of unstable equilibria. Thus the proposed analysis will shed light on fundamental properties virtues, and limitations, of regularization by means of the Mumford-Shah functional \(MS\) and provide a rigorous justification of the numerical results appearing in the literature.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Iterative thresholding meets free-discontinuity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q707746)