Die Mathe-Redaktion - 25.04.2019 02:37 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 234 Gäste und 10 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Fabi Dune ligning
Lineare Algebra » Matrizenrechnung » Zeilen von V in reduzierter SVD haben Norm 1
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Zeilen von V in reduzierter SVD haben Norm 1
C_der_Baum
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.02.2017
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-03-20


Hey ihr,

beim Implementieren von einer SVD-updating-procedure kam ich auf folgende Beobachtung:
Für eine Rang-$r$ Matrix $A\in \mathbb{R}^{m\times n}$ haben wir die reduzierte SVD $A=USV^T$ mit $U\in \mathbb{R}^{m\times r}$, $S\in \mathbb{R}^{r\times r}$ und $V\in \mathbb{R}^{n\times r}$, wobei $U$ und $V$ jeweils orthogonale Spalten der Norm 1 haben. Sei nun $A_i$ (die $i$-te Spalte von A) NICHT im Spann der anderen Spalten $A_1,\dots,A_{i-1},A_{i+1},\dots,A_n$, also lapidar gesprochen, $A_i$ ist aktiv am Rang $r$ beteiligt, dann hat die $i$-te Zeile von $V$ Norm 1,

$||(V^T)_i||=1$.

Fällt irgendjemandem etwas dazu ein? Ich hab einige Beispiele durchgerechnet, konnte es jedesmal verifizieren. Leider habe ich keine geometrische Anschauung für die Zeile von $V$.

Wäre über jeden Hinweis dankbar.

Grüße



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2107
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-03-20


Hallo,

beachte, dass V orthogonal ist.



  Profil  Quote  Link auf diesen Beitrag Link
C_der_Baum
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.02.2017
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-03-20


Danke für die Ergänzung. Bei einer SVD (Singular Value Decomposition) sind $U$ und $V$ natürlich orthogonale Matrizen. Bei der reduzierten Form haben wir natürlich keine quadratische Matrizen mehr und $U$ und $V$ haben "nur" noch orthogonale Spalten der Norm 1 (semi-orthogonal).



  Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 2107
Aus: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-03-20


Wenn $V\in\mathbb{R}^{n,r}$ mit $n>r$ und $V^TV=I_r$ gilt, dann haben alle Zeilen von $V$ eine Norm kleiner gleich 1 und die Norm mindestens einer Zeile ist echt kleiner als 1. Wir können die Spalten von $V$ doch zu einer ONB vom $\mathbb{R}^n$ ergänzen.

Ein Beipiel wäre
\[V=\begin{bmatrix}
1&0\\0&0\\0&-1
\end{bmatrix}.\]



  Profil  Quote  Link auf diesen Beitrag Link
C_der_Baum
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.02.2017
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-03-21


Deine Folgerungen sind richtig. Die Norm einer Zeile von $V$ ist echt kleiner als $1$ genau dann, wenn die zugehörige Spalte von $A$ im Spann der anderen Spalten liegt (das zumindest ist die Behauptung). In deinem Beispiel würde $V$ immer zu der SVD einer Matrix A korrespondieren, die eine Nullspalte als 2. Spalte hat, was der Trivialfall wäre. Aber auch andere Beispiele, wie

$
V=\begin{bmatrix}
(1/2)^{1/2} & 0\\ (1/2)^{1/2} & 0 \\ 0 & -1
\end{bmatrix},
$

was eine gültige semi-orthogonale Matrix darstellt, liefert immer Matrizen $A$ mit der letzen Spalte nicht im Spann der anderen (wobei die anderen Spalten jeweils schon im Spann der (nochmals) anderen liegen). Z.B.

$U=\begin{bmatrix}
0 & (1/2)^{1/2} \\ 1 & 0 \\  0 &(1/2)^{1/2} \\
\end{bmatrix}$

und

$S=I_{2\times 2}$

liefern

$USV^T=\begin{bmatrix}
0 & 0 & -(1/2)^{1/2}\\
(1/2)^{1/2} & (1/2)^{1/2} & 0 \\
0 & 0 & -(1/2)^{1/2}
\end{bmatrix}$,

eine Matrix, bei der nur die letzte (dritte) Spalte nicht im Spann der anderen liegt. Das deckt sich mit: die letzte (dritte) Zeile von $V$ hat Norm $1$.

