Restricted Invertibility

Given a matrix A which is n x m, the image of A (viewed as a linear operator) is the space spanned by its m columns {c_1, ..., c_m} . The rank of A, denoted r, can be defined either as the size of the maximum set of linearly independent columns in A, or equivalently as the number of non-zero singular values of A. In many cases, the minimum non-zero singular value of A may be very close to zero, which makes it unsuitable for applications.

Restricted invertibility asks for the following: Is there a restriction of A to a large representative subset S \subseteq [m] of its columns, so that the minimum non-zero singular value of A_S is far from zero? This intuitively asks for the following: is there a large subset of the big columns of A that are not only linearly independent, but also as 'orthogonal' to each other as possible? Spielman and Srivastava give a beautiful proof that shows that there is  such a subset S of size roughly equal to a quantity called the 'stable rank' of A.

This question turns up in problems related to Banach space theory, differential privacy, and numerical algebra systems. The proof requires only basic linear algebra as a prerequisite. Furthermore, the proof technique has been used in various other places: showing the existence of expanders, and the solution of the longstanding Kadison-Singer problem in physics. We will have a look at the proof in this talk.