Singular value decomposition

Singular value decomposition using the example of a two-dimensional, real shear : This transformation distorts the blue unit circle at the top left to the ellipse at the top right in the image. can be broken down into two rotations and an expansion / compression along the coordinate axes. The singular values and are the lengths of the major and minor semiaxes of the ellipse. The exact values ​​for this example can be found in the picture description . ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle U}$ ${\displaystyle V^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \sigma _{1}}$ ${\displaystyle \sigma _{2}}$

A singular value decomposition (abbr .: SWZ or SVD for Singular Value Decomposition ) of a matrix describes its representation as the product of three special matrices. From this one can read the singular values ​​of the matrix. Similar to the eigenvalues , these characterize properties of the matrix. Singular value decompositions exist for every matrix - also for non-square matrices.

definition

The singular value decomposition of a complex matrix with rank is a product of the shape ${\displaystyle m\times n}$ ${\displaystyle M}$ ${\displaystyle r}$

${\displaystyle M=U\Sigma V^{*},}$

in which

• ${\displaystyle U}$is a unitary matrix, ${\displaystyle m\times m}$
• ${\displaystyle V^{*}}$the adjoint of a unitary matrix and ${\displaystyle n\times n}$ ${\displaystyle V}$
• ${\displaystyle \Sigma }$a real matrix of shape ${\displaystyle m\times n}$

${\displaystyle \Sigma =\left({\begin{array}{ccc|ccc}\sigma _{1}&&&&\vdots &\\&\ddots &&\cdots &0&\cdots \\&&\sigma _{r}&&\vdots &\\\hline &\vdots &&&\vdots &\\\cdots &0&\cdots &\cdots &0&\cdots \\&\vdots &&&\vdots &\\\end{array}}\right)}$

with is. ${\displaystyle \sigma _{1}\geq \dotsb \geq \sigma _{r}>0}$

The positive diagonal entries of are called singular values of . The singular values ​​and thus also the matrix are uniquely determined by. The column vectors of hot left singular vectors , the column vectors of hot right singular vectors (to the index ) of the matrix . Neither nor are clearly determined. ${\displaystyle \sigma _{i},i=1,\dotsc ,r}$ ${\displaystyle \Sigma }$ ${\displaystyle M}$ ${\displaystyle \Sigma }$ ${\displaystyle M}$
${\displaystyle u_{i},i=1,\dotsc ,m}$ ${\displaystyle U}$ ${\displaystyle v_{i},i=1,\dotsc ,n}$ ${\displaystyle V}$ ${\displaystyle i}$ ${\displaystyle M}$ ${\displaystyle U}$ ${\displaystyle V}$

properties

Each matrix has at least one singular value decomposition. In the case of a real matrix, the matrices and the decomposition can be chosen real. ${\displaystyle U}$ ${\displaystyle V}$

Because of

${\displaystyle M^{*}\cdot M=\left(V\Sigma ^{T}U^{*}\right)\cdot \left(U\Sigma V^{*}\right)=V\Sigma ^{T}\Sigma V^{*}}$

is similar to . Thus the singular values ​​of the matrix are equal to the square roots of the positive eigenvalues of . Therefore, that is spectral norm of equal to the largest singular value , . Furthermore which is Frobenius norm , Euclidean norm of the vector of the singular values . ${\displaystyle M^{*}M}$ ${\displaystyle \Sigma ^{T}\Sigma }$ ${\displaystyle M}$ ${\displaystyle M^{*}M}$ ${\displaystyle M}$ ${\displaystyle \sigma _{1}}$ ${\displaystyle \|M\|_{2}=\sigma _{1}}$ ${\displaystyle \|M\|_{F}=\|[\sigma _{i}]_{i=1}^{r}\|_{2}}$

Insertion and recalculation shows that the pseudo inverse (in the case of invertibility, the inverse) becomes out ${\displaystyle M}$

${\displaystyle M^{+}=V\Sigma ^{+}U^{*}}$

With

${\displaystyle (\Sigma ^{+})_{ij}={\begin{cases}{\frac {1}{\sigma _{i}}},&{\text{falls}}\ i=j\leq r,\\0&{\text{sonst}}\end{cases}}}$

results. Thus the singular values ​​of the inverse are too precise , and the condition number of related to the spectral norm results in . ${\displaystyle M}$ ${\displaystyle {\tfrac {1}{\sigma _{i}}}}$ ${\displaystyle M}$ ${\displaystyle \kappa _{2}(M)={\tfrac {\sigma _{1}}{\sigma _{n}}}}$

Since unitary transformations do not change the amount of the determinant, the following applies

${\displaystyle |\det(M)|=\prod _{i=1}^{r}\sigma _{i},}$

if a square matrix is ​​with . ${\displaystyle M}$ ${\displaystyle \det(M)\neq 0}$

It applies

${\displaystyle Mv_{i}=\sigma _{i}u_{i}}$

and

${\displaystyle M^{T}u_{i}=\sigma _{i}v_{i}\quad {\text{ für }}i=1,\dotsc ,\min(m,n),}$

d. That is, the pairs of singular value and singular vectors characterize the change in length and direction in the image space through the linear transformation or , respectively, on the vectors of an orthonormal system in the original image space. ${\displaystyle M}$ ${\displaystyle M^{T}}$

Economic variant of the singular value decomposition

Be

${\displaystyle M=U\Sigma V^{*}}$

