Regularization To ols
A Matlab Package for
Analysis and Solution of Discrete Ill-Posed Problems
Version 3.0 for Matlab 5.2
Per Christian Hansen
Department of Mathematical Modelling
Building 305, Technical University of Denmark
DK-2800 Lyngby, Denmark
http://www.imm.dtu.dk/~pch
June 1992
Last revision March 1998
The software described in this report is published in
Numerical Algorithms
6
(1994), pp. 1{35, and is available via
Netlib (
netlib@research.att.com
) in the le
numeralgo/na4
.
Contents
Changes Since Version 2.0 3
1 Introduction 5
2 Discrete Ill-Posed Problems and their Regularization 7
2.1 Discrete Ill-Posed Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Regularization Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 SVD and Generalized SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.1 The Singular Value Decomposition . . . . . . . . . . . . . . . . . . . 10
2.3.2 The Generalized Singular Value Decomposition . . . . . . . . . . . . 11
2.4 The Discrete Picard Condition and Filter Factors . . . . . . . . . . . . . . . 13
2.5 The L-Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Transformation to Standard Form . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 Transformation for Direct Metho ds . . . . . . . . . . . . . . . . . . . 18
2.6.2 Transformation for Iterative Metho ds . . . . . . . . . . . . . . . . . 19
2.6.3 Norm Relations etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Direct Regularization Metho ds . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.1 Tikhonov Regularization . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7.2 Least Squares with a Quadratic Constraint . . . . . . . . . . . . . . 21
2.7.3 TSVD, MTSVD, and TGSVD . . . . . . . . . . . . . . . . . . . . . 22
2.7.4 Damped SVD/GSVD . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7.5 Maximum Entropy Regularization . . . . . . . . . . . . . . . . . . . 23
2.7.6 Truncated Total Least Squares . . . . . . . . . . . . . . . . . . . . . 24
2.8 Iterative Regularization Methods . . . . . . . . . . . . . . . . . . . . . . . . 25
2.8.1 Conjugate Gradients and LSQR . . . . . . . . . . . . . . . . . . . . 25
2.8.2 Bidiagonalization with Regularization . . . . . . . . . . . . . . . . . 27
2.8.3 The
-Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.8.4 Extension to General-Form Problems . . . . . . . . . . . . . . . . . . 29
2.9 Methods for Cho osing the Regularization Parameter . . . . . . . . . . . . . 29
3 Regularization Tools Tutorial 33
3.1 The Discrete Picard Condition . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Filter Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 The L-Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Regularization Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Standard Form Versus General Form . . . . . . . . . . . . . . . . . . . . . . 38
3.6 No Square Integrable Solution . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2 CONTENTS
4 Regularization Tools Reference 43
Routines by Sub ject Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
The Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Alphabetical List of Routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Bibliography 105
Changes Since Version 2.0
The following is a list of the ma jor changes since Version 2.0 of the package.
Replaced
gsvd
by
cgsvd
which has a
dierent
sequence of output arguments.
Removed the obsolete function
csdecomp
(which replaced the function
csd
)
Deleted the function
mgs
.
Changed the storage format of bidiagonal matrices to sparse, instead of a dense
matrix with two columns.
Removed the obsolete function
bsvd
.
Added the function
regutm
that generates random test matrices for regularization
methods.
Added the
blur
test problem.
Functions
tsvd
and
tgsvd
now allow
k
= 0, and functions
tgsvd
and
tikhonov
now
allow a square
L
.
Added output arguments
rho
and
eta
to functions
dsvd
,
mtsvd
,
tgsvd
,
tikhonov
, and
tsvd
.
Added a priori guess
x
0
as input to
tikhonov
.
Corrected
get
l
such that the sign of
L*x
is correct.
Added MGS reorthogonalization of the normal equation residual vectors in the two
functions
cgls
and
pcgls
.
Added the metho d
'ttls'
to the function
l
fac
.
More precise computation of the regularization parameter in
gcv
,
lcurve
, and
qua-
siopt
.
Changed
heb
new
and
newton
to work with
instead of
2
.
Added legend to
lagrange
and
picard
.
评论0