Fall 2017
=========
We meet 5:30--7:00 in Evans room 1011.
Thursday, September 28
-----------------------
| **Graph Clustering Algorithms** (:download:`slides <../pdfs/2017-09-28-schramm.pdf>` | `video `_)
| `Tselil Schramm `_ (`Simons Institute `_, UC Berkeley)
One of the greatest advantages of representing data with graphs is access to
generic algorithms for analytic tasks, such as clustering. In this talk I will
describe some popular graph clustering algorithms, and explain why they are
well-motivated from a theoretical perspective.
Thursday, October 19
--------------------
| **Spectral Sparsification of Graphs** (:download:`slides <../pdfs/2017-10-19-srivastava.pdf>`)
| `Nikhil Srivastava `_ (`Mathematics `_, UC Berkeley)
Many important properties of an undirected graph manifest themselves spectrally
in the eigenvalues or quadratic forms of matrices related to the graph. For
instance, the connectivity structure, electrical properties, and random walk
behavior of a graph are determined by its Laplacian matrix. A spectral
sparsifier of a graph G is a sparse graph H on the same set of vertices such
that the Laplacians of H and G are close, so that H captures the spectral
behavior of G while being much cheaper to store and perform computations on. We
survey a line of work showing that spectral sparsifiers with constant degree
exist for every graph and can be computed efficiently.
Thursday, November 30
---------------------
| **Data-Driven Methods for Learning Sparse Graphical Models** (`video `_)
| `Somayeh Sojoudi `_ (`EECS `_ and `Mechanical Engineering `_, UC Berkeley)
Learning models from data has a significant impact on many disciplines,
including computer vision, medical imaging, social networks, neuroscience and
signal processing. In the network inference problem, one may model the
relationships between the network components through an underlying inverse
covariance matrix. Learning this graphical model is often challenged by the
fact that only a small number of samples are available. Despite the popularity
of graphical lasso for solving this problem, there is not much known about the
properties of this statistical method as an optimization algorithm. In this
talk, we will develop new notions of sign-consistent matrices and
inverse-consistent matrices to obtain key properties of graphical lasso. In
particular, we will prove that although the complexity of solving graphical
lasso is high, the sparsity pattern of its solution has a simple formula if a
sparse graphical model is sought. Besides graphical lasso, there are several
techniques for learning graphical models. We will design an optimization-based
mathematical framework to study the performance of various techniques. We will
illustrate our results in different case studies.