Skip to main content
Top
Published in: BIT Numerical Mathematics 4/2017

18-05-2017

GCV for Tikhonov regularization by partial SVD

Authors: Caterina Fenu, Lothar Reichel, Giuseppe Rodriguez , Hassane Sadok

Published in: BIT Numerical Mathematics | Issue 4/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Tikhonov regularization is commonly used for the solution of linear discrete ill-posed problems with error-contaminated data. A regularization parameter that determines the quality of the computed solution has to be chosen. One of the most popular approaches to choosing this parameter is to minimize the Generalized Cross Validation (GCV) function. The minimum can be determined quite inexpensively when the matrix A that defines the linear discrete ill-posed problem is small enough to rapidly compute its singular value decomposition (SVD). We are interested in the solution of linear discrete ill-posed problems with a matrix A that is too large to make the computation of its complete SVD feasible, and show how upper and lower bounds for the numerator and denominator of the GCV function can be determined fairly inexpensively for large matrices A by computing only a few of the largest singular values and associated singular vectors of A. These bounds are used to determine a suitable value of the regularization parameter. Computed examples illustrate the performance of the proposed method.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM 58, 8:1–8:34 (2011)CrossRefMATHMathSciNet Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM 58, 8:1–8:34 (2011)CrossRefMATHMathSciNet
2.
go back to reference Baglama, J., Fenu, C., Reichel, L., Rodriguez, G.: Analysis of directed networks via partial singular value decomposition and Gauss quadrature. Linear Algebra Appl. 456, 93–121 (2014)CrossRefMATHMathSciNet Baglama, J., Fenu, C., Reichel, L., Rodriguez, G.: Analysis of directed networks via partial singular value decomposition and Gauss quadrature. Linear Algebra Appl. 456, 93–121 (2014)CrossRefMATHMathSciNet
4.
go back to reference Baglama, J., Reichel, L.: An implicitly restarted block Lanczos bidiagonalization method using Leja shifts. BIT 53, 285–310 (2013)MATHMathSciNet Baglama, J., Reichel, L.: An implicitly restarted block Lanczos bidiagonalization method using Leja shifts. BIT 53, 285–310 (2013)MATHMathSciNet
6.
go back to reference Björck, Å.: A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations. BIT 18, 659–670 (1988)CrossRefMATHMathSciNet Björck, Å.: A bidiagonalization algorithm for solving large and sparse ill-posed systems of linear equations. BIT 18, 659–670 (1988)CrossRefMATHMathSciNet
7.
8.
go back to reference Brezinski, C., Fika, P., Mitrouli, M.: Estimations of the trace of powers of self-adjoint operators by extrapolation of the moments. Electron. Trans. Numer. Anal. 39, 144–159 (2012)MATHMathSciNet Brezinski, C., Fika, P., Mitrouli, M.: Estimations of the trace of powers of self-adjoint operators by extrapolation of the moments. Electron. Trans. Numer. Anal. 39, 144–159 (2012)MATHMathSciNet
9.
go back to reference Brezinski, C., Fika, P., Mitrouli, M.: Moments of a linear operator on a Hilbert space, with applications to the trace of the inverse of matrices and the solution of equations. Numer. Linear Algebra Appl. 19, 937–953 (2012)CrossRefMATHMathSciNet Brezinski, C., Fika, P., Mitrouli, M.: Moments of a linear operator on a Hilbert space, with applications to the trace of the inverse of matrices and the solution of equations. Numer. Linear Algebra Appl. 19, 937–953 (2012)CrossRefMATHMathSciNet
10.
go back to reference Craven, P., Wahba, G.: Smoothing noisy data with spline functions. Numer. Math. 31, 377–403 (1979)CrossRefMATH Craven, P., Wahba, G.: Smoothing noisy data with spline functions. Numer. Math. 31, 377–403 (1979)CrossRefMATH
11.
go back to reference Eldén, L.: A weighted pseudoinverse, generalized singular values, and constrained least squares problems. BIT 22, 487–501 (1982)CrossRefMATHMathSciNet Eldén, L.: A weighted pseudoinverse, generalized singular values, and constrained least squares problems. BIT 22, 487–501 (1982)CrossRefMATHMathSciNet
12.
go back to reference Eldén, L.: A note on the computation of the generalized cross-validation function for ill-conditioned least squares problems. BIT 24, 467–472 (1984)CrossRefMATHMathSciNet Eldén, L.: A note on the computation of the generalized cross-validation function for ill-conditioned least squares problems. BIT 24, 467–472 (1984)CrossRefMATHMathSciNet
13.
go back to reference Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996)CrossRefMATH Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996)CrossRefMATH
14.
go back to reference Fenu, C., Reichel, L., Rodriguez, G.: GCV for Tikhonov regularization via global Golub–Kahan decomposition. Numer. Linear Algebra Appl. 23, 467–484 (2016)CrossRefMATHMathSciNet Fenu, C., Reichel, L., Rodriguez, G.: GCV for Tikhonov regularization via global Golub–Kahan decomposition. Numer. Linear Algebra Appl. 23, 467–484 (2016)CrossRefMATHMathSciNet
15.
go back to reference Gazzola, S., Novati, P., Russo, M.R.: On Krylov projection methods and Tikhonov regularization. Electron. Trans. Numer. Anal. 44, 83–123 (2015)MATHMathSciNet Gazzola, S., Novati, P., Russo, M.R.: On Krylov projection methods and Tikhonov regularization. Electron. Trans. Numer. Anal. 44, 83–123 (2015)MATHMathSciNet
16.
go back to reference Golub, G.H., Heath, M., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215–223 (1979)CrossRefMATHMathSciNet Golub, G.H., Heath, M., Wahba, G.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215–223 (1979)CrossRefMATHMathSciNet
17.
go back to reference Golub, G.H., Luk, F.T., Overton, M.L.: A block Lanczos method for computing the singular values and corresponding singular Vectors of a matrix. ACM Trans. Math. Software 7, 149–169 (1981)CrossRefMATHMathSciNet Golub, G.H., Luk, F.T., Overton, M.L.: A block Lanczos method for computing the singular values and corresponding singular Vectors of a matrix. ACM Trans. Math. Software 7, 149–169 (1981)CrossRefMATHMathSciNet
18.
go back to reference Golub, G.H., Meurant, G.: Moments and Quadrature with Applications. Princeton University Press, Princeton (2010)MATH Golub, G.H., Meurant, G.: Moments and Quadrature with Applications. Princeton University Press, Princeton (2010)MATH
19.
go back to reference Golub, G.H., von Matt, U.: Generalized cross-validation for large-scale problems. J. Comput. Graph. Stat. 6, 1–34 (1997)MATHMathSciNet Golub, G.H., von Matt, U.: Generalized cross-validation for large-scale problems. J. Comput. Graph. Stat. 6, 1–34 (1997)MATHMathSciNet
20.
go back to reference Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998)CrossRef Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998)CrossRef
23.
go back to reference Hochstenbach, M.E.: Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems. BIT 44, 721–754 (2004)CrossRefMATHMathSciNet Hochstenbach, M.E.: Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems. BIT 44, 721–754 (2004)CrossRefMATHMathSciNet
24.
go back to reference Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Statist. Simula. 18, 1059–1076 (1989)CrossRefMATHMathSciNet Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Statist. Simula. 18, 1059–1076 (1989)CrossRefMATHMathSciNet
25.
go back to reference Jia, Z., Niu, D.: An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition. SIAM J. Matrix Anal. Appl. 25, 246–265 (2003)CrossRefMATHMathSciNet Jia, Z., Niu, D.: An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition. SIAM J. Matrix Anal. Appl. 25, 246–265 (2003)CrossRefMATHMathSciNet
26.
go back to reference Kindermann, S.: Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems. Electron. Trans. Numer. Anal. 38, 233–257 (2011)MATHMathSciNet Kindermann, S.: Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems. Electron. Trans. Numer. Anal. 38, 233–257 (2011)MATHMathSciNet
27.
29.
go back to reference Onunwor, E., Reichel, L.: On the computation of a truncated SVD of a large linear discrete ill-posed problem. Numer. Algorithms, in press Onunwor, E., Reichel, L.: On the computation of a truncated SVD of a large linear discrete ill-posed problem. Numer. Algorithms, in press
30.
32.
go back to reference Tang, J., Saad, Y.: A probing method for computing the diagonal of the matrix inverse. Numer. Linear Algebra Appl. 19, 485–501 (2012)CrossRefMATHMathSciNet Tang, J., Saad, Y.: A probing method for computing the diagonal of the matrix inverse. Numer. Linear Algebra Appl. 19, 485–501 (2012)CrossRefMATHMathSciNet
33.
go back to reference van der Mee, C.V.M., Seatzu, S.: A method for generating infinite positive self-adjoint test matrices and Riesz bases. SIAM J. Matrix Anal. Appl. 26, 1132–1149 (2005)CrossRefMATHMathSciNet van der Mee, C.V.M., Seatzu, S.: A method for generating infinite positive self-adjoint test matrices and Riesz bases. SIAM J. Matrix Anal. Appl. 26, 1132–1149 (2005)CrossRefMATHMathSciNet
Metadata
Title
GCV for Tikhonov regularization by partial SVD
Authors
Caterina Fenu
Lothar Reichel
Giuseppe Rodriguez
Hassane Sadok
Publication date
18-05-2017
Publisher
Springer Netherlands
Published in
BIT Numerical Mathematics / Issue 4/2017
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI
https://doi.org/10.1007/s10543-017-0662-0

Other articles of this Issue 4/2017

BIT Numerical Mathematics 4/2017 Go to the issue

Premium Partner