When do convex relaxations return integer solutions? In this talk, I will discuss several instances of discrete optimization problems where, for a suitable distribution on inputs, LP and SDP relaxations produce integer solutions with high probability. This phenomenon has been studied in the context of LP decoding, sparse recovery, stochastic block models and so on. I will also mention some recent results for clustering problems: when points are drawn from a distribution over k sufficiently separated clusters, the well known k-median relaxation and a (not so well known) SDP relaxation for k-means exactly recover the clusters.

Spectral analysis of graphs has lead to powerful algorithms, for example in machine learning, in particular for regression, classification and clustering. Eigenfunctions of the Laplacian on a graph are a natural basis for analyzing functions on a graph. In this talk we discuss a new flexible set of basis functions, called Diffusion Wavelets, that allow for a multiscale analysis of functions on a graph, very much in the same way classical wavelets perform a multiscale analysis in Euclidean spaces. They allow efficient, representation, compression, denoising of functions on the graph, and are very well-suited for statistical learning tasks, as well as unsupervised algorithms. They are also associated with a multiscale decomposition of the graph, which has applications by itself, for example to the analysis of time series of graphs, and for defining families of new robust distances between graphs. We will discuss this construction with several examples, going from signal processing on manifolds and graphs, to some applications to clustering and learning.

ICA is a classical model of unsupervised learning originating and widely used in signal processing. In this model, observations in n-space are obtained by an unknown linear transformation of a signal with independent components. The goal is to learn the the transformation and thereby the hidden basis of the independent components. In this talk, we'll begin with a polynomial-time algorithm called Fourier PCA, for underdetermined ICA, the setting where the observed signal is in a lower dimensional space than the original signal, assuming a mild, verifiable condition on the transformation. Its analysis uses higher-order derivatives of Fourier transformations and anticoncentration of Gaussian polynomials. The running time and sample complexity are polynomial, but of high constant degree, for any constant error; a MATLAB implementation of the algorithm appears to need 10⁴ samples for 10-dimensional observations. We then present a more efficient recursive variant for the fully determined case of standard ICA that needs only a nearly linear number of samples and has polynomial time complexity. An implementation of this variant appears to outperform known heuristics. Its analysis is based on understanding the roots of random polynomials. This is joint work with Navin Goyal and Ying Xiao.

Graphs are a ubiquitous mathematical abstraction employed in numerous problems in science and engineering. Of particular importance is the need to find best structure-preserving matching of graphs. Sincegraph matching is a computationally intractable problem, numerous heuristics exist to approximate its solution. An important class of graph matching heuristics is relaxation techniques based on replacing the original problem by a continuous convex program. Conditions for applicability or inapplicability of such convex relaxations are poorly understood. In this talk, I will show easy to check spectral properties characterizing a wide family of graphs for which equivalence of convex relaxation to the exact graph matching is guaranteed to hold.

Several challenging problem in clustering, partitioning and imaging have traditionally been solved using the spectral technique. These problems include the normalized cut problem, the graph expander ratio problem, the Cheeger constant problem and the conductance problem. These problems share several common features: all seek a bipartition of a set of elements; the problems are formulated as a form of ratio cut equivalent to a quadratic ratio, referred to as the Rayleigh ratio. The Rayleigh ratio optimization is defined on discrete variables and a single sum constraint which we call the balance or orthogonality constraint. The spectral method for these problems is tantamount to solving a relaxation of the Rayleigh problem omitting the discreteness constraints. On the other hand, the relaxation of the orthogonality constraint yields optimization problems that are interesting in their own right. It is shown that a new, combinatorial, algorithm solves these latter discrete problems in strongly polynomial time in O(mn\log{n^2/m}) for a graph on n nodes and m edges. The implemented algorithm, using HPF (Hochbaum's Pseudo-Flow) as subroutine, is efficient enough to solve these bi-partitioning problems on millions of elements and more than 300 million edges within a couple of minutes. It is also shown, via an experimental study, that the results of the combinatorial algorithm proposed often improve dramatically on the quality of the results of the spectral method as measured by the proximity to the optimum of the respective NP-hard problems.

Hodge Theory is a milestone bridging differential geometry and algebraic topology. It studies certain functions (called forms) on data rather than data points themselves, and brings an optimization perspective to decompose such functions adaptive to the underlying topology. Recently Hodge Theory inspires rising applications in computer vision, multimedia, statistical ranking, game and voting theory, in addition to traditional applications in mechanics etc. In this talk we give an introduction to Hodge Theory with examples in these applications.

I present on-going research on two applications where spectral methods may be helpful. The first application models human memory search as a random walk, but with a twist that only the first visit to a state is observable. The task is to estimate the transition matrix from such censored observations. The second application teaches humans a target labeling on a graph. The assumption is that, given a few initial labeled nodes in the graph, humans utilize a known algorithm to complete the labeling on the rest of the graph (think of mincut). The task is to select the smallest set of initial nodes so that the completed labeling equals the target, i.e. the inverse problem of graph-based semi-supervised learning. The goal of the talk is to generate discussions on the research challenges in these and other similar applications.

We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees and resemble W-cycles in the Multigrid method, our algorithm only requires spectral graph sparsifiers and is analogous to V-cycles.

Joint work with Dan Spielman.