Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning

arXiv2002.12236MaRDI QIDQ6335715

Author name not available (Why is that?)

Publication date: 27 February 2020

Abstract: Structured convex optimization on weighted graphs finds numerous applications in machine learning and computer vision. In this work, we propose a novel adaptive preconditioning strategy for proximal algorithms on this problem class. Our preconditioner is driven by a sharp analysis of the local linear convergence rate depending on the "active set" at the current iterate. We show that nested-forest decomposition of the inactive edges yields a guaranteed local linear convergence rate. Further, we propose a practical greedy heuristic which realizes such nested decompositions and show in several numerical experiments that our reconditioning strategy, when applied to proximal gradient or primal-dual hybrid gradient algorithm, achieves competitive performances. Our results suggest that local convergence analysis can serve as a guideline for selecting variable metrics in proximal algorithms.

Has companion code repository: https://github.com/zhenzhangye/graph_TV_recond

This page was built for publication: Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning

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