Search

In the first part of this paper we develop a theory for image restoration with a learned regularizer that is analogous to that of Meyer's geometric characterization of solutions of the classical variational method of Rudin-Osher-Fatemi (ROF). The learned regularizer we use is a Kantorovich potential for an optimal transport problem of mapping a distribution of noisy images onto clean ones, as first proposed by Lunz, \" Oktem, and Sch\"onlieb. We show that the effect of their restoration method on the distribution of the images is an explicit Euler discretization of a gradient flow on probability space, while our variational problem, dubbed Wasserstein ROF (WROF), is the corresponding implicit Euler discretization. We obtain our geometric characterization of the solution in this learned regularizer setting by first proving a much more general convex analysis theorem for variational problems having solutions characterized by projections. We then use optimal transport arguments to obtain the corresponding theorem for WROF from this general result, as well as a natural decomposition of a transport map into large scale "features" and small scale "details," where scale refers to the magnitude of the transport distance. In the second part of the paper we leverage our theory for restoration with learned regularizers to analyze two algorithms which iterate WROF. We refer to these as iterative regularization and multiscale transport. For the former we obtain a proof of convergence to the clean data. For the latter we produce successive approximations to the target distribution that match it up to finer and finer scales. These two algorithms are in complete analogy to well-known effective methods based on ROF for iterative denoising, respectively hierarchical image decomposition. We also obtain an analogue of the Tadmor-Nezzar-Vese energy identity, which decomposes the Wasserstein 2 distance between two measures into a sum of nonnegative terms that correspond to transport costs at different scales. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

Proximal mappings are essential in splitting algorithms for both convex and noncon-vex optimization. In this paper, we show that proximal mappings of every prox-bounded function are nonexpansive if and only if they are firmly nonexpansive if and only if they are averaged if and only if the function is convex. Lipschitz proximal mappings of prox-bounded functions are also characterized via hypoconvex or strongly convex functions. Our results generalize a recent result due to Rockafellar [ABSTRACT FROM AUTHOR]

Given closed convex sets Ci, i=1, ... l, and some nonzero linear maps Ai, i=1, ... l, of suitable dimensions, the multiset split feasibility problem aims at finding a point in ... based on computing projections onto Ci and multiplications by Ai and AiT. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto ...; we refer to this problem as the best approximation problem in multiset split feasibility settings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving the BA-MSF in the special case when all Ai - I, to solve the general BA-MSF. Our Dykstra-type projection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrange dual problem, and it only requires computing projections onto Ci and multiplications by Ai and AiT in each iteration. Under a standard relative interior condition and a genericity assumption on the point we need to project, we show that the dual objective satisfies the Kurdyka-Łojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each Ci is C1,α.-cone reducible for some α∈ (0,1]: this class of sets covers the class of C²-cone reducible sets, which include all polyhedrons, second-order cone, and the cone of positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear or sublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concrete examples are constructed to illustrate the necessity of some of our assumptions. [ABSTRACT FROM AUTHOR]

This paper proposes a path-based approach for the minimization of a continuously differentiable function over sparse symmetric sets, which is a hard problem that exhibits a restrictiveness-hierarchy of necessary optimality conditions. To achieve the more restrictive conditions in the hierarchy, state-of-the-art algorithms require a support optimization oracle that must exactly solve the problem in smaller dimensions. The path-based approach developed in this study produces a path-based optimality condition, which is placed well in the restrictiveness-hierarchy, and a method to achieve it that does not require a support optimization oracle and, moreover, is projection-free. In the development process, new results are derived for the regularized linear minimization problem over sparse symmetric sets, which give additional means to identify optimal solutions for convex and concave objective functions. We complement our results with numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we have studied a decomposition method for solving a class of non-convex two-stage stochastic programs, where both the objective and constraints of the second-stage problem are nonlinearly parameterized by the first-stage variables. Due to the failure of the Clarke regularity of the resulting nonconvex recourse function, classical decomposition approaches such as Benders decomposition and (augmented) Lagrangian-based algorithms cannot be directly generalized to solve such models. By exploring an implicitly convex-concave structure of the recourse function, we introduce a novel decomposition framework based on the so-called partial Moreau envelope. The algorithm successively generates strongly convex quadratic approximations of the recourse function based on the solutions of the second-stage convex subproblems and adds them to the first-stage mas-ter problem. Convergence has been established for both a fixed number of scenarios and a sequential internal sampling strategy. Numerical experiments are conducted to demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and a nonsmooth function, while the second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have weak convergence guarantees or need to solve lots of subproblems per iteration. Due to this, we propose hybrid algorithms for solving this problem in which we first compute approximate critical points and then check whether these points are approximate D-stationary points. Under suitable conditions, we prove that there exists a subsequence of iterates of which every accumulation point is a D-stationary point. Some preliminary numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The Euler elastica (EE) model with surface curvature can generate artifact-free results compared with the traditional total variation regularization model in image processing. However, strong nonlinearity and singularity due to the curvature term in the EE model pose a great challenge for one to design fast and stable algorithms for the EE model. In this paper, we propose a new, fast, hybrid alternating minimization (HALM) algorithm for the EE model based on a bilinear decomposition of the gradient of the underlying image and prove the global convergence of the minimizing sequence generated by the algorithm under mild conditions. The HALM algorithm comprises three subminimization problems and each is either solved in the closed form or approximated by fast solvers, making the new algorithm highly accurate and efficient. We also discuss the extension of the HALM strategy to deal with general curvature-based variational models, especially with a Lipschitz smooth functional of the curvature. A host of numerical experiments are conducted to show that the new algorithm produces good results with much-improved efficiency compared to other state-of-the-art algorithms for the EE model. As one of the benchmarks, we show that the average running time of the HALM algorithm is at most one-quarter of that of the fast operator-splitting-based Deng--Glowinski--Tai algorithm. [ABSTRACT FROM AUTHOR]

The constrained pressure residual (CPR) algorithm is a family of well-known and industry-standard preconditioners for large-scale reservoir simulation. The CPR algorithm is a twostage preconditioner to deal with different blocks stage-by-stage, and is often able to effectively improve the robustness behavior and the convergence speed of linear iterations. Nonetheless, as a linear preconditioner, it is hard for the traditional CPR method to be capable of action at the nonlinear level for effectively solving large sparse nonlinear systems of equations with high nonlinearity. In this paper, we present and study the extension of this linear method to the nonlinearly CPR (NCPR) case for solving fractured reservoir problems, to deal with the difficulty of the slow convergence or stagnation from the nonlinear level. In the proposed nonlinear preconditioning, a subspace nonlinear block system is first built and solved to remove the unbalanced nonlinearities of the pressure and the saturation fields, and the fast convergence can then be restored when a variant of semismooth Newton methods is called after the subspace nonlinear block system is solved. Experiments on two or three dimensional porous media applications are presented to demonstrate the applicability and parallel scalability of the aforementioned NCPR method. We also show that the proposed algorithm is superior to the commonly used nonlinear algorithm in terms of the robustness and the positivity-preserving property. [ABSTRACT FROM AUTHOR]