1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
<html lang="en">
<head>
<title>Singular Value Decomposition - GNU Scientific Library -- Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Scientific Library -- Reference Manual">
<meta name="generator" content="makeinfo 4.8">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Linear-Algebra.html" title="Linear Algebra">
<link rel="prev" href="QR-Decomposition-with-Column-Pivoting.html" title="QR Decomposition with Column Pivoting">
<link rel="next" href="Cholesky-Decomposition.html" title="Cholesky Decomposition">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with the
Invariant Sections being ``GNU General Public License'' and ``Free Software
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled ``GNU Free Documentation
License''.
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
GNU Manual, like GNU software.''-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="Singular-Value-Decomposition"></a>
Next: <a rel="next" accesskey="n" href="Cholesky-Decomposition.html">Cholesky Decomposition</a>,
Previous: <a rel="previous" accesskey="p" href="QR-Decomposition-with-Column-Pivoting.html">QR Decomposition with Column Pivoting</a>,
Up: <a rel="up" accesskey="u" href="Linear-Algebra.html">Linear Algebra</a>
<hr>
</div>
<h3 class="section">13.4 Singular Value Decomposition</h3>
<p><a name="index-SVD-1273"></a><a name="index-singular-value-decomposition-1274"></a>
A general rectangular M-by-N matrix A has a
singular value decomposition (<span class="sc">svd</span>) into the product of an
M-by-N orthogonal matrix U, an N-by-N
diagonal matrix of singular values S and the transpose of an
N-by-N orthogonal square matrix V,
<pre class="example"> A = U S V^T
</pre>
<p class="noindent">The singular values
<!-- {$\sigma_i = S_{ii}$} -->
\sigma_i = S_{ii} are all non-negative and are
generally chosen to form a non-increasing sequence
<!-- {$\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_N \ge 0$} -->
\sigma_1 >= \sigma_2 >= ... >= \sigma_N >= 0.
<p>The singular value decomposition of a matrix has many practical uses.
The condition number of the matrix is given by the ratio of the largest
singular value to the smallest singular value. The presence of a zero
singular value indicates that the matrix is singular. The number of
non-zero singular values indicates the rank of the matrix. In practice
singular value decomposition of a rank-deficient matrix will not produce
exact zeroes for singular values, due to finite numerical
precision. Small singular values should be edited by choosing a suitable
tolerance.
<p>For a rank-deficient matrix, the null space of A is given by
the columns of V corresponding to the zero singular values.
Similarly, the range of A is given by columns of U
corresponding to the non-zero singular values.
<div class="defun">
— Function: int <b>gsl_linalg_SV_decomp</b> (<var>gsl_matrix * A, gsl_matrix * V, gsl_vector * S, gsl_vector * work</var>)<var><a name="index-gsl_005flinalg_005fSV_005fdecomp-1275"></a></var><br>
<blockquote><p>This function factorizes the M-by-N matrix <var>A</var> into
the singular value decomposition A = U S V^T for <!-- {$M \ge N$} -->
M >= N. On output the matrix <var>A</var> is replaced by
U. The diagonal elements of the singular value matrix S
are stored in the vector <var>S</var>. The singular values are non-negative
and form a non-increasing sequence from S_1 to S_N. The
matrix <var>V</var> contains the elements of V in untransposed
form. To form the product U S V^T it is necessary to take the
transpose of <var>V</var>. A workspace of length <var>N</var> is required in
<var>work</var>.
<p>This routine uses the Golub-Reinsch SVD algorithm.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_linalg_SV_decomp_mod</b> (<var>gsl_matrix * A, gsl_matrix * X, gsl_matrix * V, gsl_vector * S, gsl_vector * work</var>)<var><a name="index-gsl_005flinalg_005fSV_005fdecomp_005fmod-1276"></a></var><br>
<blockquote><p>This function computes the SVD using the modified Golub-Reinsch
algorithm, which is faster for <!-- {$M \gg N$} -->
M>>N. It requires the vector <var>work</var> of length <var>N</var> and the
N-by-N matrix <var>X</var> as additional working space.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_linalg_SV_decomp_jacobi</b> (<var>gsl_matrix * A, gsl_matrix * V, gsl_vector * S</var>)<var><a name="index-gsl_005flinalg_005fSV_005fdecomp_005fjacobi-1277"></a></var><br>
<blockquote><p>This function computes the SVD of the M-by-N matrix <var>A</var>
using one-sided Jacobi orthogonalization for <!-- {$M \ge N$} -->
M >= N. The Jacobi method can compute singular values to higher
relative accuracy than Golub-Reinsch algorithms (see references for
details).
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_linalg_SV_solve</b> (<var>gsl_matrix * U, gsl_matrix * V, gsl_vector * S, const gsl_vector * b, gsl_vector * x</var>)<var><a name="index-gsl_005flinalg_005fSV_005fsolve-1278"></a></var><br>
<blockquote><p>This function solves the system A x = b using the singular value
decomposition (<var>U</var>, <var>S</var>, <var>V</var>) of A given by
<code>gsl_linalg_SV_decomp</code>.
<p>Only non-zero singular values are used in computing the solution. The
parts of the solution corresponding to singular values of zero are
ignored. Other singular values can be edited out by setting them to
zero before calling this function.
<p>In the over-determined case where <var>A</var> has more rows than columns the
system is solved in the least squares sense, returning the solution
<var>x</var> which minimizes ||A x - b||_2.
</p></blockquote></div>
<hr>The GNU Scientific Library - a free numerical library licensed under the GNU GPL<br>Back to the <a href="/software/gsl/">GNU Scientific Library Homepage</a></body></html>
|
