Many tasks in imaging can be modeled via the minimization of a nonconvex composite function. A popular class of algorithms for solving such problems are majorization-minimization techniques which iteratively approximate the composite nonconvex function by a majorizing function that is easy to minimize. Most techniques, e.g. gradient descent, utilize convex majorizers in order guarantee that the majorizer is easy to minimize. In our work we consider a natural class of nonconvex majorizers for these functions, and show that these majorizers are still sufficient for a provably convergent optimization scheme under quite general assumptions. Numerical results illustrate that by applying this scheme, one can often obtain superior local optima compared to previous majorization-minimization methods, when the nonconvex majorizers are solved to global optimality. Finally, we illustrate the behavior of our algorithm for depth super-resolution from raw time-of-flight data.
Recent works have also proposed general frameworks for iteratively replacing the original minimization problem with simple approximation functions @math beyond majorization-minimization. @cite_2 analyzed approximation functions @math , satisfying @math for a proper growth function @math . A minimization scheme of these approximation functions exhibits subsequential convergence to critical points, even if the subproblem evaluations are inexact. These approximation functions need not necessarily be convex, but the distance of their subsequent evaluations must tend to zero. A slightly different generalization is discussed in @cite_44 , where approximation functions satisfying @math are examined. Here @math is a growth function and @math a Bregman distance generated by a 'kernel' function similarly to the previously discussed eq:intro_fb . Subsequence convergence can again be shown here, under relatively weak conditions. However the approximation function @math is taken to be convex in this work to, among other properties, guarantee the success of a backtracking scheme and reach an implementable algorithm.
@cite_44 @cite_2
1967138577 2038497950 2171413647 1836708065
In view of the minimization of a nonsmooth nonconvex function f, we prove an abstract convergence result for descent methods satisfying a sufficient-decrease assumption, and allowing a relative error tolerance. Our result guarantees the convergence of bounded sequences, under the assumption that the function f satisfies the Kurdyka–Łojasiewicz inequality. This assumption allows to cover a wide range of problems, including nonsmooth semi-algebraic (or more generally tame) minimization. The specialization of our result to different kinds of structured problems provides several new convergence results for inexact versions of the gradient method, the proximal method, the forward–backward splitting algorithm, the gradient projection and some proximal regularization of the Gauss–Seidel method in a nonconvex setting. Our results are illustrated through feasibility problems, or iterative thresholding procedures for compressive sensing. For the problem of minimizing a lower semicontinuous proper convex function f on a Hilbert space, the proximal point algorithm in exact form generates a sequence @math by taking @math to be the minimizes of @math , where @math . This algorithm is of interest for several reasons, but especially because of its role in certain computational methods based on duality, such as the Hestenes-Powell method of multipliers in nonlinear programming. It is investigated here in a more general form where the requirement for exact minimization at each iteration is weakened, and the subdifferential @math is replaced by an arbitrary maximal monotone operator T. Convergence is established under several criteria amenable to implementation. The rate of convergence is shown to be “typically” linear with an arbitrarily good modulus if @math stays large enough, in fact superlinear if @math . The case of @math is treated in extra detail. Applicati... We consider the minimization of a function G defined on @math , which is the sum of a (not necessarily convex) differentiable function and a (not necessarily differentiable) convex function. Moreover, we assume that G satisfies the Kurdyka---?ojasiewicz property. Such a problem can be solved with the Forward---Backward algorithm. However, the latter algorithm may suffer from slow convergence. We propose an acceleration strategy based on the use of variable metrics and of the Majorize---Minimize principle. We give conditions under which the sequence generated by the resulting Variable Metric Forward---Backward algorithm converges to a critical point of G. Numerical results illustrate the performance of the proposed algorithm in an image reconstruction application. We study the minimization of a convex function @math over the set of @math positive semi-definite matrices, but when the problem is recast as @math , with @math and @math . We study the performance of gradient descent on @math ---which we refer to as Factored Gradient Descent (FGD)---under standard assumptions on the original function @math . We provide a rule for selecting the step size and, with this choice, show that the local convergence rate of FGD mirrors that of standard gradient descent on the original @math : i.e., after @math steps, the error is @math for smooth @math , and exponentially small in @math when @math is (restricted) strongly convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to @math via a first-order oracle; for several problem instances, such proper initialization leads to global convergence guarantees. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization. To the best of our knowledge, this is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.