printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

center for computational mathematics seminar

pierre youssef

university of alberta

extracting a well conditioned submatrix and the paving conjecture

abstract:

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.

october 28, 2014

11:00 am

ap&m 2402

****************************