Abstract
Suppose that m, nεN and that A:Rm→Rn is a linear operator. It is shown here that if k, rεN satisfy k<r≤rank(A) then there exists a subset σ ⊇ {1,…, m} with | σ | = k such that the restriction of A to Rσ⊇Rm is invertible, and moreover the operator norm of the inverse A-1:A(Rσ)→Rm is at most a constant multiple of the quantity (formula presented), where s1(A)≥…≥sm(A) are the singular values of A. This improves over a series of works, starting from the seminal Bourgain-Tzafriri Restricted Invertibility Principle, through the works of Vershynin, Spielman-Srivastava and Marcus-Spielman-Srivastava. In particular, this directly implies an improved restricted invertibility principle in terms of Schatten-von Neumann norms.
Original language | English (US) |
---|---|
Title of host publication | A Journey through Discrete Mathematics |
Subtitle of host publication | A Tribute to Jiri Matousek |
Publisher | Springer International Publishing |
Pages | 657-691 |
Number of pages | 35 |
ISBN (Electronic) | 9783319444796 |
ISBN (Print) | 9783319444789 |
DOIs | |
State | Published - Jan 1 2017 |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Economics, Econometrics and Finance
- General Business, Management and Accounting
- General Mathematics