We present a proximal quasi-Newton method in which the approximation of the Hessian has the special format of “identity minus rank one” (IMRO) in each iteration. The proposed structure enables us to effectively recover the proximal point. The algorithm is applied to @math -regularized least squares problems arising in many applications including sparse recovery in compressive sensing, machine learning, and statistics. Our numerical experiment suggests that the proposed technique competes favorably with other state-of-the-art solvers for this class of problems. We also provide a complexity analysis for variants of IMRO, showing that it matches known best bounds.
Shuffling the linear and quadratic terms and ignoring the constants in , it can equivalently be written as x^ k+1 = 1 2 |x-(x^k- f(x^k) |^2 +p(x) . Using the notion of @math operator we conclude that x^ k+1 = p (x^k- f(x^k) ). The iterative scheme of is the generalized gradient method" or proximal gradient method". Note that it actually coincides with steepest descent method in the absence of @math . It is also sometimes called Forward-backward Splitting Method" @cite_38 @cite_12 . It gets its name from the two separate stages during each iteration while minimizing ; the first stage is taking a forward step @math involving only @math , and the second stage is a backward step @math which involves only @math . Finding the proximal point may not be a trivial task in general, but for solving @math it can be computed efficiently because the @math -norm is separable.
@cite_38 @cite_12
2006262045 2951870246
We show that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties. This formulation makes it possible to derive existence, uniqueness, characterization, and stability results in a unified and standardized fashion for a large class of apparently disparate problems. Recent results on monotone operator splitting methods are applied to establish the convergence of a forward-backward algorithm to solve the generic problem. In turn, we recover, extend, and provide a simplified analysis for a variety of existing iterative methods. Applications to geometry texture image decomposition schemes are also discussed. A novelty of our framework is to use extensively the notion of a proximity operator, which was introduced by Moreau in the 1960s. The proximity operator of a convex function is a natural extension of the notion of a projection operator onto a convex set. This tool, which plays a central role in the analysis and the numerical solution of convex optimization problems, has recently been introduced in the arena of signal processing, where it has become increasingly important. In this paper, we review the basic properties of proximity operators which are relevant to signal processing and present optimization methods based on these operators. These proximal splitting methods are shown to capture and extend several well-known algorithms in a unifying framework. Applications of proximal methods in signal recovery and synthesis are discussed.