Verschiedene Ansätze könnten das Problem vereinfachen:

1. Man ordnet die $j$ Spalten, die jeweils linear unabhängig sind, an den Anfang der Matrix $A$ und versucht dann die Aussage für die ersten $j$ Spalten zu bekommen.

2. Auf deinem Kommentar beruhend: Man zeigt, dass die Einträge der zu den linear unabhängigen Spalten korrespondieren Zeilen von $V$, die man bekommt, wenn man die komplette Matrix $V$ (also die komplette SVD) betrachtet, alle $0$ sind.

Ich probiere noch ein wenig rum.
Danke schon mal!



  Profil  Quote  Link auf diesen Beitrag Link
C_der_Baum
Junior Letzter Besuch: im letzten Monat
Dabei seit: 26.02.2017
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-03-24


Ich hab einen Beweis, hoffe der geht so durch:



Consider the compact SVD of the rank-$r$ matrix $A=USV^T$ with $U\in \mathbb{R}^{m\times r}$, $S\in \mathbb{R}^{r\times r}$ and $V\in \mathbb{R}^{n\times r}$. For the $i$-th column of $A$, $A_i$, and the $i$-th row of $V$, $v_i$, it then holds that $A_i\notin \text{Span}(A_1,\dots,A_{i-1},A_{i+1},\dots,A_n)$ if and only if $\langle v_i,v_j\rangle =\delta_{ij}\enspace \forall j=1,\dots,n$.

($\Rightarrow$)
Consider $k=[k_1,\dots,k_n]^T\in \ker(A)$ for which holds


$\label{Lemmaoneweek}
0=Ak=\begin{bmatrix}
a_{11}k_1+\dots+a_{1n}k_n\\\vdots \\a_{m1}k_1+\dots +a_{mn}k_n
\end{bmatrix}=k_1A_1+\dots+k_iA_i+\dots+k_nA_n.
$


Furthermore, the following implications hold:

$
A_i\notin \text{Span}(A_1,\dots,A_{i-1},A_{i+1},\dots,A_n)$

$\Rightarrow A_i\neq \sum_{j\neq i}\lambda_j A_j \enspace \forall \lambda_j\in  \mathbb{R}, j=1,\dots,i-1,i+1,\dots ,n$

$\Rightarrow \left(0=\lambda A_i+\sum_{j\neq i}\lambda_jA_j,\enspace \lambda\in \mathbb{R}\enspace \Rightarrow \lambda=0\right).$  

Combining that with the kernel equation above, we obtain that if $A_i$ is not in the span of the other columns of $A$ then $k_i$ is zero for any arbitrary kernel element $k$. Thus, it also holds for any basis vector of any basis of the kernel of $A$. Therefore, if we were to complete $V$ such that it becomes an orthonormal basis of $\mathbb{R}^n$ the vectors to be appended all have a zero entry in the $i$-th entry. This means that the $i$-th row of $V$ already was of norm $1$ and because the rows of the completed $V$ are orthonormal to all other rows, the $i$-th row of the compact $V$ must already be orthogonal to all others.

($\Leftarrow$) Reciprocally, suppose that $A_i\in \text{Span}(A_1,\dots,A_{i-1},A_{i+1},\dots,A_n)$, then this implies that

$
\exists \lambda_1,\dots,\lambda_{i-1},\lambda_{i+1},\dots,\lambda_n\in \mathbb{R}\enspace :\enspace
0=-A_i+\sum_{j\neq i}\lambda_j A_j.
$

Choosing $k=[\lambda_1,\dots,\lambda_{i-1},-1,\lambda_{i+1},\dots,\lambda_n]^T$ yields that $k\in \ker(A)$ with the $i$-th component non-zero. This means that for every basis of the kernel of $A$ there must exist a basis vector with the $i$-th component non-zero. Again, if we were to complete $V$ to be an orthonormal basis of $\mathbb{R}^n$ it would append an element to the $i$-th row of $V$ that is non zero which means that $v_i$ was not of norm $1$.



  Profil  Quote  Link auf diesen Beitrag Link
C_der_Baum hat die Antworten auf ihre/seine Frage gesehen.
C_der_Baum wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]