On the reduction of Tikhonov minimization problems and the construction of regularization matrices. (English) Zbl 1254.65049
Summary: Tikhonov regularization replaces a linear discrete ill-posed problem by a penalized least-squares problem, whose solution is less sensitive to errors in the data and round-off errors introduced during the solution process. The penalty term is defined by a regularization matrix and a regularization parameter. The latter generally has to be determined during the solution process. This requires a repeated solution of the penalized least-squares problem. It is therefore attractive to transform the least-squares problem to a simpler form before solving it. The present paper describes a transformation of the penalized least-squares problem to a simpler form that is faster to compute than available transformations in the situation when the regularization matrix has linearly dependent columns and no exploitable structure. Properties of this kind of regularization matrices are discussed and their performance is illustrated.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
Keywords:
ill-posed problem; Tikhonov regularization; regularization matrix; singular value decomposition; numerical examples; penalized least-squares problemReferences:
| [1] | Bai, Z.: The CSD, GSVD, Their Applications and Computation. IMA preprint 958, Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN (1992) |
| [2] | Bai, Z., Demmel, J.W.: Computing the generalized singular value decomposition. SIAM J. Sci. Comput. 14, 1464–1486 (1993) · Zbl 0789.65024 · doi:10.1137/0914085 |
| [3] | Brezinski, C., Redivo-Zaglia, M., Rodriguez, G., Seatzu, S.: Extrapolation techniques for ill-conditioned linear systems. Numer. Math. 81, 1–29 (1998) · Zbl 0921.65032 · doi:10.1007/s002110050382 |
| [4] | Brezinski, C., Redivo-Zaglia, M., Rodriguez, G., Seatzu, S.: Multi-parameter regularization techniques for ill-conditioned linear systems. Numer. Math. 94, 203–228 (2003) · Zbl 1024.65036 · doi:10.1007/s00211-002-0435-8 |
| [5] | Brezinski, C., Rodriguez, G., Seatzu, S.: Error estimates for linear systems with application to regularization. Numer. Algorithms 49, 85–104 (2008) · Zbl 1162.65018 · doi:10.1007/s11075-008-9163-1 |
| [6] | Brezinski, C., Rodriguez, G., Seatzu, S.: Error estimates for the regularization of least squares problems. Numer. Algorithms 51, 61–76 (2009) · Zbl 1166.65331 · doi:10.1007/s11075-008-9243-2 |
| [7] | Calvetti, D., Reichel, L., Shuibi, A.: Invertible smoothing preconditioners for linear discrete ill-posed problems. Appl. Numer. Math. 54, 135–149 (2005) · Zbl 1072.65057 · doi:10.1016/j.apnum.2004.09.027 |
| [8] | Campbell, S.L., Meyer, C.D.: Generalized Inverses of Linear Transformations. Dover, Mineola (1991) · Zbl 0732.15003 |
| [9] | Eldén, L.: Algorithms for the regularization of ill-conditioned least squares problems. BIT 17, 134–145 (1977) · Zbl 0362.65105 · doi:10.1007/BF01932285 |
| [10] | Eldén, L.: A weighted pseudoinverse, generalized singular values, and constrained least squares problems. BIT 22, 487–501 (1982) · Zbl 0509.65019 · doi:10.1007/BF01934412 |
| [11] | Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996) · Zbl 0859.65054 |
| [12] | Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009 |
| [13] | Hansen, P.C.: Regularization, GSVD and truncated GSVD. BIT 29, 491–504 (1989) · Zbl 0682.65021 · doi:10.1007/BF02219234 |
| [14] | Hansen, P.C.: Regularization tools version 4.0 for Matlab 7.3. Numer. Algorithms 46, 189–194 (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9 |
| [15] | Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998) |
| [16] | Morigi, S., Reichel, L., Sgallari, F.: Orthogonal projection regularization operators. Numer. Algorithms 44, 99–114 (2007) · Zbl 1124.65043 · doi:10.1007/s11075-007-9080-8 |
| [17] | Phillips, D.L.: A technique for the numerical solution of certain integral equations of the first kind. J. ACM 9, 84–97 (1962) · Zbl 0108.29902 · doi:10.1145/321105.321114 |
| [18] | Reichel, L., Ye, Q.: Simple square smoothing regularization operators. Electron. Trans. Numer. Anal. 33, 63–83 (2009) · Zbl 1171.65033 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
