Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian Matrix, appears ubiquitously in mathematical physics. Due to the discovery of very fast solvers for these equations, they are becoming increasingly popular in combinatorial optimization and machine learning.
This talk describes ongoing work on faster algorithms for image processing and related problems. We present an algorithm for solving mixed L2-L1 minimization that extends recent works on approximating graph cuts using electrical flows. These minimization problems, which we call grouped least squares, generalize key tools from image processing such as the total variation objective. They also give insights for graph algorithms, leading to faster algorithms for multicommodity flow and speedups to the electrical flow framework on separable graphs.
Topics in this talk represent joint work with Hui Han Chin, Jon Kelner, Aleksander Madry and Gary Miller.