We study the convergence of a generic half-quadratic algorithm for minimizing a wide class of $C^{1}$ objectives that occur in inverse imaging problems; this algorithm amounts to solving a sequence of positive definite systems (the inner systems) and has the advantages of simplicity and versatility. Half-quadratic optimization has been meticulously studied, both theoretically and experimentally, but two difficulties remain: first, the practical solutions of the inner systems are approximate, which may hamper convergence; and second, convergence to a stationary point of the objective is not guaranteed if the set of such points contains a continuum. We present new results that do not suffer from these limitations and hence extend our work in [M. Robini and Y. Zhu, SIAM J. Imaging Sci., 8 (2015), pp. 1752--1797]. We consider the inexact process in which the inner systems are solved to a fixed arbitrary accuracy defined in terms of the energy norm of the error. We show that this process converges to a stationary point of the objective under minimal conditions ubiquitous in regularized reconstruction and restoration. Our main results are based on the assumption that the objective has the Kurdyka--Łojasiewicz property, for which we provide constructing rules using the concept of tameness from the theory of o-minimal structures. We also propose an implementation using a truncated conjugate gradient method that controls the accuracy at negligible additional cost. Experiments on three different inverse problems show that the resulting algorithm performs well in various nonconvex scenarios and converges to solutions accurate to full machine precision.

We present new global convergence results for half-quadratic optimization in the context of image reconstruction. In particular, we do not assume that the inner optimization problem is solved exactly and we include the problematic cases where the objective function is nonconvex and has a continuum of stationary points. The inexact algorithm is modeled by a set-valued map defined from the majorization-minimization interpretation of half-quadratic optimization, and our main convergence results are based on the Kurdyka-Lojasiewicz inequality. We also propose a practical implementation that uses the conjugate gradient method and whose efficiency is illustrated by numerical experiments.

We study the global and local convergence of a generic half-quadratic optimization algorithm inspired from the dual energy formulation of Geman and Reynolds [IEEE Trans. Pattern Anal. Mach. Intell., 14 (1992), pp. 367--383]. The target application is the minimization of $C^{1}$ convex and nonconvex objective functionals arising in regularized image reconstruction. Our global convergence proofs are based on a monotone convergence theorem of Meyer [J. Comput. System Sci., 12 (1976), pp. 108--121]. Compared to existing results, ours extend to a larger class of objectives and apply under weaker conditions; in particular, we cover the case where the set of stationary points is not discrete. Our local convergence results use a majorization-minimization interpretation to derive an insightful characterization of the basins of attraction; this new perspective grounds a formal description of the intuitive water-flooding analogy. We conclude with image restoration experiments to illustrate the efficiency of the algorithm under various nonconvex scenarios.

This paper studies and evaluates the feasibility and the performance of different level interpolations for improving spatial resolution of diffusion tensor magnetic resonance imaging (DT-MRI or DTI). In particular, the following techniques are investigated: anisotropic interpolation operating on scalar gray-level images, log-Euclidean interpolation method, and the quaternion interpolation method, which operate on diffusion tensor fields. The performance is evaluated both qualitatively and quantitatively using criteria such as tensor determinant, fractional anisotropy (FA), mean diffusivity (MD), fiber length, etc. We conclude that tensor field interpolations allow avoiding undesirable swelling effect in DTI, which is not the case with scalar gray-level interpolation, and that scalar gray-level image interpolation and log-Euclidean tensor field interpolation suffer from decrease in FA and MD, which may mislead the interpretation of the clinical parameters FA and MD. In contrast, the quaternion tensor field interpolation avoids such FA and MD decrease, which suggests its use for clinical applications.

Simulated annealing (SA) and deterministic continuation are well-known generic approaches to global optimization. Deterministic continuation is computationally attractive but produces suboptimal solutions, whereas SA is asymptotically optimal but converges very slowly. In this paper, we introduce a new class of hybrid algorithms which combines the theoretical advantages of SA with the practical advantages of deterministic continuation. We call this class of algorithms stochastic continuation (SC). In a nutshell, SC is a variation of SA in which both the energy function and the communication mechanism are allowed to be time-dependent. We first prove that SC inherits the convergence properties of generalized SA under weak assumptions. Then, we show that SC can be successfully applied to optimization issues raised by the Bayesian approach to signal reconstruction. The considered class of energy functions arises in maximum a posteriori estimation with a Markov random field prior. The associated minimization task is NP-hard and beyond the scope of popular methods such as loopy belief propagation, tree-reweighted message passing, and graph cuts and its extensions. We perform numerical experiments in the context of three-dimensional reconstruction from a very limited number of projections; our results show that SC can substantially outperform both deterministic continuation and SA.

