TY - GEN
T1 - Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing
AU - Koutis, Ioannis
AU - Miller, Gary L.
AU - Tolliver, David
N1 - Funding Information:
This work was partially supported by the National Science Foundation under grant number CCF-0635257 and the University of Pittsburgh Medical Center under award number A-006461.
PY - 2009
Y1 - 2009
N2 - Linear systems and eigen-calculations on symmetric diagonally dominant matrices (SDDs) occur ubiquitously in computer vision, computer graphics, and machine learning. In the past decade a multitude of specialized solvers have been developed to tackle restricted instances of SDD systems for a diverse collection of problems including segmentation, gradient inpainting and total variation. In this paper we explain and apply the support theory of graphs, a set of of techniques developed by the computer science theory community, to construct SDD solvers with provable properties. To demonstrate the power of these techniques, we describe an efficient multigrid-like solver which is based on support theory principles. The solver tackles problems in fairly general and arbitrarily weighted topologies not supported by prior solvers. It achieves state of the art empirical results while providing robust guarantees on the speed of convergence. The method is evaluated on a variety of vision applications.
AB - Linear systems and eigen-calculations on symmetric diagonally dominant matrices (SDDs) occur ubiquitously in computer vision, computer graphics, and machine learning. In the past decade a multitude of specialized solvers have been developed to tackle restricted instances of SDD systems for a diverse collection of problems including segmentation, gradient inpainting and total variation. In this paper we explain and apply the support theory of graphs, a set of of techniques developed by the computer science theory community, to construct SDD solvers with provable properties. To demonstrate the power of these techniques, we describe an efficient multigrid-like solver which is based on support theory principles. The solver tackles problems in fairly general and arbitrarily weighted topologies not supported by prior solvers. It achieves state of the art empirical results while providing robust guarantees on the speed of convergence. The method is evaluated on a variety of vision applications.
UR - http://www.scopus.com/inward/record.url?scp=72549117301&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72549117301&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10331-5_99
DO - 10.1007/978-3-642-10331-5_99
M3 - Conference contribution
AN - SCOPUS:72549117301
SN - 3642103308
SN - 9783642103308
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1067
EP - 1078
BT - Advances in Visual Computing - 5th International Symposium, ISVC 2009, Proceedings
T2 - 5th International Symposium on Advances in Visual Computing, ISVC 2009
Y2 - 30 November 2009 through 2 December 2009
ER -