Satz von der eingeschränkten Invertierbarkeit

Der Satz von der eingeschränkten Invertierbarkeit (englisch restricted invertibility theorem), auch Satz von Bourgain-Tzafriri, ist ein mathematischer Satz aus der Funktionalanalysis. Das Theorem beschäftigt sich mit der Frage der Invertierbarkeit eines linearen Operators (respektive einer quadratischen Matrix) auf einem endlichdimensionalen $l_{p}^{n}$-Raum. Das Theorem hat bedeutende Anwendungen in der lokalen Theorie der Banach-Räume.

Der Satz wurde von Jean Bourgain und Lior Tzafriri bewiesen.

Eingeschränkte Invertierbarkeit

Notation:

• $l_{p}^{n}:=(\mathbb {R} ^{n},\|\cdot \|_{p}).$
• $l_{p}:=l_{p}^{\infty }$ ist der Folgenraum der $p$-summierbaren Folgen.
• $\|L\|$ ist die Operatornorm.
• $|S|$ ist die Kardinalität von $S$.

Aussage

Sei $L:l_{2}^{n}\to l_{2}^{n}$ ein linearer Operator, so dass für jeden Einheitsvektor $\{e_{1},\dots ,e_{n}\}$ gilt

$\|Le_{j}\|=1,\quad \forall j\in \{1,\dots ,n\}$.

Dann existieren universelle Konstanten $c,d>0$ und eine Index-Untermenge $S\subseteq \{1,\dots ,n\}$, welche mindestens

$|S|\geq {\frac {cn}{\|L\|^{2}}}$

Indizes hat, so dass für die Norm der Restriktion gilt

$\left\|\sum \limits _{i\in S}a_{i}Le_{i}\right\|^{2}\geq d\sum \limits _{i\in S}|a_{i}|^{2}$

wobei $\{a_{i}\}_{i\in S}$ beliebige Skalare sind.

Erläuterungen an einem Beispiel

Sei $L$ eine reelle $n\times n$-Matrix und $L_{S}$ bezeichnet die Restriktion von $L$ auf die Spalten mit Indizes in $S$

$L_{S}:=\sum \limits _{i\in S}Le_{i}.$

Es gilt nun für jeden Vektor $a\in \mathbb {R} ^{|S|}$, dass

$\left\|L_{S}a\right\|\geq d\|a\|.$

Betrachtet man nun den kleinsten Singulärwert (oder allgemeiner die Schatten-Norm)

$\sigma _{\operatorname {min} }(L_{S})=\min \limits _{\|x\|=1}\|L_{S}x\|$

dann gilt

$\sigma _{\operatorname {min} }(L_{S})\geq d>0$

und daraus folgt, dass $L_{S}$ invertierbar ist. Weiter besitzt $L_{S}$ mindestens $cn/\|L\|^{2}$ Spalten. Außerdem folgt aus der Konditionsnummer

$\kappa (L_{S})={\frac {\sigma _{\operatorname {max} }(L_{S})}{\sigma _{\operatorname {min} }(L_{S})}},$

dass die Operatornorm der Inversen nach oben beschränkt ist

$\|L_{S}^{-1}\|={\frac {\kappa (L_{S})}{\|L_{S}\|}}={\frac {\sigma _{\operatorname {max} }(L_{S})}{\|L_{S}\|\sigma _{\operatorname {min} }(L_{S})}}\leq {\frac {\sigma _{\operatorname {max} }(L_{S})}{d^{2}}}=:K.$

Verallgemeinerungen

Es existieren diverse Verallgemeinerungen und verwandte Aussagen (u. a. von Spielman-Srivastava, Vershynin und Naor-Youssef). Zum Beispiel kann die Restriktion der Einheitsvektoren $\|Le_{j}\|=1$ entfernt werden. Es existiert auch eine Version für unendlichdimensionale Räume.

Bourgain-Tzafriri-Vermutung

Eine Verallgemeinerung ist die Bourgain-Tzafriri-Vermutung (BT-Vermutung), welche äquivalent zum Kadison-Singer-Problem (KS-Problem) ist. Das KS-Problem wurde 2013 positiv gelöst und somit auch die BT-Vermutung.

Formulierung

Sei $L:l_{2}^{n}\to l_{2}^{n}$ ein linearer Operator, so dass für jeden Einheitsvektor $\{e_{1},\dots ,e_{n}\}$ gilt

$\|Le_{j}\|=1,\quad \forall j\in \{1,\dots ,n\}$.

Dann existiert eine universelle Konstante $c>0$, so das für jede positive Zahl $b>0$ mit

$\|L\|\leq b$

ein $m=m(b)\in \mathbb {N}$ und eine Partition $\{I_{j}\}_{j=1}^{m}$ von $\{1,\dots ,n\}$ existieren, so dass

$\left\|\sum \limits _{i\in I_{j}}a_{i}Le_{i}\right\|^{2}\geq c\sum \limits _{i\in I_{j}}|a_{i}|^{2},\qquad 1\leq j\leq m$

wobei $\{a_{i}\}_{i\in I_{j}}$ beliebige Skalare sind.

Literatur

• Assaf Naor und Pierre Youssef: Restricted invertibility revisited. Hrsg.: arXiv. 2016, doi:10.48550/ARXIV.1601.00948, arxiv:1601.00948 [abs]. 
• Daniel A. Spielman und Nikhil Srivastava: An Elementary Proof of the Restricted Invertibility Theorem. Hrsg.: arXiv. 2009, doi:10.48550/ARXIV.0911.1114, arxiv:0911.1114 [abs]. 
• J. Bourgain und L. Tzafriri: Invertibility of ‘large’ submatrices with applications to the geometry of Banach spaces and harmonic analysis. In: Israel Journal of Mathematics. Band 57, Nr. 2, 1987, S. 137–224, doi:10.1007/BF02772174.