Iterated hard-thresholding for linear inverse problems with sparsity constraints

We describe an iterative algorithm for the minimization of Tikhonov type functionals which involve sparsity constraints in form of ℓ^p -penalties which have been proposed recently for the regularization of ill-posed problems. In contrast to the well-known algorithm considered by Daubechies, Defrise and De Mol, it uses hard instead of soft thresholding. This hard thresholding algorithm is based on the generalized conditional gradient method. General results on the convergence of the generalized conditional gradient method enable us to prove strong convergence of the iterates. Furthermore we are able to establish convergence rates of O (n^–1/2) and O (λⁿ) for p = 1 and 1 < p ≤ 2 respectively. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear Convergence of Iterative Soft-Thresholding

In this article a unified approach to iterative soft-thresholding algorithms for the solution of linear operator equations in infinite dimensional Hilbert spaces is presented. We formulate the algorithm in the framework of generalized gradient methods and present a new convergence analysis. As main result we show that the algorithm converges with linear rate as soon as the underlying operator satisfies the so-called finite basis injectivity property or the minimizer possesses a so-called strict sparsity pattern. Moreover it is shown that the constants can be calculated explicitly in special cases (i.e. for compact operators). Furthermore, the techniques also can be used to establish linear convergence for related methods such as the iterative thresholding algorithm for joint sparsity and the accelerated gradient projection method.     

Symmetric tensor fields of bounded deformation

We introduce and study spaces of symmetric tensor fields of bounded deformation for tensors of arbitrary order, i.e., where the symmetrized derivative is still a Radon measure. A Sobolev–Korn type estimate, a boundary trace theorem and continuous as well as compact embedding properties into Lebesgue spaces are obtained, showing that these spaces can be regarded as a natural generalization of the spaces of bounded deformation to higher-order symmetric tensors.     

An optimal control problem in image processing

As a starting point, we present a control problem in mammographic image processing which leads to non-standard penalty terms and involves a degenerate parabolic PDE which has to be controlled in the coefficients. We then discuss the classical conditional gradient method from constrained optimization and propose a generalization for non-convex functionals which covers the conditional gradient method as well as the recently proposed iterative shrinkage method of Daubechies, Defrise and De Mol for the solution of linear inverse problems with sparsity promoting penalty terms. We prove that this new algorithm converges. This also gives a deeper understanding of the iterative shrinkage method. Further, we show an application to the above-mentioned control problem in image processing. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Tensor-Free Proximal Methods for Lifted Bilinear/Quadratic Inverse Problems with Applications to Phase Retrieval

Foundations of Computational Mathematics - We propose and study a class of novel algorithms that aim at solving bilinear and quadratic inverse problems. Using a convex relaxation based on tensorial...     

A generalized conditional gradient method and its connection to an iterative shrinkage method

This article combines techniques from two fields of applied mathematics: optimization theory and inverse problems. We investigate a generalized conditional gradient method and its connection to an iterative shrinkage method, which has been recently proposed for solving inverse problems. The iterative shrinkage method aims at the solution of non-quadratic minimization problems where the solution is expected to have a sparse representation in a known basis. We show that it can be interpreted as a generalized conditional gradient method. We prove the convergence of this generalized method for general class of functionals, which includes non-convex functionals. This also gives a deeper understanding of the iterative shrinkage method.     

A Generalized Conditional Gradient Method for Dynamic Inverse Problems with Optimal Transport Regularization

We develop a dynamic generalized conditional gradient method (DGCG) for dynamic inverse problems with optimal transport regularization. We consider the framework introduced in Bredies and Fanzon (ESAIM: M2AN 54:2351–2382, 2020), where the objective functional is comprised of a fidelity term, penalizing the pointwise in time discrepancy between the observation and the unknown in time-varying Hilbert spaces, and a regularizer keeping track of the dynamics, given by the Benamou–Brenier energy constrained via the homogeneous continuity equation. Employing the characterization of the extremal points of the Benamou–Brenier energy (Bredies et al. in Bull Lond Math Soc 53(5):1436–1452, 2021), we define the atoms of the problem as measures concentrated on absolutely continuous curves in the domain. We propose a dynamic generalization of a conditional gradient method that consists of iteratively adding suitably chosen atoms to the current sparse iterate, and subsequently optimizing the coefficients in the resulting linear combination. We prove that the method converges with a sublinear rate to a minimizer of the objective functional. Additionally, we propose heuristic strategies and acceleration steps that allow to implement the algorithm efficiently. Finally, we provide numerical examples that demonstrate the effectiveness of our algorithm and model in reconstructing heavily undersampled dynamic data, together with the presence of noise.