Regularization Tools
A Matlab Package for
Analysis and Solution of Discrete Ill-Posed Problems
Version 4.1 for Matlab 7.3
Per Christian Hansen
Informatics and Mathematical Modelling
Building 321, Technical University of Denmark
DK-2800 Lyngby, Denmark
http://www.imm.dtu.dk/~pch
March 2008
The software described in this report was originally published in
Numerical Algorithms 6 (1994), pp. 1–35.
The current version is published in Numer. Algo. 46 (2007), pp. 189–194,
and it is available from www.netlib.org/numeralgo
and www.mathworks.com/matlabcentral/fileexchange
Contents
Changes from Earlier Versions 3
1 Introduction 5
2 Discrete Ill-Posed Problems and their Regularization 9
2.1 Discrete Ill-Posed Problems . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Regularization Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 SVD and Generalized SVD . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.1 The Singular Value Decomposition . . . . . . . . . . . . . . . . 13
2.3.2 The Generalized Singular Value Decomposition . . . . . . . . . 14
2.4 The Discrete Picard Condition and Filter Factors . . . . . . . . . . . . 16
2.5 The L-Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Transformation to Standard Form . . . . . . . . . . . . . . . . . . . . 21
2.6.1 Transformation for Direct Methods . . . . . . . . . . . . . . . . 21
2.6.2 Transformation for Iterative Methods . . . . . . . . . . . . . . 22
2.6.3 Norm Relations etc. . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7 Direct Regularization Methods . . . . . . . . . . . . . . . . . . . . . . 25
2.7.1 Tikhonov Regularization . . . . . . . . . . . . . . . . . . . . . . 25
2.7.2 Least Squares with a Quadratic Constraint . . . . . . . . . . . 25
2.7.3 TSVD, MTSVD, and TGSVD . . . . . . . . . . . . . . . . . . 26
2.7.4 Damped SVD/GSVD . . . . . . . . . . . . . . . . . . . . . . . 27
2.7.5 Maximum Entropy Regularization . . . . . . . . . . . . . . . . 28
2.7.6 Truncated Total Least Squares . . . . . . . . . . . . . . . . . . 29
2.8 Iterative Regularization Methods . . . . . . . . . . . . . . . . . . . . . 29
2.8.1 Conjugate Gradients and LSQR . . . . . . . . . . . . . . . . . 29
2.8.2 Bidiagonalization with Regularization . . . . . . . . . . . . . . 32
2.8.3 The ν-Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.8.4 Extension to General-Form Problems . . . . . . . . . . . . . . . 33
2.9 Methods for Choosing the Regularization Parameter . . . . . . . . . . 34
2.10 New Functions in Version 4.1 . . . . . . . . . . . . . . . . . . . . . . . 36
2 CONTENTS
3 Regularization Tools Tutorial 39
3.1 The Discrete Picard Condition . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Filter Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 The L-Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Regularization Parameters . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Standard Form Versus General Form . . . . . . . . . . . . . . . . . . . 43
3.6 No Square Integrable Solution . . . . . . . . . . . . . . . . . . . . . . . 46
4 Regularization Tools Reference 47
Routines by Subject Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
The Test Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Alphabetical List of Routines . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Bibliography 121
Changes from Earlier Versions
The following is a list of the major changes since Version 2.0 of the package.
• Replaced gsvd by cgsvd which has a different 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 regulariza-
tion 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 method ’ttls’ to the function fil fac.
• More precise computation of the regularization parameter in gcv, lcurve, and
quasiopt.
• Changed heb new and newton to work with λ instead of λ
2
.
• Added legend to lagrange and picard.
评论5