Optimal preconditioning for image deblurring with anti-reflective boundary conditions. (English) Zbl 1338.65081
Summary: Inspired by the theoretical results on optimal preconditioning stated by Ng, Chan, and Tang in the framework of Reflective boundary conditions (BCs), in this paper we present analogous results for Anti-Reflective BCs. Here a key technical difficulty is represented by the non-orthogonal character of the Anti-Reflective transform and indeed the proof proposed by Ng, Chan, and Tang does not work. Nevertheless, in both cases, the optimal preconditioner is the blurring matrix associated to the symmetrized Point Spread Function (PSF). The geometrical idea on which our proof is based is very simple and general, so it may be useful in the future to prove theoretical results for new proposed BCs. Numerical tests show that the optimal preconditioning strategy is effective when using both preconditioned conjugate gradient methods and recently introduced nonstationary preconditioned iterations.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
References:
| [1] | Almeida, M. S.C.; Figueiredo, M. A.T., Deconvolving images with unknown boundaries using the alternating direction method of multipliers, IEEE Trans. Image Process., 22, 3074-3086 (2013) · Zbl 1373.94019 |
| [2] | Aricò, A.; Donatelli, M.; Nagy, J.; Serra Capizzano, S., The anti-reflective transform and regularization by filtering, (Numerical Linear Algebra in Signals, Systems, and Control. Numerical Linear Algebra in Signals, Systems, and Control, Lect. Notes Electr. Eng., vol. 80 (2011), Springer-Verlag), 1-21, (special volume) · Zbl 1258.94014 |
| [3] | Aricò, A.; Donatelli, M.; Serra Capizzano, S., Spectral analysis of the anti-reflective algebra, Linear Algebra Appl., 428, 2-3, 657-675 (2008) · Zbl 1140.15005 |
| [4] | Aricò, A.; Donatelli, M.; Serra Capizzano, S., The antireflective algebra: structural and computational analysis with application to image deblurring and denoising, Calcolo, 45, 3, 149-175 (2008) · Zbl 1171.94303 |
| [5] | Bai, Z. J.; Donatelli, M.; Serra Capizzano, S., Fast preconditioners for total variation deblurring with anti-reflective boundary conditions, SIAM J. Matrix Anal. Appl., 32, 3, 785-805 (2011) · Zbl 1269.65144 |
| [6] | Berisha, S.; Nagy, J. G., Iterative methods for image restoration (2012), Department of Mathematics and Computer Science: Department of Mathematics and Computer Science Emory University, Report TR-2012-013 |
| [7] | Bertero, M.; Boccacci, P., Introduction to Inverse Problems in Imaging (1998), Institute of Physics Publ.: Institute of Physics Publ. Bristol · Zbl 0914.65060 |
| [8] | Bertero, M.; Boccacci, P., A simple method for the reduction of boundary effects in the Richardson-Lucy approach to image deconvolution, Astronom. Astrophys., 437, 369-374 (2005) |
| [9] | Böttcher, A.; Grudsky, S.; Ramirez de Arellano, E., On the asymptotic behavior of the eigenvectors of large banded Toeplitz matrices, Math. Nachr., 279, 1/2, 121-129 (2006) · Zbl 1101.47015 |
| [10] | Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 9, 766-771 (1988) · Zbl 0646.65042 |
| [11] | Davis, P. J., Circulant Matrices (1979), Wiley: Wiley New York · Zbl 0418.15017 |
| [12] | Dell’Acqua, P.; Donatelli, M.; Estatico, C., Preconditioners for image restoration by reblurring techniques, J. Comput. Appl. Math., 272, 313-333 (2014) · Zbl 1294.65026 |
| [13] | Donatelli, M., Fast transforms for high order boundary conditions in deconvolution problems, BIT, 50, 3, 559-576 (2010) · Zbl 1204.65151 |
| [14] | Donatelli, M.; Estatico, C.; Martinelli, A.; Serra Capizzano, S., Improved image deblurring with anti-reflective boundary conditions and re-blurring, Inverse Probl., 22, 2035-2053 (2006) · Zbl 1167.65474 |
| [15] | Donatelli, M.; Estatico, C.; Nagy, J.; Perrone, L.; Serra Capizzano, S., Anti-reflective boundary conditions and fast 2D deblurring models, (Luk, F., Proceedings of SPIE’s 48th Annual Meeting. Proceedings of SPIE’s 48th Annual Meeting, San Diego, CA, USA, vol. 5205 (2003)), 380-389 |
| [16] | Donatelli, M.; Hanke, M., Fast nonstationary preconditioned iterative methods for ill-posed problems, with application to image deblurring, Inverse Probl., 29, Article 095008 pp. (2013) · Zbl 1285.65030 |
| [17] | Donatelli, M.; Hanke, M., On the condition number of the antireflective transform, Linear Algebra Appl., 432, 1772-1784 (2010) · Zbl 1181.94041 |
| [18] | Donatelli, M.; Luati, A.; Martinelli, A., On the condition number of the antireflective transform, Linear Algebra Appl., 473, 217-235 (2015) · Zbl 1312.62117 |
| [19] | Donatelli, M.; Serra Capizzano, S., Anti-reflective boundary conditions and re-blurring, Inverse Probl., 21, 169-182 (2005) · Zbl 1088.94510 |
| [20] | Golinskii, L.; Serra Capizzano, S., The asymptotic spectrum of non symmetrically perturbed symmetric Jacobi matrix sequences, J. Approx. Theory, 144, 1, 84-102 (2007) · Zbl 1111.15013 |
| [21] | Hanke, M.; Hansen, P. C., Regularization methods for large-scale problems, Surv. Math. Ind., 3, 253-315 (1993) · Zbl 0805.65058 |
| [22] | Hanke, M.; Nagy, J. G., Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques, Inverse Probl., 12, 157-173 (1996) · Zbl 0859.65141 |
| [23] | Hanke, M.; Nagy, J. G.; Plemmons, R. J., Preconditioned iterative regularization for ill-posed problems, (Reichel, L.; Ruttan, A.; Varga, R. S., Numerical Linear Algebra (1993), de Gruyter: de Gruyter Berlin), 141-163 · Zbl 0794.65039 |
| [24] | Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems (1998), SIAM: SIAM Philadelphia |
| [25] | Hansen, P. C.; Nagy, J. G.; O’Leary, D. P., Deblurring Images: Matrices, Spectra and Filtering (2006), SIAM: SIAM Philadelphia · Zbl 1112.68127 |
| [27] | Kilmer, M. E., Cauchy-like preconditioners for two-dimensional ill-posed problems, SIAM J. Matrix Anal. Appl., 20, 777-799 (1999) · Zbl 0931.65128 |
| [28] | Lagendijk, R. L.; Biemond, J., Iterative Identification and Restoration of Images (1991), Springer-Verlag: Springer-Verlag New York · Zbl 0752.68093 |
| [29] | Nagy, J. G.; Palmer, K.; Perrone, L., Iterative methods for image deblurring: a Matlab object oriented approach, Numer. Algorithms, 36, 73-93 (2004) · Zbl 1048.65039 |
| [30] | Ng, M. K.; Chan, R. H.; Tang, W. C., A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21, 3, 851-866 (1999) · Zbl 0951.65038 |
| [31] | Perrone, L., Kronecker product approximations for image restoration with anti-reflective boundary conditions, Numer. Linear Algebra Appl., 13, 1, 1-22 (2006) · Zbl 1174.94309 |
| [32] | Reeves, S. J., Fast image restoration without boundary artifacts, IEEE Trans. Image Process., 14, 1448-1453 (2005) |
| [33] | Serra Capizzano, S., A note on anti-reflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25, 3, 1307-1325 (2003) · Zbl 1062.65152 |
| [34] | Shi, Y.; Chang, Q., Acceleration methods for image restoration problem with different boundary conditions, Appl. Numer. Math., 58, 5, 602-614 (2008) · Zbl 1162.65065 |
| [35] | Strang, G., The discrete cosine transform, SIAM Rev., 41, 1, 135-147 (1999) · Zbl 0939.42021 |
| [36] | Tablino Possio, C., Truncated decompositions and filtering methods with reflective/anti-reflective boundary conditions: a comparison, (Olshevsky, V.; Tyrtyshnikov, E., Matrix Methods: Theory, Algorithms, Applications. Dedicated to the Memory of Gene Golub (2010), World Scientific Publishing), 382-408 · Zbl 1216.94019 |
| [37] | Zamarashkin, N.; Tyrtyshnikov, E., On the distribution of eigenvectors of Toeplitz matrices with weakened requirements on the generating function, Russian Math. Surveys, 52, 6, 1333 (1997) · Zbl 0914.15004 |
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.
