On the submatrices with the best-bounded inverses

Titel: Über Submatrizen mit den am besten beschränkten Inversen

Autoren: Richik Sengupta und Mikhail Pautov
Thema: Beweis einer Hypothese von Goreinov, Tyrtyshnikov und Zamarashkin für den Fall $k=2$.

1. Problemstellung

Das Paper adressiert ein offenes Problem aus der numerischen linearen Algebra, das ursprünglich von Goreinov, Tyrtyshnikov und Zamarashkin in [1] formuliert wurde.

Die Hypothese:
Sei $U$ eine reelle $n \times k$-Matrix mit orthonormalen Spalten ($n > k$). Es wird vermutet, dass es stets eine $k \times k$-Submatrix $Q$ von $U$ gibt, deren kleinster singulärer Wert $\sigma_k(Q)$ durch
$$\sigma_k(Q) \geq \frac{1}{\sqrt{n}}$$
beschränkt ist. Äquivalent dazu ist die Aussage, dass die Spektralnorm der Inversen dieser Submatrix $\sqrt{n}$ nicht überschreitet.

Status vor der Arbeit:
Die Hypothese ist für den trivialen Fall $n \leq 4$ (mit $k=2$) bereits bewiesen (insbesondere für $n=4$ durch Y. Nesterenko). Für alle nicht-trivialen Fälle mit $1 < k < n-1$ blieb das Problem jedoch offen, obwohl es durch numerische Experimente gestützt wurde.

Ziel der Arbeit:
Die Autoren liefern einen vollständigen Beweis für den Fall $k=2$ (d.h. für Matrizen mit zwei orthonormalen Spalten) für beliebiges $n$.

2. Methodik und Beweisstrategie

Der Beweis erfolgt durch Induktion über $n$ unter der Annahme, dass die Hypothese für $n-1$ Zeilen bereits gilt. Der Fall $k=2$ wird in zwei Hauptfälle unterteilt, basierend auf den Normen der Zeilenvektoren der Matrix $A \in \mathbb{R}^{n \times 2}$ (wobei $A^T A = I$).

Fall A: Existenz einer Zeile mit kleiner Norm

• Annahme: Es existiert eine Zeile $i$, sodass $\|r_i\|^2 = A_{i1}^2 + A_{i2}^2 \leq \frac{1}{n}$.
• Strategie:
  1. Durch eine Rotation $P \in \mathbb{R}^{2 \times 2}$ wird die Matrix so transformiert, dass die erste Zeile die Form $(b, 0)$ hat, wobei $b^2 \leq \frac{1}{n}$.
  2. Falls $b=0$, kann die erste Zeile entfernt werden. Die verbleibende $(n-1) \times 2$-Matrix hat orthonormale Spalten. Nach der Induktionsannahme existiert dort eine Submatrix mit $\sigma_2 \geq \frac{1}{\sqrt{n-1}} \geq \frac{1}{\sqrt{n}}$.
  3. Falls $b > 0$, wird die restliche Matrix $C$ (ohne erste Zeile) skaliert, um eine Matrix $\hat{C}$ mit orthonormalen Spalten zu erhalten.
  4. Durch Anwendung der Induktionsannahme auf $\hat{C}$ und Nutzung der Invarianz der singulären Werte unter Multiplikation mit Diagonalmatrizen wird gezeigt, dass die ursprüngliche Submatrix die geforderte untere Schranke erfüllt.

Fall B: Alle Zeilennormen sind groß

