Ignace Loris

Frederik J. Simons, Ignace Loris, Guust Nolet et al.

We propose a class of spherical wavelet bases for the analysis of geophysical models and forthe tomographic inversion of global seismic data. Its multiresolution character allows for modeling with an effective spatial resolution that varies with position within the Earth. Our procedure is numerically efficient and can be implemented with parallel computing. We discuss two possible types of discrete wavelet transforms in the angular dimension of the cubed sphere. We discuss benefits and drawbacks of these constructions and apply them to analyze the information present in two published seismic wavespeed models of the mantle, for the statistics and power of wavelet coefficients across scales. The localization and sparsity properties of wavelet bases allow finding a sparse solution to inverse problems by iterative minimization of a combination of the $\ell_2$ norm of data fit and the $\ell_1$ norm on the wavelet coefficients. By validation with realistic synthetic experiments we illustrate the likely gains of our new approach in future inversions of finite-frequency seismic data and show its readiness for global seismic tomography.

Ignace Loris, Caroline Verhoeven

An explicit algorithm for the minimization of an $\ell_1$ penalized least squares functional, with non-separable $\ell_1$ term, is proposed. Each step in the iterative algorithm requires four matrix vector multiplications and a single simple projection on a convex set (or equivalently thresholding). Convergence is proven and a 1/N convergence rate is derived for the functional. In the special case where the matrix in the $\ell_1$ term is the identity (or orthogonal), the algorithm reduces to the traditional iterative soft-thresholding algorithm. In the special case where the matrix in the quadratic term is the identity (or orthogonal), the algorithm reduces to a gradient projection algorithm for the dual problem. By replacing the projection with a simple proximity operator, other convex non-separable penalties than those based on an $\ell_1$-norm can be handled as well.

Ignace Loris

The problem of assessing the performance of algorithms used for the minimization of an $\ell_1$-penalized least-squares functional, for a range of penalty parameters, is investigated. A criterion that uses the idea of `approximation isochrones' is introduced. Five different iterative minimization algorithms are tested and compared, as well as two warm-start strategies. Both well-conditioned and ill-conditioned problems are used in the comparison, and the contrast between these two categories is highlighted.

Silvia Bonettini, Ignace Loris, Federica Porta et al.

We consider a variable metric linesearch based proximal gradient method for the minimization of the sum of a smooth, possibly nonconvex function plus a convex, possibly nonsmooth term. We prove convergence of this iterative algorithm to a critical point if the objective function satisfies the Kurdyka-Lojasiewicz property at each point of its domain, under the assumption that a limit point exists. The proposed method is applied to a wide collection of image processing problems and our numerical tests show that our algorithm results to be flexible, robust and competitive when compared to recently proposed approaches able to address the optimization problems arising in the considered applications.

Ignace Loris, Caroline Verhoeven

A qualitative comparison of total variation like penalties (total variation, Huber variant of total variation, total generalized variation, ...) is made in the context of global seismic tomography. Both penalized and constrained formulations of seismic recovery problems are treated. A number of simple iterative recovery algorithms applicable to these problems are described. The convergence speed of these algorithms is compared numerically in this setting. For the constrained formulation a new algorithm is proposed and its convergence is proven.

Ignace Loris

L1Packv2 is a Mathematica package that contains a number of algorithms that can be used for the minimization of an $\ell_1$-penalized least squares functional. The algorithms can handle a mix of penalized and unpenalized variables. Several instructive examples are given. Also, an implementation that yields an exact output whenever exact data are given is provided.

Ignace Loris, Caroline Verhoeven

We propose an iterative algorithm for the minimization of a $\ell_1$-norm penalized least squares functional, under additional linear constraints. The algorithm is fully explicit: it uses only matrix multiplications with the three matrices present in the problem (in the linear constraint, in the data misfit part and in penalty term of the functional). None of the three matrices must be invertible. Convergence is proven in a finite-dimensional setting. We apply the algorithm to a synthetic problem in magneto-encephalography where it is used for the reconstruction of divergence-free current densities subject to a sparsity promoting penalty on the wavelet coefficients of the current densities. We discuss the effects of imposing zero divergence and of imposing joint sparsity (of the vector components of the current density) on the current density reconstruction.

Silvia Bonettini, Ignace Loris, Federica Porta et al.

We develop a new proximal-gradient method for minimizing the sum of a differentiable, possibly nonconvex, function plus a convex, possibly non differentiable, function. The key features of the proposed method are the definition of a suitable descent direction, based on the proximal operator associated to the convex part of the objective function, and an Armijo-like rule to determine the step size along this direction ensuring the sufficient decrease of the objective function. In this frame, we especially address the possibility of adopting a metric which may change at each iteration and an inexact computation of the proximal point defining the descent direction. For the more general nonconvex case, we prove that all limit points of the iterates sequence are stationary, while for convex objective functions we prove the convergence of the whole sequence to a minimizer, under the assumption that a minimizer exists. In the latter case, assuming also that the gradient of the smooth part of the objective function is Lipschitz, we also give a convergence rate estimate, showing the O(1/k) complexity with respect to the function values. We also discuss verifiable sufficient conditions for the inexact proximal point and we present the results of a numerical experience on a convex total variation based image restoration problem, showing that the proposed approach is competitive with another state-of-the-art method.

Ignace Loris, Caroline Verhoeven

The effectiveness of using model sparsity as a priori information when solving linear inverse problems is studied. We investigate the reconstruction quality of such a method in the non-idealized case and compute some typical recovery errors (depending on the sparsity of the desired solution, the number of data, the noise level on the data, and various properties of the measurement matrix); they are compared to known theoretical bounds and illustrated on a magnetic tomography example.