Restricted invertibility revisited

Assaf Naor, Pierre Youssef

Research output: Chapter in Book/Report/Conference proceedingChapter

16 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

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

Fingerprint

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

Cite this