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
|
<!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</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Large Dense Linear Systems">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Large Dense Linear Systems">
<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="Least_002dSquares-Fitting.html#Least_002dSquares-Fitting" rel="up" title="Least-Squares Fitting">
<link href="Large-Dense-Linear-Systems-Normal-Equations.html#Large-Dense-Linear-Systems-Normal-Equations" rel="next" title="Large Dense Linear Systems Normal Equations">
<link href="Robust-linear-regression.html#Robust-linear-regression" rel="previous" title="Robust linear regression">
<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"></a>
<div class="header">
<p>
Next: <a href="Troubleshooting.html#Troubleshooting" accesskey="n" rel="next">Troubleshooting</a>, Previous: <a href="Robust-linear-regression.html#Robust-linear-regression" accesskey="p" rel="previous">Robust linear regression</a>, Up: <a href="Least_002dSquares-Fitting.html#Least_002dSquares-Fitting" accesskey="u" rel="up">Least-Squares Fitting</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Large-dense-linear-systems"></a>
<h3 class="section">38.6 Large dense linear systems</h3>
<a name="index-large-dense-linear-least-squares"></a>
<a name="index-linear-least-squares_002c-large"></a>
<p>This module is concerned with solving large dense least squares systems
<em>X c = y</em> where the <em>n</em>-by-<em>p</em> matrix
<em>X</em> has <em>n >> p</em> (ie: many more rows than columns).
This type of matrix is called a “tall skinny” matrix, and for
some applications, it may not be possible to fit the
entire matrix in memory at once to use the standard SVD approach.
Therefore, the algorithms in this module are designed to allow
the user to construct smaller blocks of the matrix <em>X</em> and
accumulate those blocks into the larger system one at a time. The
algorithms in this module never need to store the entire matrix
<em>X</em> in memory. The large linear least squares routines
support data weights and Tikhonov regularization, and are
designed to minimize the residual
</p><div class="example">
<pre class="example">\chi^2 = || y - Xc ||_W^2 + \lambda^2 || L c ||^2
</pre></div>
<p>where <em>y</em> is the <em>n</em>-by-<em>1</em> observation vector,
<em>X</em> is the <em>n</em>-by-<em>p</em> design matrix, <em>c</em> is
the <em>p</em>-by-<em>1</em> solution vector,
<em>W =</em> diag<em>(w_1,...,w_n)</em> is the data weighting matrix,
<em>L</em> is an <em>m</em>-by-<em>p</em> regularization matrix,
<em>\lambda</em> is a regularization parameter,
and <em>||r||_W^2 = r^T W r</em>. In the discussion which follows,
we will assume that the system has been converted into Tikhonov
standard form,
</p><div class="example">
<pre class="example">\chi^2 = || y~ - X~ c~ ||^2 + \lambda^2 || c~ ||^2
</pre></div>
<p>and we will drop the tilde characters from the various parameters.
For a discussion of the transformation to standard form
see <a href="Regularized-regression.html#Regularized-regression">Regularized regression</a>.
</p>
<p>The basic idea is to partition the matrix <em>X</em> and observation
vector <em>y</em> as
</p><div class="example">
<pre class="example">[ X_1 ] c = [ y_1 ]
[ X_2 ] [ y_2 ]
[ X_3 ] [ y_3 ]
[ ... ] [ ... ]
[ X_k ] [ y_k ]
</pre></div>
<p>into <em>k</em> blocks, where each block (<em>X_i,y_i</em>) may have
any number of rows, but each <em>X_i</em> has <em>p</em> columns.
The sections below describe the methods available for solving
this partitioned system. The functions are declared in
the header file <samp>gsl_multilarge.h</samp>.
</p>
<table class="menu" border="0" cellspacing="0">
<tr><td align="left" valign="top">• <a href="Large-Dense-Linear-Systems-Normal-Equations.html#Large-Dense-Linear-Systems-Normal-Equations" accesskey="1">Large Dense Linear Systems Normal Equations</a>:</td><td> </td><td align="left" valign="top">
</td></tr>
<tr><td align="left" valign="top">• <a href="Large-Dense-Linear-Systems-TSQR.html#Large-Dense-Linear-Systems-TSQR" accesskey="2">Large Dense Linear Systems TSQR</a>:</td><td> </td><td align="left" valign="top">
</td></tr>
<tr><td align="left" valign="top">• <a href="Large-Dense-Linear-Systems-Solution-Steps.html#Large-Dense-Linear-Systems-Solution-Steps" accesskey="3">Large Dense Linear Systems Solution Steps</a>:</td><td> </td><td align="left" valign="top">
</td></tr>
<tr><td align="left" valign="top">• <a href="Large-Dense-Linear-Systems-Routines.html#Large-Dense-Linear-Systems-Routines" accesskey="4">Large Dense Linear Systems Routines</a>:</td><td> </td><td align="left" valign="top">
</td></tr>
</table>
<hr>
<div class="header">
<p>
Next: <a href="Troubleshooting.html#Troubleshooting" accesskey="n" rel="next">Troubleshooting</a>, Previous: <a href="Robust-linear-regression.html#Robust-linear-regression" accesskey="p" rel="previous">Robust linear regression</a>, Up: <a href="Least_002dSquares-Fitting.html#Least_002dSquares-Fitting" accesskey="u" rel="up">Least-Squares Fitting</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
