Search

This paper introduces a preconditioned convex splitting algorithm enhanced with line search techniques for nonconvex optimization problems. The algorithm utilizes second-order backward differentiation formulas (BDF) for the implicit and linear components and the Adams-Bashforth scheme for the nonlinear and explicit parts of the gradient flow in variational functions. The proposed algorithm, resembling a generalized difference-of-convex-function approach, involves a changing set of convex functions in each iteration. It integrates the Armijo line search strategy to improve performance. The study also discusses classical preconditioners such as symmetric Gauss-Seidel, Jacobi, and Richardson within this context. The global convergence of the algorithm is established through the Kurdyka-{\L}ojasiewicz properties, ensuring convergence within a finite number of preconditioned iterations. Numerical experiments demonstrate the superiority of the proposed second-order convex splitting with line search over conventional difference-of-convex-function algorithms.

In this work, we propose and study a preconditioned framework with a graphic Ginzburg-Landau functional for image segmentation and data clustering by parallel computing. Solving nonlocal models is usually challenging due to the huge computation burden. For the nonconvex and nonlocal variational functional, we propose several damped Jacobi and generalized Richardson preconditioners for the large-scale linear systems within a difference of convex functions algorithms framework. They are efficient for parallel computing with GPU and can leverage the computational cost. Our framework also provides flexible step sizes with a global convergence guarantee. Numerical experiments show the proposed algorithms are very competitive compared to the singular value decomposition based spectral method.

In this article, we propose and study a stochastic and relaxed preconditioned Douglas--Rachford splitting method to solve saddle-point problems that have separable dual variables. We prove the almost sure convergence of the iteration sequences in Hilbert spaces for a class of convex-concave and nonsmooth saddle-point problems. We also provide the sublinear convergence rate for the ergodic sequence concerning the expectation of the restricted primal-dual gap functions. Numerical experiments show the high efficiency of the proposed stochastic and relaxed preconditioned Douglas--Rachford splitting methods.

For some typical and widely used non-convex half-quadratic regularization models and the Ambrosio-Tortorelli approximate Mumford-Shah model, based on the Kurdyka-\L ojasiewicz analysis and the recent nonconvex proximal algorithms, we developed an efficient preconditioned framework aiming at the linear subproblems that appeared in the nonlinear alternating minimization procedure. Solving large-scale linear subproblems is always important and challenging for lots of alternating minimization algorithms. By cooperating the efficient and classical preconditioned iterations into the nonlinear and nonconvex optimization, we prove that only one or any finite times preconditioned iterations are needed for the linear subproblems without controlling the error as the usual inexact solvers. The proposed preconditioned framework can provide great flexibility and efficiency for dealing with linear subproblems and guarantee the global convergence of the nonlinear alternating minimization method simultaneously.

Estimating optical flows is one of the most interesting problems in computer vision, which estimates the essential information about pixel-wise displacements between two consecutive images. This work introduces an efficient dual optimization framework with accelerated preconditioners to the challenging nonsmooth optimization problem of total-variation regularized optical-flow estimation. In theory, the proposed dual optimization framework brings an elegant variational analysis on the given difficult optimization problem, while presenting an efficient algorithmic scheme without directly tackling the corresponding nonsmoothness in numeric. By introducing efficient preconditioners with a multi-scale implementation, the proposed accelerated dual optimization approaches achieve competitive estimation results of image motion, comparing to the state-of-the-art methods. Moreover, we show that the proposed preconditioners can guarantee convergence of the implemented numerical schemes with high efficiency.

Total generalization variation (TGV) is a very powerful and important regularization for various inverse problems and computer vision tasks. In this paper, we proposed a semismooth Newton based augmented Lagrangian method to solve this problem. The augmented Lagrangian method (also called as method of multipliers) is widely used for lots of smooth or nonsmooth variational problems. However, its efficiency usually heavily depends on solving the coupled and nonlinear system together and simultaneously, which is very complicated and highly coupled for total generalization variation. With efficient primal-dual semismooth Newton methods for the complicated linear subproblems involving total generalized variation, we investigated a highly efficient and competitive algorithm compared to some efficient first-order method. With the analysis of the metric subregularities of the corresponding functions, we give both the global convergence and local linear convergence rate for the proposed augmented Lagrangian methods., Comment: arXiv admin note: text overlap with arXiv:1911.10968

The Potts model has many applications. It is equivalent to some min-cut and max-flow models. Primal-dual algorithms have been used to solve these problems. Due to the special structure of the models, convergence proof is still a difficult problem. In this work, we developed two novel, preconditioned, and over-relaxed alternating direction methods of multipliers (ADMM) with convergence guarantee for these models. Using the proposed preconditioners or block preconditioners, we get accelerations with the over-relaxation variants of preconditioned ADMM. The preconditioned and over-relaxed Douglas-Rachford splitting methods are also considered for the Potts model. Our framework can handle both the two-labeling or multi-labeling problems with appropriate block preconditioners based on Eckstein-Bertsekas and Fortin-Glowinski splitting techniques.

