alternating direction method

Alternating direction algorithms for total variation deconvolution in image reconstruction

  • Tao Min
  • Junfeng Yang
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    Image restoration and reconstruction from blurry and noisy observation is known to be ill-posed. To stabilize the recovery, total variation (TV) regularization was introduced by Rudin, Osher and Fatemi in \cite{LIR92}, which has demonstrated superiority in preserving image edges. However, the nondifferentiability of TV makes the underlying optimization problems difficult to solve. In this paper, … Read more

    Sparse and Low-Rank Matrix Decomposition Via Alternating Direction Methods

  • Junfeng Yang
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , , ,

    The problem of recovering the sparse and low-rank components of a matrix captures a broad spectrum of applications. Authors in [4] proposed the concept of “rank-sparsity incoherence” to characterize the fundamental identifiability of the recovery, and derived practical sufficient conditions to ensure the high possibility of recovery. This exact recovery is achieved via solving a … Read more

    Alternating Direction Methods for Sparse Covariance Selection

  • Xiao-Ming Yuan
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The mathematical model of the widely-used sparse covariance selection problem (SCSP) is an NP-hard combinatorial problem, whereas it can be well approximately by a convex relaxation problem whose maximum likelihood estimation is penalized by the $L_1$ norm. This convex relaxation problem, however, is still numerically challenging, especially for large-scale cases. Recently, some efficient first-order methods … Read more

    Alternating Direction Augmented Lagrangian Methods for semidefinite programming

  • Donald Goldfarb
  • Zaiwen Wen
  • Wotao Yin
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We present an alternating direction method based on an augmented Lagrangian framework for solving semidefinite programming (SDP) problems in standard form. At each iteration, the algorithm, also known as a two-splitting scheme, minimizes the dual augmented Lagrangian function sequentially with respect to the Lagrange multipliers corresponding to the linear constraints, then the dual slack variables … Read more

    Row by row methods for semidefinite programming

  • Zaiwen Wen
  • Donald Goldfarb
  • Shiqian Ma
  • Katya Scheinberg
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , ,

    We present a row-by-row (RBR) method for solving semidefinite programming (SDP) problem based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n-1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order … Read more

    Joint minimization with alternating Bregman proximity operators

  • Heinz Bauschke
  • Patrick L. Combettes
  • Dominikus Noll
    • Categories Convex Optimization Tags , , , , , , , ,

    A systematic study of the proximity properties of Bregman distances is carried out. This investigation leads to the introduction of a new type of proximity operator which complements the usual Bregman proximity operator. We establish key properties of these operators and utilize them to devise a new alternating procedure for solving a broad class of … Read more