html xmlns="http://www.w3.org/1999/xhtml"> 15-859N: Spectral Graph Theory with Applications to ML, Spring 2020

The class will be a ZOOM meeting ZOOM. It will be held at the usual times. The first zoom class will be Wednesday Mar 18.

Course Information

Instructors:
Gary Miller (Office Hours: Monday 2-3PM and Thursday 2-3PM )
To join the office hours click this link. ZOOM-OH.
Teaching Assistant: Timothy Chu (Office Hours: Tuesday 10:30-11:30AM GHC 5103 )
First Class: Monday January 13th
Place/Time: GHC 4102, MWF 10:30 - 11:50AM.
Course Secretary: Erin E. Davis (Office: GHC 7123)
Official Course Blog will be Piazza: cmu-15-859N Piazza Please signup.

Announcements

  • Corrected typo in Homework 5 PDF. It is due on Monday, April 27th.
  • Homework 5 is out PDF. It is due on Monday, April 27th. We have not determined the method of handin.
  • The class will be a ZOOM meeting ZOOM . It will be held at the usual times.
  • Homework 4 is out PDF. It is due on Friday, March 28th. We have not determined the method of handin.
  • Homework 3 is out PDF. It is due on Friday, February 28th, in class.
  • The Scheduled Final Time is May 4th 8:30-11:30AM. Our intention is to use this time for project presentations.
  • Clarification have been added to Homework 2 PDF.
  • Homework 2 is out PDF. It is due on Friday, February 14, in class.
  • Homework 1 is out PDF. It is due on Friday, January 31, in class.
  • We have add a section to the resources page containing Professor Kolter notes and lectures on linear algebra. Hopefully these resources should help with homework 0.
  • Linear Algebra review will take place in GHC 8102 at 7PM Tuesday Jan 21.
  • Homework 0 is out PDF. It is due on Tuesday evening on January 21th in the review session.
  • Overview

    At a very high level the course shows how one can use linear algebra to solve fundamental problems in computer science much more efficiently. Many of the problems that these approaches apply to are graph problems such as graph cut and the maximum flow problems, giving almost linear time algorithms. The opposite is also true, we will use graph algorithms to solve problems in linear algebra. This interplay is what will give us these very fast algorithms. The key to these new algorithms is the use of numerical analysis and methods, iterative algorithms. There was a major revolution in algorithms for linear programming in the 1980's and 1990's, which at a high level, can be attributed to the use of Newton's iterative method to find a good approximation to the linear program. Over the last two decades computer scientists starting with Vaidya have introduced the use of Conjugate Gradient and Chebyshev iterations to solve problems such as maximum flow. In the last few months advances have been made using Nesterov iterations. Critical to these new methods are new graph algorithms. One key idea is that of graph sparsification, given a graph and find a new graph with substantially fewer edges that is similar to the original one. In turn finding these sparse graphs uses the design of new types of spanning trees. We two we will discuss are low stretch trees and Bartal Steiner trees.

    This class will cover material from three areas: Spectral Graph Theory, Numerical Linear Algebra, and the application to problem in CS.

    The central issue in spectral graph theory is understanding, estimating, and finding eigenvectors and eigenvalues of graphs. The study of random walks on a graph was one of the first users of spectral graph theory. Answering such questions as: How many times should you shuffle a deck of cards to insure that the deck is "well shuffled"? More recent application include Google's page rank algorithm which performs a random walk on the hyperlink graph of the Internet. It has also been applied to the problem of finding these eigenvectors as well as solving related linear systems.