Restricted invertibility revisited

Assaf Naor, Pierre Youssef

Research output: Chapter in Book/Report/Conference proceedingChapter

16 Scopus citations


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
Number of pages35
ISBN (Electronic)9783319444796
ISBN (Print)9783319444789
StatePublished - Jan 1 2017

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Economics, Econometrics and Finance
  • General Business, Management and Accounting
  • General Mathematics


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

Cite this