zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
The truncated SVD as a method for regularization. (English) Zbl 0633.65041

The paper deals with the unconstrained linear least squares problem (1) minAx-B, A m×n , mn, for an ill-conditioned matrix A. There are two well-known attempts to deal with such ill-posed problems: the method of regularization by Tikhonov and Phillips and the truncated singular value decomposition (TSVD).

Let A=UΣV T be the singular value decomposition (SVD) of the matrix A; here U m×m , V n×n are orthogonal, Σ=diag{σ 1 ,σ 2 ,···,σ n } and σ i are singular values of A. The TSVI solution of (1) is defined as x k =A k + B, where A k + is the pseudoinverse of A k =UΣ k V T ,Σ k =diag{σ 1 ,···,σ k ,0,···,0}·

To analyze the behaviour of TSVD solutions a perturbation theory is developed. It states that the perturbed TSVD solution can be guaranteed to be closed to the true solution if the relative gap ω k =A-A k ·A k + =σ k+1 /σ k between the singular values σ k and σ k+1 is small. This divides all ill-conditioned matrices into two classes: those with well-determined numerical rank and with ill-determined numerical rank. It is proved that for the matrices of the first class the TSVD solution is close to the regularized solution provided the regularization parameter is chosen properly. Finally, the case of matrices with ill-determined numerical rank is discussed.

Reviewer: V.S.Zajačkovski

MSC:
65F20Overdetermined systems, pseudoinverses (numerical linear algebra)
65F15Eigenvalues, eigenvectors (numerical linear algebra)
15A18Eigenvalues, singular values, and eigenvectors
62J05Linear regression
65C99Probabilistic methods, simulation and stochastic differential equations (numerical analysis)
References:
[1]H. C. Andrews and B. R. Hunt,Digital Image Restoration, Prentice-Hall (1977).
[2]A. Ben-Israel and T. N. E. Greville,Generalized Inverses: Theory and Applications, Wiley-Interscience (1974).
[3]T. F. Chan and D. Foulser,Effective condition numbers for linear systems, Tech Memo 86-05, Saxpy Computer Corporation, Sunnyvale (1986).
[4]T. F. Chan and P. C. Hansen,Computing truncated SVD least squares solutions by rank revealing QR-factorizations, CAM Report 86-01, Dept. of Mathematics, U.C.L.A. (1986).
[5]U. Eckhardt and K. Mika,Numerical treatment of incorrectly posed problems – a case study; in J. Albrecht and L. Collatz (Eds.),Numerical Treatment of Integral Equations, Workshop on numerical treatment of integral equations, Oberwolfach. November 18–24, 1979, Birkhäuser Verlag (1980), pp. 92–101.
[6]L. Eldén,Algorithms for regularization of ill-conditioned least squares problems, BIT 17 (1977), 134–145. · Zbl 0362.65105 · doi:10.1007/BF01932285
[7]L. Eldén,The numerical solution of a non-characteristic Cauchy problem for a parabolic equation; in P. Deuflhard and E. Hairer (Eds.),Numerical Treatment of Inverse Problems in Differential and Integral Equations, Birkhäuser Verlag (1983), pp. 246–268.
[8]G. E. Forsythe, M. A. Malcolm and C. B. Moler,Computer Methods for Mathematical Computations, Prentice-Hall (1977).
[9]G. H. Golub, V. Klema and G. W. Stewart,Rank degeneracy and least squares problems, Technical Report TR-456, Computer Science Department, University of Maryland (1976).
[10]G. H. Golub and C. F. Van Loan,Matrix Computations, North Oxford Academic (1983).
[11]P. C. Hansen and S. Christiansen,An SVD analysis of linear algebraic equations derived from first kind integral equations, J. Comp. Appl. Math. 12&13 (1985), 341–357. · Zbl 0577.65116 · doi:10.1016/0377-0427(85)90029-9
[12]R. J. Hanson,A numerical method for solving Fredholm integral equations of the first kind using singular values, SIAM J. Numer. Anal. 8 (1971), 616–622. · Zbl 0221.65188 · doi:10.1137/0708058
[13]C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice Hall (1974).
[14]A. K. Louis and F. Natterer,Mathematical problems of computerized tomography, Proc. IEEE 71 (1983), 379–389. · doi:10.1109/PROC.1983.12596
[15]B. C. Moore and A. J. Laub,Computation of supremal (A,B)-invariant and controllability subspaces, IEEE Trans. Automat. Contr. AC-23 (1978), 783–792. · Zbl 0394.93009 · doi:10.1109/TAC.1978.1101882
[16]F. Natterer,Numerical inversion of the Radon transform, Numer. Math. 30 (1978), 81–91. · Zbl 0425.65073 · doi:10.1007/BF01403908
[17]D. L. Phillips,A technique for the numerical solution of certain integral equations of the first kind, J. ACM 9 (1962), 84–97. · Zbl 0108.29902 · doi:10.1145/321105.321114
[18]A. N. Tikhonov,Solution of incorrectly formulated problems and the regularization method, Dokl. Akad. Nauk. SSSR 151 (1963), 501–504 = Soviet Math. Dokl. 4 (1963), 1035–1038.
[19]D. W. Tufts and R. Kumaresan,Singular value decomposition and improved frequency estimation using linear prediction, IEEE Trans. Acoust., Speech, Signal Processing ASSP-30 (1982), 671–675. · doi:10.1109/TASSP.1982.1163927
[20]P. M. Van Dooren,The generalized eigenstructure problem in linear system theory, IEEE Trans. Automat. Contr. AC-26 (1981), 111–129.
[21]J. M. Varah,On the numerical solution of ill-conditioned linear systems with applications to ill-posed problems, SIAM J. Numer. Anal. 10 (1973), 257–267. · Zbl 0261.65034 · doi:10.1137/0710025
[22]J. M. Varah,A practical examination of some numerical methods for linear discrete ill-posed problems, SIAM Review 21 (1979), 100–111. · Zbl 0406.65015 · doi:10.1137/1021007
[23]P.-Å. Wedin,Perturbation bounds in connection with the singular value decomposition, BIT 12 (1972), 99–111. · Zbl 0239.15015 · doi:10.1007/BF01932678
[24]P.-Å. Wedin,Perturbation theory for pseudo-inverses, BIT 13 (1973), 217–232. · Zbl 0263.65047 · doi:10.1007/BF01933494
[25]P.-Å. Wedin,On the almost rank deficient case of the least squares problem, BIT 13 (1973), 344–354. · Zbl 0277.65019 · doi:10.1007/BF01951945