A stochastic variance reduced primal dual fixed point method for linearly constrained separable optimization

DOI10.1137/20M1354398zbMATH Open1474.65042arXiv2007.11783OpenAlexW3200236211MaRDI QIDQ5860367FDOQ5860367

Authors: Ya-Nan Zhu, Xiaoqun Zhang 

Publication date: 19 November 2021

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Abstract: In this paper we combine the stochastic variance reduced gradient (SVRG) method [17] with the primal dual fixed point method (PDFP) proposed in [7] to solve a sum of two convex functions and one of which is linearly composite. This type of problems are typically arisen in sparse signal and image reconstruction. The proposed SVRG-PDFP can be seen as a generalization of Prox-SVRG [37] originally designed for the minimization of a sum of two convex functions. Based on some standard assumptions, we propose two variants, one is for strongly convex objective function and the other is for general convex cases. Convergence analysis shows that the convergence rate of SVRG-PDFP is O(1/k) (here k is the iteration number) for general convex objective function and linear for k strongly convex case. Numerical examples on machine learning and CT image reconstruction are provided to show the effectiveness of the algorithms.

Full work available at URL: https://arxiv.org/abs/2007.11783

Recommendations

• Stochastic primal dual fixed point method for composite optimization
• An analysis of stochastic variance reduced gradient for linear inverse problems ^*
• A proximal stochastic gradient method with progressive variance reduction
• A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions
• Efficient primal-dual fixed point algorithms with dynamic stepsize for composite convex optimization problems

zbMATH Keywords

image restorationstochastic variance reduced gradientprimal dual fixed point method

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Convex analysis and monotone operator theory in Hilbert spaces
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the global and linear convergence of the generalized alternating direction method of multipliers
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• Signal Recovery by Proximal Forward-Backward Splitting
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Proximity algorithms for image models: denoising
• A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• Convergence of stochastic proximal gradient algorithm
• Efficient online and batch learning using forward backward splitting
• Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
• A generalized forward-backward splitting
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Optimal Primal-Dual Methods for a Class of Saddle Point Problems
• Stochastic primal dual fixed point method for composite optimization
• New Proximal Point Algorithms for Convex Minimization
• Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications

Cited In (3)

• A stochastic primal-dual method for a class of nonconvex constrained optimization
• Federated primal dual fixed point algorithm
• A stochastic variance reduction algorithm with Bregman distances for structured composite problems

Uses Software

• LIBSVM
• ElemStatLearn
• Saga

This page was built for publication: A stochastic variance reduced primal dual fixed point method for linearly constrained separable optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5860367)