# zbMATH — the first resource for mathematics

Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition. (English) Zbl 1434.65039
Summary: The truncated singular value decomposition may be used to find the solution of linear discrete ill-posed problems in conjunction with Tikhonov regularization and requires the estimation of a regularization parameter that balances between the sizes of the fit to data function and the regularization term. The unbiased predictive risk estimator is one suggested method for finding the regularization parameter when the noise in the measurements is normally distributed with known variance. In this paper we provide an algorithm using the unbiased predictive risk estimator that automatically finds both the regularization parameter and the number of terms to use from the singular value decomposition. Underlying the algorithm is a new result that proves that the regularization parameter converges with the number of terms from the singular value decomposition. For the analysis it is sufficient to assume that the discrete Picard condition is satisfied for exact data and that noise completely contaminates the measured data coefficients for a sufficiently large number of terms, dependent on both the noise level and the degree of ill-posedness of the system. A lower bound for the regularization parameter is provided leading to a computationally efficient algorithm. Supporting results are compared with those obtained using the method of generalized cross validation. Simulations for two-dimensional examples verify the theoretical analysis and the effectiveness of the algorithm for increasing noise levels, and demonstrate that the relative reconstruction errors obtained using the truncated singular value decomposition are less than those obtained using the singular value decomposition.
##### MSC:
 65F20 Numerical solutions to overdetermined systems, pseudoinverses 65F22 Ill-posedness and regularization problems in numerical linear algebra 65F15 Numerical computation of eigenvalues and eigenvectors of matrices