the singular value decomposition of a matrix . ${\displaystyle m\times n}$ ${\displaystyle M}$

In this case there is an "economic variant" of the singular value decomposition of the shape ${\displaystyle m<n}$

${\displaystyle M=U\Sigma _{m}V_{m}^{*}}$.

Here is the matrix whose columns consist of the first columns of and consists of the first columns of . ${\displaystyle V_{m}}$ ${\displaystyle n\times m}$ ${\displaystyle m}$ ${\displaystyle V}$ ${\displaystyle \Sigma _{m}}$ ${\displaystyle m}$ ${\displaystyle \Sigma }$

Similarly, the economic variant is given as follows: ${\displaystyle m>n}$

${\displaystyle M=U_{n}\Sigma _{n}V^{*},}$

where the first columns of contains and the first rows of . ${\displaystyle U_{n}}$ ${\displaystyle n}$ ${\displaystyle U}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle n}$ ${\displaystyle \Sigma }$

Many programming libraries for linear algebra can only calculate the latter variant; for matrices with the singular value decomposition (in the first variant) can then be achieved by transposition or adjunction : ${\displaystyle m\times n}$ ${\displaystyle m<n}$

${\displaystyle M^{*}=V_{m}\Sigma _{m}^{\top }U^{*}}$.

Numerical determination of the singular value decomposition

Since the singular values with the eigenvalues of the matrix are connected, an obvious would algorithm for numerical determination of a singular value decomposition of the matrix, the numerical solution of the symmetric eigenvalue problem to . However, such an algorithm is numerically unstable , since the condition number is squared by the product , and it is also very complex due to the matrix products required . ${\displaystyle M^{*}M}$ ${\displaystyle M^{*}M}$

In the 1960s, Gene Golub in particular developed stable iterative algorithms for calculating a singular value decomposition that directly transform the matrix , making the decomposition practically usable. These are based on the symmetrical or self-adjoint block matrix ${\displaystyle M}$

${\displaystyle {\begin{bmatrix}0&M\\M^{\ast }&0\end{bmatrix}}}$

whose eigenvalues ​​are the singular values ​​and their negatives as well as zero. The original method was published by him in 1965 with William Kahan and an iterative one in 1970 with Christian Reinsch . The processes first transform the matrix into a more favorable shape: With the help of orthogonal transformations - for example through household transformations -  the matrix is ​​brought into a biagonal shape . After this intermediate step, a modified form of the QR algorithm allows efficient numerical determination of the singular values. The effort is approximately arithmetic operations. ${\displaystyle {\tfrac {4}{3}}n^{3}+{\mathcal {O}}\left(n^{2}\right)}$

application

Singular value decomposition is used in particular in numerical mathematics . In this way, for example, almost singular linear equation systems can be adequately solved within the framework of computational accuracy.

Singular value decomposition is the most important numerical method in geophysical inversion, in which the structure of the latter can be determined from geophysical signals observed on the earth's surface. Special applications here are seismic tomography and the reversal problem of potential theory .

In statistics, the singular value decomposition is the computational core of the principal component analysis , there also called Karhunen-Loève transformation .

Some modern image compression methods are based on an algorithm that converts the image (= matrix of color values) into a singular value decomposition, then only takes into account the elements of the matrix that are strongly different from zero and then saves the vectors required to recover the matrix and the remaining diagonal elements. This compression is particularly effective with certain rectangular patterns and of course the more effective the larger (and the more square-like) the image is. This is one possible application of model reduction. The omission of small singular values ​​is a lossy model reduction method. ${\displaystyle \Sigma }$

In particle physics , singular value decomposition is used to diagonalize mass matrices of Dirac particles . The singular values ​​indicate the masses of the particles in their mass eigenstates. From the transformation and constructed to Mischungsmatrizen as the CKM matrix expressing that the mass eigenstates of particles from a mixture of flavor may consist eigenstates. ${\displaystyle U}$ ${\displaystyle V}$

Singular value decomposition is the core of Latent Semantic Analysis , an information retrieval procedure that helps to uncover latent concepts in large text collections. B. differently labeled information on the same topic can be found.

In control theory , singular value decomposition is one of the foundations for the development of robust controllers .

literature

• Günter Gramlich: Application of linear algebra with MATLAB ^® . Carl Hanser Verlag, 2004. ISBN 3-446-22655-9 .
• Peter Deuflhard and Andreas Hohmann: Numerical Mathematics I. Walter deGruyter, Berlin 2008. ISBN 3-11-020354-5 .

Footnotes

1. ↑ The largest and smallest singular value of a square matrix was also referred to in the middle of the 20th century as the "upper limit" or "lower limit" of the matrix, see limit (upper and lower) of a square matrix. In: J. Naas, HL Schmid: Mathematical dictionary. BG Teubner, Stuttgart 1979, ISBN 3-519-02400-4 .

Web links

• Gene H. Golub, William Kahan: Calculating the singular values ​​and pseudo-inverse of a matrix. SIAM J. Numer. Anal., Series B, Vol. 2 (1965), No. 2, pp. 205-224. Online also at galton.uchicago.edu and at www3.math.tu-berlin.de.
• Gilbert W. Stewart : On the early history of the singular value decomposition. SIAM Review, 35, No. 4, pp. 551-566 (1993).
• taramath online tool for calculating the singular value decomposition of real matrices.