Restricted invertibility revisited

Assaf Naor, Pierre Youssef

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Scopus citations

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 languageEnglish (US)
Title of host publicationA Journey through Discrete Mathematics
Subtitle of host publicationA Tribute to Jiri Matousek
PublisherSpringer International Publishing
Pages657-691
Number of pages35
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
DOIs
StatePublished - Jan 1 2017

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Restricted invertibility revisited'. Together they form a unique fingerprint.

  • Cite this

    Naor, A., & Youssef, P. (2017). Restricted invertibility revisited. In 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