Adaptive cross approximation for ill-posed problems. (English) Zbl 1416.65565
Summary: Integral equations of the first kind with a smooth kernel and perturbed right-hand side, which represents available contaminated data, arise in many applications. Discretization gives rise to linear systems of equations with a matrix whose singular values cluster at the origin. The solution of these systems of equations requires regularization, which has the effect that components in the computed solution connected to singular vectors associated with small singular values are damped or ignored. In order to compute a useful approximate solution typically approximations of only a fairly small number of the largest singular values and associated singular vectors of the matrix are required. The present paper explores the possibility of determining these approximate singular values and vectors by adaptive cross approximation. This approach is particularly useful when a fine discretization of the integral equation is required and the resulting linear system of equations is of large dimensions, because adaptive cross approximation makes it possible to compute only fairly few of the matrix entries.
MSC:
| 65R32 | Numerical methods for inverse problems for integral equations |
| 45Q05 | Inverse problems for integral equations |
| 65F50 | Computational methods for sparse matrices |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
ill-posed problem; inverse problem; sparse discretization; regularization; adaptive cross approximationReferences:
| [1] | Engl, H. W.; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Kluwer: Kluwer Dordrecht · Zbl 0859.65054 |
| [2] | Groetsch, C. W., The Theory of Tikhonov Regularization for Fredholm Equations of the First Kind (1984), Pitman: Pitman Boston · Zbl 0545.65034 |
| [3] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 1268.65037 |
| [4] | Calvetti, D.; Reichel, L., Tikhonov regularization of large linear problems, BIT, 43, 263-283 (2003) · Zbl 1038.65048 |
| [5] | Gazzola, S.; Novati, P.; Russo, M. R., On Krylov projection methods and Tikhonov regularization, Electron. Trans. Numer. Anal., 44, 83-123 (2015) · Zbl 1312.65065 |
| [6] | Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems (1998), SIAM: SIAM Philadelphia |
| [7] | Hochstenbach, M. E.; McNinch, N.; Reichel, L., Discrete ill-posed least-squares problems with a solution norm constraint, Linear Algebra Appl., 436, 3801-3818 (2012) · Zbl 1237.65039 |
| [8] | Noschese, S.; Reichel, L., A modified TSVD method for discrete ill-posed problems, Numer. Linear Algebra Appl., 21, 813-822 (2014) · Zbl 1340.65070 |
| [9] | Brezinski, C.; Rodriguez, G.; Seatzu, S., Error estimates for linear systems with applications to regularization, Numer. Algorithms, 49, 85-104 (2008) · Zbl 1162.65018 |
| [10] | 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) · Zbl 1287.65043 |
| [11] | Reichel, L.; Rodriguez, G., Old and new parameter choice rules for discrete ill-posed problems, Numer. Algorithms, 63, 65-87 (2013) · Zbl 1267.65045 |
| [12] | Baglama, J.; Reichel, L., An implicitly restarted block Lanczos bidiagonalization method using Leja shifts, BIT, 53, 285-310 (2013) · Zbl 1269.65038 |
| [13] | Hochstenbach, M. E., Harmonic and refined extraction methods for the singular value problem, with applications in least-squares problems, BIT, 44, 721-754 (2004) · Zbl 1079.65047 |
| [14] | 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) · Zbl 1063.65030 |
| [15] | Bebendorf, M.; Grzibovski, R., Accelerating Galerkin BEM for linear elasticity using adaptive cross approximation, Math. Methods Appl. Sci., 29, 1721-1747 (2006) · Zbl 1110.74054 |
| [16] | Bebendorf, M.; Rjasanow, S., Adaptive low-rank approximation of collocation matrices, Computing, 70, 1-24 (2003) · Zbl 1068.41052 |
| [17] | Frederix, K.; Van Barel, M., Solving a large dense linear system by adaptive cross approximation, J. Comput. Appl. Math., 234, 3181-3195 (2010) · Zbl 1196.65064 |
| [18] | Goreinov, S. A.; Tyrtyshnikov, E. E.; Zamarashkin, N. L., A theory of pseudo-skeleton approximation, Linear Algebra Appl., 261, 1-21 (1997) · Zbl 0877.65021 |
| [19] | Tyrtyshnikov, E. E., Incomplete cross approximation in the Mosaic-Skeleton method, Computing, 64, 367-380 (2000) · Zbl 0964.65048 |
| [20] | Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86, 565-589 (2000) · Zbl 0966.65094 |
| [21] | Goreinov, S. A.; Zamarashkin, N. L.; Tyrtyshnikov, E. E., Pseudo-skeleton approximations by matrices of maximal volume, Math. Notes, 62, 515-519 (1997) · Zbl 0916.65040 |
| [22] | Calvetti, D.; Petersen, J.; Reichel, L., A parallel implementation of the GMRES algorithm, (Reichel, L.; Ruttan, A.; Varga, R. S., Numerical Linear Algebra (1993), de Gruyter: de Gruyter Berlin), 31-46 · Zbl 0799.65036 |
| [23] | Erhel, J., A parallel GMRES version for general sparse matrices, Electron. Trans. Numer. Anal., 3, 160-176 (1995) · Zbl 0860.65021 |
| [24] | Yamamoto, Y.; Nakatsukasa, Y.; Yanagisawa, Y.; Fukaya, T., Roundoff error analysis of the CholeskyQR2 algorithm, Electron. Trans. Numer. Anal., 44, 306-326 (2015) · Zbl 1330.65049 |
| [25] | Daniel, J. W.; Gragg, W. B.; Kaufman, L.; Stewart, G. W., Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp., 30, 772-795 (1976) · Zbl 0345.65021 |
| [26] | Hansen, P. C., Regularization Tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194 (2007), Software is available in Netlib at: http://www.netlib.org · Zbl 1128.65029 |
| [27] | Baart, M. L., The use of auto-correlation for pseudo-rank determination in noisy ill-conditioned least-squares problems, IMA J. Numer. Anal., 2, 241-247 (1982) · Zbl 0484.65021 |
| [28] | Shaw, C. B., Improvements of the resolution of an instrument by numerical solution of an integral equation, J. Math. Anal. Appl., 37, 83-112 (1972) · Zbl 0237.65086 |
| [29] | Fox, L.; Goodwin, E. T., The numerical solution of non-singular linear integral equations, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 245, 902, 501-534 (1953) · Zbl 0050.12902 |
| [30] | Hansen, P. C., Deconvolution and regularization with Toeplitz matrices, Numer. Algorithms, 29, 323-378 (2002) · Zbl 1002.65145 |
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.
