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
|
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<!--Converted with LaTeX2HTML 96.1-h (September 30, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
<HTML>
<HEAD>
<TITLE>Singular Value Decomposition</TITLE>
<META NAME="description" CONTENT="Singular Value Decomposition">
<META NAME="keywords" CONTENT="slug">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<LINK REL=STYLESHEET HREF="slug.css">
</HEAD>
<BODY LANG="EN" >
<A NAME="tex2html2952" HREF="node65.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2950" HREF="node50.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2944" HREF="node63.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2954" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html2955" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html2953" HREF="node65.html">Generalized Symmetric Definite Eigenproblems</A>
<B>Up:</B> <A NAME="tex2html2951" HREF="node50.html">Computational Routines</A>
<B> Previous:</B> <A NAME="tex2html2945" HREF="node63.html">EigenvaluesEigenvectors, and Schur </A>
<BR> <P>
<H2><A NAME="SECTION04336000000000000000">Singular Value Decomposition</A></H2>
<A NAME="subseccompsvd"> </A>
<P>
Let <I>A</I> be a general real <I>m</I>-by-<I>n</I> matrix. The <B>singular value
decomposition (SVD)</B> of <I>A</I> is the factorization<A NAME="2043"> </A> <IMG WIDTH=86 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14119" SRC="img195.gif">, where
<I>U</I> and <I>V</I> are orthogonal and
<IMG WIDTH=144 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline14125" SRC="img196.gif">, <IMG WIDTH=106 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline14127" SRC="img197.gif">,
with <IMG WIDTH=132 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14129" SRC="img198.gif">. If <I>A</I> is complex,
its SVD is <IMG WIDTH=88 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14133" SRC="img199.gif">, where <I>U</I> and <I>V</I> are unitary
and <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12820" SRC="img76.gif"> is as before with real
diagonal elements.
The <IMG WIDTH=13 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12826" SRC="img77.gif"> are called the <B>singular values</B><A NAME="2045"> </A>,
the first <I>r</I> columns of <I>V</I>
the <B>right singular vectors</B><A NAME="2047"> </A>, and
the first <I>r</I> columns of <I>U</I>
the <B>left singular vectors</B><A NAME="2049"> </A>.
<P>
The routines described in this section, and listed in table <A HREF="node64.html#tabcompsvd">3.10</A>,
are used to compute this decomposition.
The computation proceeds in the following stages:
<P>
<OL>
<LI> The matrix <I>A</I> is reduced to bidiagonal<A NAME="2052"> </A>
form: <IMG WIDTH=94 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14153" SRC="img200.gif"> if
<I>A</I> is real (<IMG WIDTH=96 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14157" SRC="img201.gif"> if <I>A</I> is complex), where <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14161" SRC="img202.gif"> and <IMG WIDTH=15 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14163" SRC="img203.gif">
are orthogonal (unitary if <I>A</I> is complex), and <I>B</I> is real and
upper-bidiagonal when <IMG WIDTH=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline13306" SRC="img125.gif"> and lower bidiagonal when <I>m</I> < <I>n</I>, so
that <I>B</I> is nonzero only on the main diagonal and either on the first
superdiagonal (if <IMG WIDTH=48 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline13306" SRC="img125.gif">) or the first subdiagonal (if <I>m</I><<I>n</I>).
<LI> The SVD of the bidiagonal matrix <I>B</I> is computed: <IMG WIDTH=93 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14181" SRC="img204.gif">,
where <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14183" SRC="img205.gif"> and <IMG WIDTH=15 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14185" SRC="img206.gif"> are orthogonal and <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12820" SRC="img76.gif"> is diagonal as described
above. The singular vectors of <I>A</I> are then <IMG WIDTH=73 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14191" SRC="img207.gif"> and
<IMG WIDTH=70 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14193" SRC="img208.gif">.
</OL>
<P>
The reduction to bidiagonal form is performed by the subroutine PxGEBRD
and the SVD of <I>B</I> is computed using the LAPACK routine xBDSQR.
<A NAME="2054"> </A>
<A NAME="2055"> </A><A NAME="2056"> </A><A NAME="2057"> </A><A NAME="2058"> </A>
<P>
The routine PxGEBRD represents
<IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14161" SRC="img202.gif"> and <IMG WIDTH=15 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14163" SRC="img203.gif"> in factored form as products of elementary reflectors,<A NAME="2059"> </A><A NAME="2060"> </A>
as described in section <A HREF="node66.html#secorthog">3.4</A>.
If <I>A</I> is real,
the matrices <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14161" SRC="img202.gif"> and <IMG WIDTH=15 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14163" SRC="img203.gif"> may be multiplied by other matrices without
forming <IMG WIDTH=17 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14161" SRC="img202.gif"> and <IMG WIDTH=15 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline14163" SRC="img203.gif"> using routine PxORMBR<A NAME="2062"> </A><A NAME="2063"> </A>.
If <I>A</I> is complex, one instead uses PxUNMBR<A NAME="2064"> </A><A NAME="2065"> </A>.
<P>
If <IMG WIDTH=52 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline14213" SRC="img209.gif">, it may be more efficient to first perform a <I>QR</I> factorization
of <I>A</I>, using the routine
PxGEQRF<A NAME="2066"> </A><A NAME="2067"> </A><A NAME="2068"> </A><A NAME="2069"> </A>,
and then to compute the SVD of the <I>n</I>-by-<I>n</I> matrix <I>R</I>, since
if <I>A</I> = <I>QR</I> and <IMG WIDTH=87 HEIGHT=15 ALIGN=BOTTOM ALT="tex2html_wrap_inline14227" SRC="img210.gif">, then the SVD of <I>A</I> is given by
<IMG WIDTH=114 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline14231" SRC="img211.gif">.
Similarly, if <IMG WIDTH=52 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline14233" SRC="img212.gif">, it may be more efficient to first perform an
<I>LQ</I> factorization of <I>A</I>, using xGELQF. These preliminary <I>QR</I> and <I>LQ</I>
<A NAME="2070"> </A><A NAME="2071"> </A><A NAME="2072"> </A><A NAME="2073"> </A>
factorizations are performed by the driver PxGESVD.
<A NAME="2074"> </A><A NAME="2075"> </A><A NAME="2076"> </A><A NAME="2077"> </A>
<P>
The SVD may be used to find a minimum norm solution<A NAME="2078"> </A> to a (possibly)
rank-deficient linear least squares
<A NAME="2079"> </A>
problem (<A HREF="node45.html#llsq">3.1</A>). The effective rank, <I>k</I>, of <I>A</I> can be determined as the
number of singular values which exceed a suitable threshold.
Let <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline14247" SRC="img213.gif"> be the leading <I>k</I>-by-<I>k</I> submatrix of <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline12820" SRC="img76.gif">, and
<IMG WIDTH=12 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline14255" SRC="img214.gif"> be the matrix consisting of the first <I>k</I> columns of <I>V</I>.
Then the solution is given by
<BR><IMG WIDTH=298 HEIGHT=21 ALIGN=BOTTOM ALT="displaymath14109" SRC="img215.gif"><BR>
where <IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline13502" SRC="img143.gif"> consists of the first <I>k</I> elements of <IMG WIDTH=140 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14265" SRC="img216.gif">. <IMG WIDTH=30 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline14267" SRC="img217.gif"> can be computed by using PxORMBR.
<A NAME="2091"> </A><A NAME="2092"> </A>
<P>
<P><A NAME="2094"> </A><A NAME="tabcompsvd"> </A><IMG WIDTH=737 HEIGHT=111 ALIGN=BOTTOM ALT="table2093" SRC="img218.gif"><BR>
<STRONG>Table 3.10:</STRONG> Computational routines for the singular value decomposition<BR>
<P>
<P>
<HR><A NAME="tex2html2952" HREF="node65.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html2950" HREF="node50.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html2944" HREF="node63.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html2954" HREF="node1.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="http://www.netlib.org/utk/icons/contents_motif.gif"></A> <A NAME="tex2html2955" HREF="node190.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="http://www.netlib.org/utk/icons/index_motif.gif"></A> <BR>
<B> Next:</B> <A NAME="tex2html2953" HREF="node65.html">Generalized Symmetric Definite Eigenproblems</A>
<B>Up:</B> <A NAME="tex2html2951" HREF="node50.html">Computational Routines</A>
<B> Previous:</B> <A NAME="tex2html2945" HREF="node63.html">EigenvaluesEigenvectors, and Schur </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
