### Abstract

Suppose that m, nεN and that A:R^{m}→R^{n} 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σ⊇R^{m} is invertible, and moreover the operator norm of the inverse A-1:A(Rσ)→R^{m} is at most a constant multiple of the quantity (formula presented), where s_{1}(A)≥…≥s_{m}(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 |

### Fingerprint

### ASJC Scopus subject areas

- Computer Science(all)
- Mathematics(all)
- Economics, Econometrics and Finance(all)
- Business, Management and Accounting(all)

### Cite this

*A Journey through Discrete Mathematics: A Tribute to Jiri Matousek*(pp. 657-691). Springer International Publishing. https://doi.org/10.1007/978-3-319-44479-6_27