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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 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.3 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 the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Singular Value Decomposition</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Singular Value Decomposition">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Singular Value Decomposition">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Linear-Algebra.html#Linear-Algebra" rel="up" title="Linear Algebra">
<link href="Cholesky-Decomposition.html#Cholesky-Decomposition" rel="next" title="Cholesky Decomposition">
<link href="Complete-Orthogonal-Decomposition.html#Complete-Orthogonal-Decomposition" rel="previous" title="Complete Orthogonal Decomposition">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Singular-Value-Decomposition"></a>
<div class="header">
<p>
Next: <a href="Cholesky-Decomposition.html#Cholesky-Decomposition" accesskey="n" rel="next">Cholesky Decomposition</a>, Previous: <a href="Complete-Orthogonal-Decomposition.html#Complete-Orthogonal-Decomposition" accesskey="p" rel="previous">Complete Orthogonal Decomposition</a>, Up: <a href="Linear-Algebra.html#Linear-Algebra" accesskey="u" rel="up">Linear Algebra</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Singular-Value-Decomposition-1"></a>
<h3 class="section">14.5 Singular Value Decomposition</h3>
<a name="index-SVD"></a>
<a name="index-singular-value-decomposition"></a>
<p>A general rectangular <em>M</em>-by-<em>N</em> matrix <em>A</em> has a
singular value decomposition (<small>SVD</small>) into the product of an
<em>M</em>-by-<em>N</em> orthogonal matrix <em>U</em>, an <em>N</em>-by-<em>N</em>
diagonal matrix of singular values <em>S</em> and the transpose of an
<em>N</em>-by-<em>N</em> orthogonal square matrix <em>V</em>,
</p>
<div class="example">
<pre class="example">A = U S V^T
</pre></div>
<p>The singular values
<em>\sigma_i = S_{ii}</em> are all non-negative and are
generally chosen to form a non-increasing sequence
<em>\sigma_1 >= \sigma_2 >= ... >= \sigma_N >= 0</em>.
</p>
<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>
<p>For a rank-deficient matrix, the null space of <em>A</em> is given by
the columns of <em>V</em> corresponding to the zero singular values.
Similarly, the range of <em>A</em> is given by columns of <em>U</em>
corresponding to the non-zero singular values.
</p>
<p>Note that the routines here compute the “thin” version of the SVD
with <em>U</em> as <em>M</em>-by-<em>N</em> orthogonal matrix. This allows
in-place computation and is the most commonly-used form in practice.
Mathematically, the “full” SVD is defined with <em>U</em> as an
<em>M</em>-by-<em>M</em> orthogonal matrix and <em>S</em> as an
<em>M</em>-by-<em>N</em> diagonal matrix (with additional rows of zeros).
</p>
<dl>
<dt><a name="index-gsl_005flinalg_005fSV_005fdecomp"></a>Function: <em>int</em> <strong>gsl_linalg_SV_decomp</strong> <em>(gsl_matrix * <var>A</var>, gsl_matrix * <var>V</var>, gsl_vector * <var>S</var>, gsl_vector * <var>work</var>)</em></dt>
<dd><p>This function factorizes the <em>M</em>-by-<em>N</em> matrix <var>A</var> into
the singular value decomposition <em>A = U S V^T</em> for <em>M >= N</em>. On output the matrix <var>A</var> is replaced by
<em>U</em>. The diagonal elements of the singular value matrix <em>S</em>
are stored in the vector <var>S</var>. The singular values are non-negative
and form a non-increasing sequence from <em>S_1</em> to <em>S_N</em>. The
matrix <var>V</var> contains the elements of <em>V</em> in untransposed
form. To form the product <em>U S V^T</em> 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>
<p>This routine uses the Golub-Reinsch SVD algorithm.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005flinalg_005fSV_005fdecomp_005fmod"></a>Function: <em>int</em> <strong>gsl_linalg_SV_decomp_mod</strong> <em>(gsl_matrix * <var>A</var>, gsl_matrix * <var>X</var>, gsl_matrix * <var>V</var>, gsl_vector * <var>S</var>, gsl_vector * <var>work</var>)</em></dt>
<dd><p>This function computes the SVD using the modified Golub-Reinsch
algorithm, which is faster for <em>M>>N</em>. It requires the vector <var>work</var> of length <var>N</var> and the
<em>N</em>-by-<em>N</em> matrix <var>X</var> as additional working space.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005flinalg_005fSV_005fdecomp_005fjacobi"></a>Function: <em>int</em> <strong>gsl_linalg_SV_decomp_jacobi</strong> <em>(gsl_matrix * <var>A</var>, gsl_matrix * <var>V</var>, gsl_vector * <var>S</var>)</em></dt>
<dd><a name="index-Jacobi-orthogonalization"></a>
<p>This function computes the SVD of the <em>M</em>-by-<em>N</em> matrix <var>A</var>
using one-sided Jacobi orthogonalization for <em>M >= N</em>. The Jacobi method can compute singular values to higher
relative accuracy than Golub-Reinsch algorithms (see references for
details).
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005flinalg_005fSV_005fsolve"></a>Function: <em>int</em> <strong>gsl_linalg_SV_solve</strong> <em>(const gsl_matrix * <var>U</var>, const gsl_matrix * <var>V</var>, const gsl_vector * <var>S</var>, const gsl_vector * <var>b</var>, gsl_vector * <var>x</var>)</em></dt>
<dd><p>This function solves the system <em>A x = b</em> using the singular value
decomposition (<var>U</var>, <var>S</var>, <var>V</var>) of <em>A</em> which must
have been computed previously with <code>gsl_linalg_SV_decomp</code>.
</p>
<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>
<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 <em>||A x - b||_2</em>.
</p></dd></dl>
<dl>
<dt><a name="index-gsl_005flinalg_005fSV_005fleverage"></a>Function: <em>int</em> <strong>gsl_linalg_SV_leverage</strong> <em>(const gsl_matrix * <var>U</var>, gsl_vector * <var>h</var>)</em></dt>
<dd><p>This function computes the statistical leverage values <em>h_i</em> of a matrix <em>A</em>
using its singular value decomposition (<var>U</var>, <var>S</var>, <var>V</var>) previously computed
with <code>gsl_linalg_SV_decomp</code>. <em>h_i</em> are the diagonal values of the matrix
<em>A (A^T A)^{-1} A^T</em> and depend only on the matrix <var>U</var> which is the input to
this function.
</p></dd></dl>
<hr>
<div class="header">
<p>
Next: <a href="Cholesky-Decomposition.html#Cholesky-Decomposition" accesskey="n" rel="next">Cholesky Decomposition</a>, Previous: <a href="Complete-Orthogonal-Decomposition.html#Complete-Orthogonal-Decomposition" accesskey="p" rel="previous">Complete Orthogonal Decomposition</a>, Up: <a href="Linear-Algebra.html#Linear-Algebra" accesskey="u" rel="up">Linear Algebra</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