Total Generalized Variation (TGV) regularization in image reconstruction relies on an infimal convolution type combination of generalized first- and second-order derivatives. This helps to avoid the staircasing effect of Total Variation (TV) regularization, while still preserving sharp contrasts in images. The associated regularization effect crucially hinges on two parameters whose proper adjustment represents a challenging task. In this work, a bilevel optimization framework with a suitable statistics-based upper level objective is proposed in order to automatically select these parameters. The framework allows for spatially varying parameters, thus enabling better recovery in high-detail image areas. A rigorous dualization framework is established, and for the numerical solution, two Newton type methods for the solution of the lower level problem, i.e. the image reconstruction problem, and two bilevel TGV algorithms are introduced, respectively. Denoising tests confirm that automatically selected distributed regularization parameters lead in general to improved reconstructions when compared to results for scalar parameters.

We consider the minimization problem with the truncated quadratic regularization with gradient operator, which is a nonsmooth and nonconvex problem. We cooperated the classical preconditioned iterations for linear equations into the nonlinear difference of convex functions algorithms with extrapolation. Especially, our preconditioned framework can deal with the large linear system efficiently which is usually expensive for computations. Global convergence is guaranteed and local linear convergence rate is given based on the analysis of the Kurdyka-\L ojasiewicz exponent of the minimization functional. The proposed algorithm with preconditioners turns out to be very efficient for image restoration and is also appealing for image segmentation.

Augmented Lagrangian method (also called as method of multipliers) is an important and powerful optimization method for lots of smooth or nonsmooth variational problems in modern signal processing, imaging, optimal control and so on. However, one usually needs to solve the coupled and nonlinear system together and simultaneously, which is very challenging. In this paper, we proposed several semismooth Newton methods to solve the nonlinear subproblems arising in image restoration, which leads to several highly efficient and competitive algorithms for imaging processing. With the analysis of the metric subregularities of the corresponding functions, we give both the global convergence and local linear convergence rate for the proposed augmented Lagrangian methods with semismooth Newton solvers.

This paper proposes a systematic mathematical analysis of both the direct and inverse acoustic scattering problem given the source in Radon measure space. For the direct problem, we investigate the well-posedness including the existence, the uniqueness, and the stability by introducing a special definition of the weak solution, i.e. \emph{very} weak solution. For the inverse problem, we choose the Radon measure space instead of the popular $L^1$ space to build the sparse reconstruction, which can guarantee the existence of the reconstructed solution. The sparse reconstruction problem can be solved by the semismooth Newton method in the dual space. Numerical examples are included.

This paper is concerned with a conceptual gesture-based instruction/input technique using electromagnetic wave detection. The gestures are modelled as the shapes of some impenetrable or penetrable scatterers from a certain admissible class, called a dictionary. The gesture-computing device generates time-harmonic electromagnetic point signals for the gesture recognition and detection. It then collects the scattered wave in a relatively small backscattering aperture on a bounded surface containing the point sources. The recognition algorithm consists of two stages and requires only two incident waves of different wavenumbers. The location of the scatterer is first determined approximately by using the measured data at a small wavenumber and the shape of the scatterer is then identified using the computed location of the scatterer and the measured data at a regular wavenumber. We provide the corresponding mathematical principle with rigorous analysis. Numerical experiments show that the proposed device works effectively and efficiently.

Alternating direction method of multipliers (ADMM) is a powerful first order methods for various applications in signal processing and imaging. However, there is no clear result on the weak convergence of ADMM with relaxation studied by Eckstein and Bertsakas \cite{EP} in infinite dimensional Hilbert spaces. In this paper, by employing a kind of "partial" gap analysis, we prove the weak convergence of general preconditioned and relaxed ADMM in infinite dimensional Hilbert spaces, with preconditioning for solving all the involved implicit equations under mild conditions. We also give the corresponding ergodic convergence rates respecting to the "partial" gap function. Furthermore, the connections between certain preconditioned and relaxed ADMM and the corresponding Douglas-Rachford splitting methods are also discussed, following the idea of Gabay in \cite{DGBA}. Numerical tests also show the efficiency of the proposed overrelaxation variants of preconditioned ADMM.

We study acceleration and preconditioning strategies for a class of Douglas-Rachford methods aiming at the solution of convex-concave saddle-point problems associated with Fenchel-Rockafellar duality. While the basic iteration converges weakly in Hilbert space with $\mathcal{O}(1/k)$ ergodic convergence of restricted primal-dual gaps, acceleration can be achieved under strong-convexity assumptions. Namely, if either the primal or dual functional in the saddle-point formulation is strongly convex, then the method can be modified to yield $\mathcal{O}(1/k^2)$ ergodic convergence. In case of both functionals being strongly convex, similar modifications lead to an asymptotic convergence of $\mathcal{O}({\vartheta}^k)$ for some $0 < {\vartheta} < 1$. All methods allow in particular for preconditioning, i.e., the inexact solution of the implicit linear step in terms of linear splitting methods with all convergence rates being maintained. The efficiency of the proposed methods is verified and compared numerically, especially showing competitiveness with respect to state-of-the-art accelerated algorithms., Comment: 37 pages, 9 tables, 4 figures

