Spectral Algorithms

written by Theory Club

published November 05, 2018

We had another faculty talk this week, about how graphs, linear algebra, and algorithms come together in Spectral Algorithms by Dr. Richard Peng.

Here is the full abstract:

The study of large scale data sets in machine learning, statistics, and scientific computing is making increasing use of high performance algorithmic primitives. Tools such as linear systems solvers and convex optimization solvers are integrated in programming languages such as MATLAB, Python, and Julia, and taught as programming constructs in classes. On the other hand, the ever-increasing scale of data, as well as growth in data sources, creates a multitude of new challenges for these primitives: the running times of many, if not most, implementations of linear system solvers and convex optimization tools scale super-linearly with input sizes. Over the past three decades, works related to efficient solvers for a class of graph structured matrices, graph Laplacians, led to fundamental results in combinatorial optimization and scientific computing as well as the Laplacian paradigm for graph algorithms. In this talk I will survey these progresses, with focus on the underlying algorithm design approaches. Specifically, I will discuss the origin of algorithms that combine combinatorial and numerical building blocks via spectral graph theory, and describe recent efforts on designing new tools tailored towards the overall algorithmic questions.