[Home]   [  News]   [  Events]   [  People]   [  Research]   [  Education]   [Visitor Info]   [UCSD Only]   [Admin]
Home > Events > CCoM > Abstract
Search this site:

Extracting a well conditioned submatrix and the paving conjecture

Pierre Youssef
University of Alberta


Given U an n by m matrix, the aim is to extract a large number of linearly independent columns of U and estimate the smallest and the largest singular value of the restricted matrix. For that, we give two deterministic algorithms: one for a normalized version of the restricted invertibility principle of Bourgain-Tzafriri, and one for the norm of coordinate restriction problem due to Kashin-Tzafriri. Merging the two algorithms, we are able to extract a well-conditioned block inside U, improving a previous result due to Vershynin. We use this to attempt a proof of the paving conjecture which is known to be equivalent to the Kadison-Singer problem and was recently solved by Marcus-Spielman-Srivastava. Their proof is only existential. In our attempt, we fail to solve the conjecture; we give however a deterministic algorithm for the best previously known result on it due to Bourgain-Tzafriri.

Tuesday, October 28, 2014
11:00AM AP&M 2402