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
|
<!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>Further Details: Error Bounds for the Singular Value Decomposition</TITLE>
<META NAME="description" CONTENT="Further Details: Error Bounds for the 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="tex2html3997" HREF="node144.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3995" HREF="node142.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3991" HREF="node142.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3999" 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="tex2html4000" 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="tex2html3998" HREF="node144.html">Error Bounds for the </A>
<B>Up:</B> <A NAME="tex2html3996" HREF="node142.html">Error Bounds for the </A>
<B> Previous:</B> <A NAME="tex2html3992" HREF="node142.html">Error Bounds for the </A>
<BR> <P>
<H2><A NAME="SECTION04681000000000000000">Further Details: Error Bounds for the Singular Value Decomposition</A></H2>
<A NAME="secbackgroundsvd"> </A>
<P>
The usual error analysis of the SVD algorithm<A NAME="5944"> </A>
PxGESVD in ScaLAPACK (see
subsection <A HREF="node46.html#subsecdriveeig">3.2.3</A>)is as follows [<A HREF="node189.html#GVL2">71</A>]:
<P>
<BLOCKQUOTE> The SVD algorithm is backward stable.
<A NAME="5948"> </A>
<A NAME="5949"> </A>
This means that the computed SVD, <IMG WIDTH=49 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline18949" SRC="img680.gif">,
is nearly the exact SVD of <I>A</I>+<I>E</I> where <IMG WIDTH=169 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline18953" SRC="img681.gif">,
and <I>p</I>(<I>m</I>,<I>n</I>) is a modestly growing function of <I>m</I> and <I>n</I>. This means
<IMG WIDTH=224 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline18961" SRC="img682.gif">
is the true SVD, so that <IMG WIDTH=55 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline18963" SRC="img683.gif"> and <IMG WIDTH=55 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline18965" SRC="img684.gif"> are both orthogonal, where
<IMG WIDTH=123 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline18967" SRC="img685.gif">, and
<IMG WIDTH=124 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline18969" SRC="img686.gif">.
Each computed singular value <IMG WIDTH=13 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18971" SRC="img687.gif"> differs from true <IMG WIDTH=13 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12826" SRC="img77.gif">
by at most
<BR><IMG WIDTH=388 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath18941" SRC="img688.gif"><BR>
(we take <I>p</I>(<I>m</I>,<I>n</I>)=1 in the above code fragment).
Thus, large singular values (those near <IMG WIDTH=15 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline18977" SRC="img689.gif">) are computed to
high relative accuracy <A NAME="5965"> </A> and small ones may not be.
<A NAME="5966"> </A>
<A NAME="5967"> </A>
<P>
The angular difference between the computed left singular vector <IMG WIDTH=14 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline18979" SRC="img690.gif">
and a true <IMG WIDTH=14 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12840" SRC="img80.gif"> satisfies the approximate bound
<BR><IMG WIDTH=392 HEIGHT=41 ALIGN=BOTTOM ALT="displaymath18942" SRC="img691.gif"><BR>
where <IMG WIDTH=171 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline18985" SRC="img692.gif"> is the
<B>absolute gap</B><A NAME="5973"> </A><A NAME="5974"> </A>
between <IMG WIDTH=13 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12826" SRC="img77.gif"> and the nearest other singular value
(we take <I>p</I>(<I>m</I>,<I>n</I>)=1 in the above code fragment).
Thus, if <IMG WIDTH=13 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12826" SRC="img77.gif">
is close to other singular values, its corresponding singular vector <IMG WIDTH=14 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12840" SRC="img80.gif">
may be inaccurate. When <I>n</I> < <I>m</I>, then <IMG WIDTH=35 HEIGHT=16 ALIGN=MIDDLE ALT="tex2html_wrap_inline18997" SRC="img693.gif"> must be redefined
as <IMG WIDTH=202 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline18999" SRC="img694.gif">.
The gaps may be easily computed from the array of computed singular values
using function <A NAME="5976"> </A><A NAME="5977"> </A> SDISNA.
The gaps computed by SDISNA are ensured not to be so small as
to cause overflow when used as divisors.
<A NAME="5978"> </A>
<A NAME="5979"> </A>
The same bound applies to the computed right singular
vector <IMG WIDTH=12 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline19001" SRC="img695.gif"> and a true vector <IMG WIDTH=12 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline12842" SRC="img81.gif">.
<P>
Let <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> be the space spanned by a collection of computed left singular
vectors <IMG WIDTH=83 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline19007" SRC="img696.gif">, where <IMG WIDTH=12 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline18724" SRC="img658.gif"> is a subset
of the integers from 1 to <I>n</I>. Let <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline17602" SRC="img475.gif"> be the corresponding true space.
Then
<BR><IMG WIDTH=342 HEIGHT=41 ALIGN=BOTTOM ALT="displaymath18943" SRC="img697.gif"><BR>
where
<BR><IMG WIDTH=326 HEIGHT=35 ALIGN=BOTTOM ALT="displaymath18944" SRC="img698.gif"><BR>
is the absolute gap between the singular values in <IMG WIDTH=12 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline18724" SRC="img658.gif"> and the nearest
other singular value. Thus, a cluster<A NAME="5987"> </A>
of close singular values which is
far away from any other singular value may have a well determined
space <IMG WIDTH=11 HEIGHT=16 ALIGN=BOTTOM ALT="tex2html_wrap_inline17614" SRC="img477.gif"> even if its individual singular vectors are ill-conditioned.
The same bound applies to a set of right singular vectors
<IMG WIDTH=81 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline19021" SRC="img699.gif"><A NAME="tex2html1432" HREF="footnode.html#8103"><IMG ALIGN=BOTTOM ALT="gif" SRC="http://www.netlib.org/utk/icons/foot_motif.gif"></A>.
<P>
</BLOCKQUOTE>
<P>
There is a small possibility that PxGESVD will fail to achieve the
above error bounds on a heterogeneous network of processors
<A NAME="5994"> </A> for reasons
discussed in section <A HREF="node134.html#sec_Hetero">6.2</A>. On a homogeneous network,
PxGESVD is as robust as the corresponding LAPACK routine xGESVD.
A future release will attempt to detect heterogeneity and warn the user
to use an alternative algorithm.
<P>
In the special case of bidiagonal matrices, the singular values and
singular vectors may be computed much more accurately. A bidiagonal
matrix <I>B</I> has nonzero entries only on the main diagonal and the
diagonal immediately above it (or immediately below it). PxGESVD
computes the SVD of a general
<A NAME="5996"> </A><A NAME="5997"> </A><A NAME="5998"> </A><A NAME="5999"> </A>
matrix by first reducing it to bidiagonal form <I>B</I>, and then calling
xBDSQR
(subsection <A HREF="node64.html#subseccompsvd">3.3.6</A>)
to compute the SVD of <I>B</I>.
Reduction of a dense matrix to bidiagonal form <I>B</I> can introduce
additional errors, so the following bounds for the bidiagonal case
do not apply to the dense case.
For the error analysis of xBDSQR, see the LAPACK manual.
<P>
<HR><A NAME="tex2html3997" HREF="node144.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="http://www.netlib.org/utk/icons/next_motif.gif"></A> <A NAME="tex2html3995" HREF="node142.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="http://www.netlib.org/utk/icons/up_motif.gif"></A> <A NAME="tex2html3991" HREF="node142.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="http://www.netlib.org/utk/icons/previous_motif.gif"></A> <A NAME="tex2html3999" 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="tex2html4000" 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="tex2html3998" HREF="node144.html">Error Bounds for the </A>
<B>Up:</B> <A NAME="tex2html3996" HREF="node142.html">Error Bounds for the </A>
<B> Previous:</B> <A NAME="tex2html3992" HREF="node142.html">Error Bounds for the </A>
<P><ADDRESS>
<I>Susan Blackford <BR>
Tue May 13 09:21:01 EDT 1997</I>
</ADDRESS>
</BODY>
</HTML>
|
