Robust PCA is the well known task of recovering a low rank matrix from measurements corrupted with sparse noise. A popular recovery method is convex relaxation, where the rank and sparsity constraints are replaced by their convex surrogates. This can provably recover the low rank and sparse components under natural constraints such as incoherence and sparsity. In this talk, I will describe how non-convex methods can provably solve the robust PCA problem and also match the guarantees for the convex method. At the same time, our non-convex method has significantly lower computational complexity, since it involves finding only low rank approximations of the observed matrix. Thus, non-convex methods can achieve best of both the worlds: guaranteed recovery and low computational complexity.

This is joint work with Praneeth Netrapalli, U N Niranjan, Prateek Jain, and Sujay Sanghavi.

We describe a seriation algorithm for ranking a set of n items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compare similarly with all others. It does so by constructing a similarity matrix from pairwise comparisons, using seriation methods to reorder this matrix and construct a ranking. We first show that this spectral seriation algorithm recovers the true ranking when all pairwise comparisons are observed and consistent with a total order. We then show that ranking reconstruction is still exact even when some pairwise comparisons are corrupted or missing, and that seriation based spectral ranking is more robust to noise than other scoring methods. An additional benefit of the seriation formulation is that it allows us to solve semi-supervised ranking problems. Experiments on both synthetic and real datasets demonstrate that seriation based spectral ranking achieves competitive and in some cases superior performance compared to classical ranking methods.

This is joint work with Fajwel Fogel and Milan Vojnovic.

We present joint work with Rainer Sinn on the algebraic geometry that underlies semidefinite programming. Our focus is on spectrahedral shadows, that is, convex sets representable by linear matrix inequalities. We characterize the polynomials that vanish on the boundary of a spectrahedral shadow when the defining matrices are generic. The colorful pictures shown in this lecture can be enjoyed by everyone.

The positive semidefinite (psd) rank of a nonnegative real matrix M is the smallest integer k for which it is possible to find psd matrices A_i assigned to the rows of M and B_j assigned to the columns of M, of size k x k, such that (i,j)-entry of M is the inner product of A_i and B_j. This is an example of a cone rank of a nonnegative matrix similar to nonnegative rank, and was introduced for studying sdp-representations of convex sets. I will present the main results and open questions we have so far on psd rank. The talk will be largely based on a recent survey written with Hamza Fawzi, Joao Gouveia, Pablo Parrilo and Richard Robinson.

It is not so surprising that quantum mechanics presents hard new problems for optimization. For example, finding the lowest energy configuration of a physical system or simulating its dynamics both become more computationally difficult when we consider quantum systems. Less obvious is that the mathematics of quantum information can yield new methods of analyzing classical hard problems in optimization. In both directions, the link involves optimization problems related to tensors and polynomials. I will survey connections in both directions and discuss some promising open problems.

The talk will not assume a background in quantum information theory. It is partly based on arXiv preprints 1205.4484, 1210.6367 and 1310.0017.

Convex relaxations based on different hierarchies of linear/semi–definite programs have been used recently to devise approximation algorithms for various optimization problems. The approximation guarantee of these algorithms improves with the number of rounds r in the hierarchy, though the complexity of solving (or even writing down the solution for) the r'th level program grows as $n^{\Omega(r)}$ where n is the input size.

In this work, we observe that many of these algorithms are based on local rounding procedures that only use a small part of the SDP solution (of size $n^{O(1)}2^{O(r)}$ instead of $n^{\Omega(r)}$). We give an algorithm to find the requisite portion in time polynomial in its size. The challenge in achieving this is that the required portion of the solution is not fixed a priori but depends on other parts of the solution, sometimes in a complicated iterative manner. Our solver leads to $poly(n) 2^{O(r)}$ time algorithms to obtain the same guarantees in many cases as the earlier $n^{O(r)}$ time algorithms based on r rounds of the Lasserre/SOS hierarchy. In particular, guarantees based on $O(\log n)$ rounds can be realized in polynomial time.

Joint work with Venkatesan Guruswami.

The study of first-order methods has largely dominated research in continuous optimization for the last decade, yet still the range of problems for which optimal first-order methods have been developed is surprisingly limited, even though much has been achieved in some areas with high profile, such as compressed sensing.

We present a simple transformation of any linear (or semidefinite or hyperbolic) program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable. We observe, moreover, that the objective function is naturally smoothed, thereby allowing most first-order methods to be applied.

We develop complexity bounds in the unsmoothed case for a particular subgradient method, and in the smoothed case for Nesterov's original optimal first-order method for smooth functions. We achieve the desired bounds on the number of iterations.

Perhaps most surprising is that the transformation is simple and so is the basic theory, and yet the approach has been overlooked until now, a blind spot. Once the transformation is realized, the remaining effort in establishing complexity bounds is mainly straightforward, by making use of various works of Nesterov.