We develop three inverse elastic scattering schemes for locating multiple small, extended and multiscale rigid bodies, respectively. There are some salient and promising features of the proposed methods. The cores of those schemes are certain indicator functions, which are obtained by using only a single far-field pattern of the pressure (longitudinal) wave, or the shear (transversal) wave, or the total wave field. Though the inverse scattering problem is known to be nonlinear and ill-posed, the proposed reconstruction methods are totally "direct" and there are no inversions involved. Hence, the methods are very efficient and robust against noisy data. Both rigorous mathematical justifications and numerical simulations are presented in our study., Comment: All comments are welcome

We develop two inverse scattering schemes for locating multiple electromagnetic (EM) scatterers by the electric far-field measurement corresponding to a single incident/detecting plane wave. The first scheme is for locating scatterers of small size compared to the wavelength of the detecting plane wave. The multiple scatterers could be extremely general with an unknown number of components, and each scatterer component could be either an impenetrable perfectly conducting obstacle or a penetrable inhomogeneous medium with an unknown content. The second scheme is for locating multiple perfectly conducting obstacles of regular size compared to the detecting EM wavelength. The number of the obstacle components is not required to be known in advance, but the shape of each component must be from a certain known admissible class. The admissible class may consist of multiple different reference obstacles. The second scheme could also be extended to include the medium components if a certain generic condition is satisfied. Both schemes are based on some novel indicator functions whose indicating behaviors could be used to locate the scatterers. No inversion will be involved in calculating the indicator functions, and the proposed methods are every efficient and robust to noise. Rigorous mathematical justifications are provided and extensive numerical experiments are conducted to illustrate the effectiveness of the imaging schemes.

We consider time-harmonic wave scattering from an inhomogeneous isotropic medium supported in a bounded domain $\Omega\subset\mathbb{R}^N$ ($N\geq 2$). {In a subregion $D\Subset\Omega$, the medium is supposed to be lossy and have a large mass density. We study the asymptotic development of the wave field as the mass density $\rho\rightarrow +\infty$} and show that the wave field inside $D$ will decay exponentially while the wave filed outside the medium will converge to the one corresponding to a sound-hard obstacle $D\Subset\Omega$ buried in the medium supported in $\Omega\backslash\bar{D}$. Moreover, the normal velocity of the wave field on $\partial D$ from outside $D$ is shown to be vanishing as $\rho\rightarrow +\infty$. {We derive very accurate estimates for the wave field inside and outside $D$ and on $\partial D$ in terms of $\rho$, and show that the asymptotic estimates are sharp. The implication of the obtained results is given for an inverse scattering problem of reconstructing a complex scatterer.}

We consider regularized approximate cloaking for the Helmholtz equation. Various cloaking schemes have been recently proposed and extensively investigated. The existing cloaking schemes in literature are (optimally) within $|\ln\rho|^{-1}$ in 2D and $\rho$ in 3D of the perfect cloaking, where $\rho$ denotes the regularization parameter. In this work, we develop a cloaking scheme with a well-designed lossy layer right outside the cloaked region that can produce significantly enhanced near-cloaking performance. In fact, it is proved that the proposed cloaking scheme could (optimally) achieve $\rho^N$ in $\mathbb{R}^N$, $N\geq 2$, within the perfect cloaking. It is also shown that the limit of the proposed lossy layer corresponds to a sound-hard layer. We work with general geometry and arbitrary cloaked contents of the proposed cloaking device.

We consider approximate cloaking from a regularization viewpoint introduced in [13] for EIT and further investigated in [12] [17] for the Helmholtz equation. The cloaking schemes in [12] and [17] are shown to be (optimally) within $|\ln\rho|^{-1}$ in 2D and $\rho$ in 3D of perfect cloaking, where $\rho$ denotes the regularization parameter. In this paper, we show that by employing a sound-hard layer right outside the cloaked region, one could (optimally) achieve $\rho^N$ in $\mathbb{R}^N,\ N\geq 2$, which significantly enhances the near-cloak. We then develop a cloaking scheme by making use of a lossy layer with well-chosen parameters. The lossy-layer cloaking scheme is shown to possess the same cloaking performance as the one with a sound-hard layer. Moreover, it is shown that the lossy layer could be taken as a finite realization of the sound-hard layer. Numerical experiments are also presented to assess the cloaking performances of all the cloaking schemes for comparisons.