Abstract
Controlling the eigenvalues of a matrix is an important part of optimization, as many times the condition number of a matrix dictates the effectiveness (or time complexity) of an algorithm. We will discuss various problems relating to controlling eigenvalues; in particular, finding large subsets of well-conditioned vectors inside a given (not well-conditioned) set and dividing sets of vectors into subsets each of which as similar condition number top the original. This will make use of a new probabilistic existence argument we call the "method of interlacing polynomials." Only one of the results we discuss has an algorithmic version (and the algorithm is somewhat independent from the method) and so we will discuss a number of open algorithmic questions.
This is joint work with Dan Spielman and Nikhil Srivastava.