Diagonal preconditioning for first order primal-dual algorithms in convex optimization
Top Cited Papers
- 1 November 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 1762-1769
- https://doi.org/10.1109/iccv.2011.6126441
Abstract
In this paper we study preconditioning techniques for the first-order primal-dual algorithm proposed in [5]. In particular, we propose simple and easy to compute diagonal preconditioners for which convergence of the algorithm is guaranteed without the need to compute any step size parameters. As a by-product, we show that for a certain instance of the preconditioning, the proposed algorithm is equivalent to the old and widely unknown alternating step method for monotropic programming [7]. We show numerical results on general linear programming problems and a few standard computer vision problems. In all examples, the preconditioned algorithm significantly outperforms the algorithm of [5].Keywords
This publication has 12 references indexed in Scilit:
- A First-Order Primal-Dual Algorithm for Convex Problems with Applications to ImagingJournal of Mathematical Imaging and Vision, 2010
- A Unified Primal-Dual Algorithm Framework Based on Bregman IterationJournal of Scientific Computing, 2010
- An algorithm for minimizing the Mumford-Shah functionalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Curvature regularity for region-based image segmentation and inpainting: A linear programming relaxationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- Graph Cuts via $\ell_1$ Norm MinimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Aspects of Total Variation RegularizedL1Function ApproximationSIAM Journal on Applied Mathematics, 2005
- Convex OptimizationPublished by Cambridge University Press (CUP) ,2004
- A Variational Approach to Remove Outliers and Impulse NoiseJournal of Mathematical Imaging and Vision, 2004
- An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in VisionPublished by Springer Nature ,2001
- Monotone Operators and the Proximal Point AlgorithmSIAM Journal on Control and Optimization, 1976