We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider

i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components,

ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional components of the objective function, and

iii) quadratic Lyapunov inequalities that can be used to draw convergence conclusions.

We provide a necessary and sufficient condition for the existence of a quadratic Lyapunov inequality that amounts to solving a small-sized semidefinite program. We showcase our methodology on several first-order methods that fit the framework. Most notably, our methodology allows us to significantly extend the region of parameter choices that allow for duality gap convergence in the Chambolle–Pock method when the linear operator is the identity mapping.

We present a data-driven regularization method for inverse problems introduced in [1,2]. Our approach consists of two steps. In the first step, an intermediate reconstruction is performed by applying the truncated singular value decomposition (SVD). To prevent noise amplification, only coefficients corresponding to sufficiently large singular values are used, while the remaining coefficients are set to zero. In a second step, a trained deep neural network is used to recover the truncated SVD coefficients. We show that the proposed scheme yields a convergent regularization method. Numerical results are presented for limited data problems in PAT (photacoustic tomography) and X-ray CT (computed tomography), showing that learned SVD regularization significantly improves pure truncated SVD regularization.

[1] J. Schwab, S. Antholzer, M. Haltmeier. Big in Japan: Regularizing networks for solving inverse problems, Journal of Mathematical Imaging and Vision, 62(3): 445-455, 2020.

[2] J. Schwab, S. Antholzer, R. Nuster, G. Paltauf, M. Haltmeier. Deep learning of truncated singular values for limited view photoacoustic tomography, Photons Plus Ultrasound: Imaging and Sensing 10878: 254-262, 2019.

The Multiscale Hierarchical Decomposition Method (MHDM) is a popular method originating from mathematical imaging. In its original context, it is very well suited to recover fine details of solutions to denoising and deblurring problems. The main idea is to iteratively solve a ROF minimization problem. In every iteration, the data for the ROF functional will be the residual from the previous step, and the approximation to the true data will consist of the sum of all minimizers up to that step. Thus, one obtains iterates that represent a decomposition of the ground truth into multiple levels of detail at different scales. We consider the method in a more general framework, by replacing the total variation seminorm in the ROF functional by more general penalty terms in appropriate settings. We expand existing convergence results for the residual of the iterates in the case when some classes of convex and nonconvex penalties are employed. Moreover, we propose a necessary and sufficient condition under which the iterates of the MHDM agree with Tikhonov regularizers corresponding to suitable regularization parameters.  We discuss the results on several examples, including 1- and 2-dimensional TV-denoising.

In this paper we consider a moment relaxation for large-scale nonsmooth optimization problems with graphical structure and manifold constraints. In the context of probabilistic inference this can be interpreted as MAP-inference in a continuous graphical model. In contrast to classical moment relaxations for global polynomial optimization we exploit the partially separable structure of the optimization problem and leverage Kantorovich–Rubinstein duality for optimal transport to decouple the problem. The proposed formulation is obtained via a dual subspace approximation which allows us to tackle possibly nonpolynomial optimization problems with manifold constraints and geodesic coupling terms. We show that the duality gap vanishes in the limit by proving that a Lipschitz continuous dual multiplier on a unit sphere can be approximated as closely as desired in terms of a Lipschitz continuous polynomial. This is closely related to spherical harmonics and the eigenfunctions of the Laplace–Beltrami operator. The formulation is applied to manifold-valued imaging problems with total variation regularization and graph-based SLAM. In imaging tasks our approach achieves small duality gaps for a moderate degree. In graph-based SLAM our approach often finds solutions which after refinement with a local method are near the ground truth solution.