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
|
<!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: Large Dense Linear Systems TSQR</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Large Dense Linear Systems TSQR">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Large Dense Linear Systems TSQR">
<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="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" rel="up" title="Large Dense Linear Systems">
<link href="Large-Dense-Linear-Systems-Solution-Steps.html#Large-Dense-Linear-Systems-Solution-Steps" rel="next" title="Large Dense Linear Systems Solution Steps">
<link href="Large-Dense-Linear-Systems-Normal-Equations.html#Large-Dense-Linear-Systems-Normal-Equations" rel="previous" title="Large Dense Linear Systems Normal Equations">
<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="Large-Dense-Linear-Systems-TSQR"></a>
<div class="header">
<p>
Next: <a href="Large-Dense-Linear-Systems-Solution-Steps.html#Large-Dense-Linear-Systems-Solution-Steps" accesskey="n" rel="next">Large Dense Linear Systems Solution Steps</a>, Previous: <a href="Large-Dense-Linear-Systems-Normal-Equations.html#Large-Dense-Linear-Systems-Normal-Equations" accesskey="p" rel="previous">Large Dense Linear Systems Normal Equations</a>, Up: <a href="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" accesskey="u" rel="up">Large Dense Linear Systems</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Tall-Skinny-QR-_0028TSQR_0029-Approach"></a>
<h4 class="subsection">38.6.2 Tall Skinny QR (TSQR) Approach</h4>
<a name="index-large-linear-least-squares_002c-TSQR"></a>
<p>An algorithm which has better numerical stability for ill-conditioned
problems is known as the Tall Skinny QR (TSQR) method. This method
is based on computing the thin QR decomposition of the least squares
matrix <em>X = Q R</em>, where <em>Q</em> is an <em>n</em>-by-<em>p</em> matrix
with orthogonal columns, and <em>R</em> is a <em>p</em>-by-<em>p</em>
upper triangular matrix. Once these factors are calculated, the
residual becomes
</p><div class="example">
<pre class="example">\chi^2 = || Q^T y - R c ||^2 + \lambda^2 || c ||^2
</pre></div>
<p>which can be written as the matrix equation
</p><div class="example">
<pre class="example">[ R ; \lambda I ] c = [ Q^T b ; 0 ]
</pre></div>
<p>The matrix on the left hand side is now a much
smaller <em>2p</em>-by-<em>p</em> matrix which can
be solved with a standard SVD approach. The
<em>Q</em> matrix is just as large as the original
matrix <em>X</em>, however it does not need to be
explicitly constructed. The TSQR algorithm
computes only the <em>p</em>-by-<em>p</em> matrix
<em>R</em> and the <em>p</em>-by-1 vector <em>Q^T y</em>,
and updates these quantities as new blocks
are added to the system. Each time a new block of rows
(<em>X_i,y_i</em>) is added, the algorithm performs a QR decomposition
of the matrix
</p><div class="example">
<pre class="example">[ R_(i-1) ; X_i ]
</pre></div>
<p>where <em>R_{i-1}</em> is the upper triangular
<em>R</em> factor for the matrix
</p><div class="example">
<pre class="example">[ X_1 ; ... ; X_(i-1) ]
</pre></div>
<p>This QR decomposition is done efficiently taking into account
the sparse structure of <em>R_{i-1}</em>. See Demmel et al, 2008 for
more details on how this is accomplished. The number
of operations for this method is <em>O(2np^2 - {2 \over 3}p^3)</em>.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Large-Dense-Linear-Systems-Solution-Steps.html#Large-Dense-Linear-Systems-Solution-Steps" accesskey="n" rel="next">Large Dense Linear Systems Solution Steps</a>, Previous: <a href="Large-Dense-Linear-Systems-Normal-Equations.html#Large-Dense-Linear-Systems-Normal-Equations" accesskey="p" rel="previous">Large Dense Linear Systems Normal Equations</a>, Up: <a href="Large-Dense-Linear-Systems.html#Large-Dense-Linear-Systems" accesskey="u" rel="up">Large Dense Linear Systems</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
