Combinatorial Preconditioners for Proximal Algorithms on Graphs
  We present a novel preconditioning technique for proximal optimization
methods that relies on graph algorithms to construct effective preconditioners.
Such combinatorial preconditioners arise from partitioning the graph into
forests. We prove that certain decompositions lead to a theoretically optimal
condition number. We also show how ideal decompositions can be realized using
matroid partitioning and propose efficient greedy variants thereof for
large-scale problems. Coupled with specialized solvers for the resulting scaled
proximal subproblems, the preconditioned algorithm achieves competitive
performance in machine learning and vision applications.
