User:KYN/SingularValues

From Wikipedia, the free encyclopedia

Maybe this should be merged into singular value decomposition?

Let M be an m×n matrix with elements from the field K. Let $S m - 1$ and $S n - 1$ denote the sets of unit 2-norm vectors in $K m$ and $K n$ , respectively. Define the function

σ(u, v) = u T M v

for vectors $u \in S^{m-1}$ and $v \in S^{n-1}$ . The function σ maps from $S^{m-1} \times S^{n-1}$ to K. Since both $S m - 1$ and $S n - 1$ are compact sets, it follows that their product also is compact. Furthermore, since σ is continuous, it follows that the range of σ is compact. Consequently, σ assumes a largest value for at least one pair of vectors $u \in S^{m-1}$ and $v \in S^{n-1}$ . This largest value is denoted $σ 1$ and the corresponding vectors are denoted $u 1$ and $v 1$ .

Given $u 1$ and $v 1$ , let $\tilde{S}^{m-2}$ and $\tilde{S}^{n-2}$ denote the subsets of $S m - 1$ and $S n - 1$ which are orthogonal to $u 1$ and $v 1$ , respectively. Consider now the restriction of σ to the set $\tilde{S}^{m-2} \times \tilde{S}^{n-2}$ . Again it turns out that the domain of this σ is compact, hence it assumes a largest value for some vectors $u 2$ and $v 2$ .

Given $u 2$ and $v 2$ , let $\tilde{S}^{m-3}$ and $\tilde{S}^{n-3}$ denote the subsets of $\tilde{S}^{m-2}$ and $\tilde{S}^{n-2}$ which are orthogonal to $u 2$ and $v 2$ , respectively. By restricting σ to the corresponding domain, a largest value σ is found for some vectors $u 3$ and $v 3$ .

Clearly, this procedure of defining smaller and smaller subsets of normalized vectors in $K m$ and $K n$ which are orthogonal to all vectors $u k$ and $v k$ previously found can be repeated until we reach the sets $\tilde{S}^{m-p}$ and $\tilde{S}^{n-p}$ , where $p = min(m, n)$ , from which the value $σ p$ is found as the largest value of σ.

In the end, we have generated the set of scalars $\sigma_{1}, \sigma_{2}, \ldots, \sigma_{p}$ together with two sets of vectors $u_{1}, u_{2}, \ldots, u_{p}$ and $v_{1}, v_{2}, \ldots, v_{p}$ . It turns out that the scalars $σ k$ are the singular values of M and that $u k$ and $v k$ are the corresponding left and right singular vectors. To see this, let us reexamine $u 1, v 1,σ 1$ . The two vectors were found by minimizing the function $σ$ with $u \in S^{m-1}$ and $v \in S^{n-1}$ . This can be done by finding $u$ and $v$ for which the gradient of $σ$ with respect to $u$ and $v$ equals a linear combination of the Lagrange multipliers corresponding to the conditions $\|u\|^{2} = \|v\|^{2} = 1$ . This gives,

M v 1 = 2λ 1 u 1 + 0

M T u 1 = 0 + 2λ 2 v 1

Multiplying the first equation from left by $u_{1}^{T}$ and the second equation from left by $v_{1}^{T}$ and taking $\|u\|^{2} = \|v\|^{2} = 1$ into account gives

$u_{1}^{T} M v_{1} = \sigma_{1} = 2 \lambda_{1}$

$v_{1}^{T} M^{T} u_{1} = \sigma_{1} = 2 \lambda_{2}$

or $σ 1 = 2λ 1 = 2λ 2$ . Inserted into the above equations this gives

M v 1 = σ 1

M T u 1 = σ 1

This proves that $u 1, v 2$ are in fact left and right singular vectors of $M$ and that $σ 1$ is their corresponding singular value. Similar results can be derived for the remaining vectors and values derived above.

This definition of singular values and singular vectors may not be of much practical use, but it interesting from the point of view that it proves the existence of these entities.

Retrieved from "http://en.wikipedia.org../../../k/y/n/User%7EKYN_SingularValues_8ed9.html"

User:KYN/SingularValues

From Wikipedia, the free encyclopedia

Views

Navigation

interaction

Search