##### Software:
IR Tools; LSRN; PicardREG; Regularization tools
Full Text:
##### References:
  Abascal, J-FPJ; Arridge, SR; Bayford, RH; Holder, DS, Comparison of methods for optimal choice of the regularization parameter for linear electrical impedance tomography of brain function, Physiol. Meas., 29, 1319-1334 (2008)  Aster, R.C., Borchers, B., Thurber, C.H.: Parameter Estimation and Inverse Problems, 2nd edn. Elsevier, Amsterdam (2013) · Zbl 1273.35306  Bakushinskii, AB, Remarks on choosing a regularization parameter using the quasi-optimality and ratio criterion, USSR Comput. Math. Math. Phys., 24, 181182 (1984) · Zbl 0595.65064  Bauer, F.; Lukas, MA, Comparing parameter choice methods for regularization of ill-posed problems, Math. Comput. Simul., 81, 1795-1841 (2011) · Zbl 1220.65063  Björck, A.: Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics, Philadelphia (1996) · Zbl 0847.65023  Chung, J.; Nagy, JG; O’Leary, DP, A weighted GCV method for Lanczos hybrid regularization, Electron. Trans. Numer. Anal., 28, 149-167 (2008) · Zbl 1171.65029  Drineas, P.; Mahoney, MW, RandNLA: randomized numerical linear algebra, Commun. ACM, 59, 80-90 (2016)  Drineas, P.; Mahoney, MW; Muthukrishnan, S.; Sarlós, T., Faster least squares approximation, Numer. Math., 117, 219-249 (2011) · Zbl 1218.65037  Fenu, C.; Reichel, L.; Rodrigues, G.; Sadok, H., GCV for Tikhonov regularization by partial SVD, BIT Numer. Math., 57, 1019-1039 (2017) · Zbl 1386.65118  Gazzola, Silvia; Hansen, Per Christian; Nagy, James G., IR Tools: a MATLAB package of iterative regularization methods and large-scale test problems, Numerical Algorithms, 81, 773-811 (2018) · Zbl 1415.65003  Golub, GH; Heath, M.; Wahba, G., Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 215-223 (1979) · Zbl 0461.62059  Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins Press, Baltimore (1996) · Zbl 0865.65009  Gower, RM; Richtárik, P., Randomized iterative methods for linear systems, SIAM J. Matrix Anal. Appl., 36, 1660-1690 (2015) · Zbl 1342.65110  Hämäläinen, K., Harhanen, L., Kallonen, A., Kujanpää, A., Niemi, E., Siltanen, S.: Tomographic X-ray data of a walnut. arXiv:1502.04064 (2015)  Hämarik, U.; Palm, R.; Raus, T., On minimizationstrategies for choice of the regularization parameter in ill-posed problems, Numer. Funct. Anal. Optim., 30, 924-950 (2009) · Zbl 1189.65123  Hämarik, U.; Palm, R.; Raus, T., A family of rules for parameter choice in Tikhonov regularization of ill-posed problems with inexact noise level, J. Comput. Appl. Math., 236, 2146-2157 (2012) · Zbl 1247.65071  Hanke, M.; Hansen, PC, Regularization methods for large-scale problems, Surv. Math. Ind., 3, 253-315 (1993) · Zbl 0805.65058  Hansen, JK; Hogue, JD; Sander, GK; Renaut, RA; Popat, SC, Non-negatively constrained least squares and parameter choice by the residual periodogram for the inversion of electrochemical impedance spectroscopy data, J. Comput. Appl. Math., 278, 52-74 (2015) · Zbl 1304.65268  Hansen, PC, The discrete Picard condition for discrete ill-posed problems, BIT Numer. Math., 30, 658-672 (1990) · Zbl 0723.65147  Hansen, PC, Regularization tools—a Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 46, 189-194 (1994) · Zbl 1128.65029  Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. Society for Industrial and Applied Mathematics, Philadelphia (1998) · Zbl 0890.65037  Hansen, P.C.: Discrete Inverse Problems. Society for Industrial and Applied Mathematics, Philadelphia (2010) · Zbl 1197.65054  Hofmann, B.: Regularization for Applied Inverse and Ill-posed Problems: A Numerical Approach, Teubner-Texte zur Mathematik. Teubner, B.G., Berlin (1986)  Levin, E.; Meltzer, AY, Estimation of the regularization parameter in linear discrete ill-posed problems using the Picard parameter, SIAM J. Sci. Comput., 39, a2741-a2762 (2017) · Zbl 1378.65117  Lin, Y.; Wohlberg, B.; Guo, H., UPRE method for total variation parameter selection, Signal Process., 90, 2546-2551 (2010) · Zbl 1194.94109  Mahoney, MW, Randomized algorithms for matrices and data, Found. Trends® Mach. Learn., 3, 123-224 (2011) · Zbl 1232.68173  Mead, JL; Renaut, RA, A Newton root-finding algorithm for estimating the regularization parameter for solving ill-conditioned least squares problems, Inverse Probl., 25, 025002 (2009) · Zbl 1163.65019  Meng, X.; Saunders, MA; Mahoney, MW, LSRN: a parallel iterative solver for strongly over- or underdetermined systems, SIAM J. Sci. Comput., 36, c95-c118 (2014) · Zbl 1298.65053  Morozov, VA, On the solution of functional equations by the method of regularization, Sov. Math. Dokl., 7, 414-417 (1966) · Zbl 0187.12203  Renaut, RA; Horst, M.; Wang, Y.; Cochran, D.; Hansen, J., Efficient estimation of regularization parameters via downsampling and the singular value expansion, BIT Numer. Math., 57, 499-529 (2017) · Zbl 1367.65061  Renaut, RA; Vatankhah, S.; Ardestani, VE, Hybrid and iteratively reweighted regularization by unbiased predictive risk and weighted GCV for projected systems, SIAM J. Sci. Comput., 39, b221-b243 (2017) · Zbl 1360.65115  Rokhlin, V.; Tygert, M., A fast randomized algorithm for overdetermined linear least-squares regression, Proc. Natl. Acad. Sci., 105, 13212-13217 (2008) · Zbl 05851018  Stein, CM, Estimation of the mean of a multivariate normal distribution, Ann. Stat., 9, 1135-1151 (1981) · Zbl 0476.62035  Taroudaki, V.; O’Leary, DP, Near-optimal spectral filtering and error estimation for solving ill-posed problems, SIAM J. Sci. Comput., 37, a2947-a2968 (2015) · Zbl 1329.65084  Toma, A.; Sixou, B.; Peyrin, F., Iterative choice of the optimal regularization parameter in tv image restoration, Inverse Probl. Imaging, 9, 1171 (2015) · Zbl 1332.65074  Vatankhah, S.; Ardestani, VE; Renaut, RA, Automatic estimation of the regularization parameter in 2D focusing gravity inversion: application of the method to the Safo manganese mine in the northwest of Iran, J. Geophys. Eng., 11, 045001 (2014)  Vatankhah, S.; Ardestani, VE; Renaut, RA, Application of the $$\chi ^2$$ principle and unbiased predictive risk estimator for determining the regularization parameter in 3-D focusing gravity inversion, Geophys. J. Int., 200, 265-277 (2015)  Vatankhah, S.; Renaut, RA; Ardestani, VE, 3-D projected $$\ell _1$$ inversion of gravity data using truncated unbiased predictive risk estimator for regularization parameter estimation, Geophys. J. Int., 210, 1872-1887 (2017)  Vatankhah, S., Renaut, R.A., Ardestani, V.E.: A fast algorithm for regularized focused 3-D inversion of gravity data using the randomized SVD. Geophysics (2018)  Vatankhah, S.; Renaut, RA; Ardestani, VE, Total variation regularization of the 3-D gravity inverse problem using a randomized generalized singular value decomposition, Geophys. J. Int., 213, 695-705 (2018)  Vogel, C.: Computational Methods for Inverse Problems. Society for Industrial and Applied Mathematics, Philadelphia (2002) · Zbl 1008.65103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.