We propose a new fibre tracking algorithm for cardiac DT-MRI that parts with the locally ¿greedy¿ paradigm intrinsic to conventional tracking algorithms. We formulate the fibre tracking problem as the global problem of computing paths in a Boolean-weighted undirected graph. Each voxel is a vertex and edges connect every pair of neighboring voxels. We solve the underlying optimization task by Metropolis type annealing. The key features of our approach are: global optimality (unlike conventional tracking algorithms) and optimal balance between the density of fibres and the amount of available data. Besides, seed points are no longer needed; fibres are predicted in one shot for the whole DT-MRI volume without initialization artifacts.

We address the problem of reconstructing a piecewise constant 3-D object from a few noisy 2-D line-integral projections. More generally, the theory developed here readily applies to the recovery of an ideal n-D signal (n > or =1) from indirect measurements corrupted by noise. Stabilization of this ill-conditioned inverse problem is achieved with the Potts prior model, which leads to a challenging optimization task. To overcome this difficulty, we introduce a new class of hybrid algorithms that combines simulated annealing with deterministic continuation. We call this class of algorithms stochastic continuation (SC). We first prove that, under mild assumptions, SC inherits the finite-time convergence properties of generalized simulated annealing. Then, we show that SC can be successfully applied to our reconstruction problem. In addition, we look into the concave distortion acceleration method introduced for standard simulated annealing and we derive an explicit formula for choosing the free parameter of the cost function. Numerical experiments using both synthetic data and real radiographic testing data show that SC outperforms standard simulated annealing.

The dominant methodology for image restoration is to stabilize the problem by including a roughness penalty in addition to faithfulness to the data. Among various choices, concave stabilizers stand out for their boundary detection capabilities, but the resulting cost function to be minimized is generally multimodal. Although simulated annealing is theoretically optimal to take up this challenge, standard stochastic algorithms suffer from two drawbacks: i) practical convergence difficulties are encountered with second-order prior models and ii) it remains computationally demanding to favor the formation of smooth contour lines by taking the discontinuity field explicitly into account. This work shows that both weaknesses can be overcome in a multiresolution framework by means of the 2-D discrete wavelet transform (DWT). We first propose to improve convergence toward global minima by single-site updating on the wavelet domain. For this purpose, a new restricted DWT space is introduced and a theoretically sound updating mechanism is constructed on this subspace. Next, we suggest to incorporate the smoothness of the discontinuity field via an additional penalty term defined on the high frequency subbands. The resulting increase in complexity is small and the approach requires the specification of a unique extra parameter for which an explicit selection formula is derived.

Typically, the linear image restoration problem is an ill-conditioned, underdetermined inverse problem. Here, stabilization is achieved via the introduction of a first-order smoothness constraint which allows the preservation of edges and leads to the minimization of a nonconvex functional. In order to carry through this optimization task, we use stochastic relaxation with annealing. We prefer the Metropolis dynamics to the popular, but computationally much more expensive, Gibbs sampler. Still, Metropolis-type annealing algorithms are also widely reported to exhibit a low convergence rate. Their finite-time behavior is outlined and we investigate some inexpensive acceleration techniques that do not alter their theoretical convergence properties; namely, restriction of the state space to a locally bounded image space and increasing concave transform of the cost functional. Successful experiments about space-variant restoration of simulated synthetic aperture imaging data illustrate the performance of the resulting class of algorithms and show significant benefits in terms of convergence speed.

We address the linear image restoration problem in the case of a spatially varying blur. Most of the time, the recovery of the original image from its degraded measurements is an ill-conditioned, underdetermined inverse problem. Here, stabilization is achieved via concave potential functions and minimization is carried out using Metropolis-type simulated annealing. Still, the ordinary approach can be subject to some convergence difficulties and it remains an ambitious challenge to take into account the mutual dependence between neighboring discontinuities. We first propose to improve convergence towards global minima through single-site updating in the discrete wavelet transform (DWT) space. For this purpose, a suitable restricted DWT space is introduced and it turns out that the resulting class of algorithms shows less sensitivity to the choice of the hyperparameters. Next, we show that the smoothness of the discontinuity field can be incorporated implicitly in a multiresolution framework by means of a simple penalty term defined on the high frequency channels.

The synthetic aperture image formation process can be formulated as a space-variant 2D convolution. The recovery of the original reflection density is an ill-posed inverse problem which is both underdetermined and ill-conditioned. Its stabilization is achieved via concave stabilizers that are well adapted to the preservation of discontinuities. This leads to the minimization of a non-convex functional, a task which is successfully carried out using a Metropolis-type annealing algorithm. For improved performance, we investigate some inexpensive acceleration techniques which do not alter the theoretical convergence results; their efficiency is demonstrated through restorations from simulated data.