• Annahme: Für alle Zeilen $i$ gilt $\|r_i\|^2 > \frac{1}{n}$.
• Strategie:
  1. Vektor-Transformation: Die Zeilenvektoren $r_i = (x_i, y_i)$ werden genutzt, um neue Vektoren $w_i = (x_i^2 - y_i^2, 2x_i y_i)$ zu definieren. Es wird gezeigt, dass $\sum w_i = 0$ und $\|w_i\|^2 = \|r_i\|^4$.
  2. Reduktion auf eine Ungleichung: Das Ziel ist der Nachweis, dass es ein Paar $(i, j)$ gibt, sodass $(r_i, r_j)^2 \leq (\|r_i\|^2 - \frac{1}{n})(\|r_j\|^2 - \frac{1}{n})$. Dies wird äquivalent umgeformt zu einer Bedingung an die Skalarprodukte der $w_i$ und einer Hilfsgröße $z_i = \|r_i\|^2 - \frac{2}{n}$.
  3. Widerspruchsbeweis (Proof by Contradiction):
     • Es wird angenommen, dass die Ungleichung für alle Paare $(i, j)$ verletzt ist.
     • Daraus wird eine Matrix $G = WW^T - zz^T$ konstruiert.
     • Rang-Argument: Da $W$ eine $n \times 2$-Matrix ist, hat $WW^T$ Rang $\leq 2$. Da $zz^T$ Rang 1 hat, ist $\text{Rang}(G) \leq 3$.
     • Eigenwert-Analyse: Es wird gezeigt, dass $G$ höchstens 2 positive Eigenwerte besitzt. Der Spurwert $\text{tr}(G)$ wird berechnet und ergibt $\frac{4}{n}$. Daraus folgt, dass der größte Eigenwert $\lambda_1 \geq \frac{2}{n}$ sein muss.
     • Perron-Frobenius-Theorem: Unter der Annahme des Widerspruchs wird eine Matrix $M = G + \frac{2}{n^2}E$ (mit $E$ als Einsen-Matrix) betrachtet, deren Elemente alle positiv sind. $M$ hat den Vektor $\mathbf{1}$ als Eigenvektor zum Eigenwert $\frac{2}{n}$. Nach Perron-Frobenius ist dies der einzige und größte Eigenwert von $M$.
     • Konflikt: Da $G\mathbf{1}=0$, sind die Eigenvektoren von $G$ im orthogonalen Komplement von $\mathbf{1}$ auch Eigenvektoren von $M$. Dies würde bedeuten, dass $\lambda_1$ (der größte Eigenwert von $G$) auch ein Eigenwert von $M$ ist, der strikt kleiner als $\frac{2}{n}$ sein muss. Dies steht im direkten Widerspruch zu $\lambda_1 \geq \frac{2}{n}$.
  4. Folgerung: Die Annahme des Widerspruchs ist falsch. Es existiert also ein Paar $(i, j)$, das die Ungleichung erfüllt.
  5. Abschluss: Für die entsprechende $2 \times 2$-Submatrix wird gezeigt, dass die charakteristische Polynom-Analyse in Kombination mit der gefundener Ungleichung impliziert, dass der zweite Eigenwert $\tilde{\lambda}_2 \geq \frac{1}{n}$ ist. Daraus folgt $\sigma_2 \geq \frac{1}{\sqrt{n}}$.

3. Wichtige Beiträge und Ergebnisse

• Lösung eines offenen Problems: Der erste vollständige analytische Beweis der Hypothese von Goreinov et al. für den Fall $k=2$ für beliebiges $n$.
• Neue Techniken: Die Kombination von Induktion, geometrischen Transformationen (Rotationen) und einer tiefgehenden spektralen Analyse (Eigenwertverteilung, Spur, Rang) unter Verwendung des Perron-Frobenius-Theorems.
• Konstruktive Existenz: Der Beweis zeigt nicht nur die Existenz, sondern liefert durch die Fallunterscheidung einen Weg, wie solche Submatrizen identifiziert werden können (entweder durch Weglassen einer kleinen Zeile oder durch Finden eines spezifischen Zeilenpaares).

4. Signifikanz

• Numerische Linearalgebra: Die Ergebnisse sind fundamental für das Verständnis der Stabilität von Submatrizen orthonormaler Matrizen. Dies ist relevant für Algorithmen wie die QR-Zerlegung, die Auswahl von Spalten in Überbestimmungssystemen und die Analyse von Konditionszahlen.
• Theoretische Implikationen: Der Beweis schließt eine Lücke in der Theorie der orthonormalen Frames. Er bestätigt, dass die "schlechteste" mögliche Submatrix (im Sinne des kleinsten singulären Werts) immer noch eine garantierte untere Schranke von $1/\sqrt{n}$ besitzt, was für die Fehleranalyse in numerischen Verfahren entscheidend ist.
• Zukunftsausblick: Da der Fall $k=2$ gelöst ist, bietet diese Arbeit methodische Ansätze (insbesondere die spektrale Analyse der Matrix $G$), die möglicherweise auf den Fall $k > 2$ übertragen werden können, um das allgemeine Problem zu lösen.