%0 Journal Article %1 ss12 %A Spielman, Daniel A. %A Srivastava, Nikhil %D 2012 %I The Hebrew University Magnes Press %J Israel Journal of Mathematics %K column.subset restricted.invertibility sparsification %N 1 %P 83-91 %R 10.1007/s11856-011-0194-2 %T An Elementary Proof of the Restricted Invertibility Theorem %V 190 %X We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.

@article{ss12, abstract = {We give an elementary proof of a generalization of Bourgain and Tzafriri’s Restricted Invertibility Theorem, which says roughly that any matrix with columns of unit length and bounded operator norm has a large coordinate subspace on which it is well-invertible. Our proof gives the tightest known form of this result, is constructive, and provides a deterministic polynomial time algorithm for finding the desired subspace.}, added-at = {2013-07-06T00:30:23.000+0200}, author = {Spielman, Daniel A. and Srivastava, Nikhil}, biburl = {https://www.bibsonomy.org/bibtex/236bdd4aa3ae75a5f883f89fa4138e687/ytyoun}, doi = {10.1007/s11856-011-0194-2}, interhash = {935a875db9b306a4c41f69ee855bef7f}, intrahash = {36bdd4aa3ae75a5f883f89fa4138e687}, issn = {0021-2172}, journal = {Israel Journal of Mathematics}, keywords = {column.subset restricted.invertibility sparsification}, language = {English}, number = 1, pages = {83-91}, publisher = {The Hebrew University Magnes Press}, timestamp = {2014-02-04T22:52:14.000+0100}, title = {An Elementary Proof of the Restricted Invertibility Theorem}, volume = 190, year = 2012 }