Combinatorial Preconditioners for Proximal Algorithms on Graphs.

RSS Source
Thomas Möllenhoff, Zhenzhang Ye, Tao Wu, Daniel Cremers

We present a novel preconditioning technique for proximal optimizationmethods that relies on graph algorithms to construct effective preconditioners.Such combinatorial preconditioners arise from partitioning the graph intoforests. We prove that certain decompositions lead to a theoretically optimalcondition number. We also show how ideal decompositions can be realized usingmatroid partitioning and propose efficient greedy variants thereof forlarge-scale problems. Coupled with specialized solvers for the resulting scaledproximal subproblems, the preconditioned algorithm achieves competitiveperformance in machine learning and vision applications.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.