Combinatorial Preconditioners for Proximal Algorithms on Graphs.

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.