Application of the partitioning method to specific Toeplitz matrices

Stanimirović, P. ; Miladinović, M. ; Stojanović, I. ; Miljković, S.

International Journal of Applied Mathematics and Computer Science, Tome 23 (2013) no. 4, pp. 809-821.

Résumé

We propose an adaptation of the partitioning method for determination of the Moore–Penrose inverse of a matrix augmented by a block-column matrix. A simplified implementation of the partitioning method on specific Toeplitz matrices is obtained. The idea for observing this type of Toeplitz matrices lies in the fact that they appear in the linear motion blur models in which blurring matrices (representing the convolution kernels) are known in advance. The advantage of the introduced method is a significant reduction in the computational time required to calculate the Moore–Penrose inverse of specific Toeplitz matrices of an arbitrary size. The method is implemented in MATLAB, and illustrative examples are presented.

Détail

Keywords: Moore-Penrose inverse, partitioning method, Toeplitz matrices, MATLAB, image restoration
Mots-clés : odwrotność Moore-Penrose, metoda partycjonowania, macierze Teoplitza, MATLAB, odtworzenie obrazu

Bibliographie

[1] Banham, M.R. and Katsaggelos, A.K. (1997). Digital image restoration, IEEE Signal Processing Magazine 14(2): 24–41.

[2] Ben-Israel, A. and Grevile, T.N.E. (2003). Generalized Inverses, Theory and Applications, Second Edition, Canadian Mathematical Society/Springer, New York, NY.

[3] Bhimasankaram, P. (1971). On generalized inverses of partitioned matrices, Sankhya: The Indian Journal of Statistics, Series A 33(3): 311–314.

[4] Bovik, A. (2005). Handbook of Image and Video Processing, Elsevier Academic Press, Burlington.

[5] Bovik, A. (2009). The Essential Guide to the Image Processing, Elsevier Academic Press, Burlington.

[6] Chantas, G.K., Galatsanos, N.P. and Woods, N.A. (2007). Super-resolution based on fast registration and maximum a posteriori reconstruction, IEEE Transactions on Image Processing 16(7): 1821–1830.

[7] Chountasis, S., Katsikis, V.N. and Pappas, D. (2009a). Applications of the Moore–Penrose inverse in digital image restoration, Mathematical Problems in Engineering 2009, Article ID: 170724, DOI: 10.1155/2010/750352.

[8] Chountasis, S., Katsikis, V.N. and Pappas, D. (2009b). Image restoration via fast computing of the Moore–Penrose inverse matrix, 16th International Conference on Systems, Signals and Image Processing, IWSSIP 2009,Chalkida, Greece, Article number: 5367731.

[9] Chountasis, S., Katsikis, V.N. and Pappas, D. (2010). Digital image reconstruction in the spectral domain utilizing the Moore–Penrose inverse, Mathematical Problems in Engineering 2010, Article ID: 750352, DOI: 10.1155/2010/750352.

[10] Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2001). Introduction to Algorithms, Second Edition, MIT Press, Cambridge, MA.

[11] Courrieu, P. (2005). Fast computation of Moore–Penrose inverse matrices, Neural Information Processing—Letters and Reviews 8(2): 25–29.

[12] Craddock, R.C., James, G.A., Holtzheimer, P.E. III, Hu, X.P. and Mayberg, H.S. (2012). A whole brain FMRI atlas generated via spatially constrained spectral clustering, Human Brain Mapping 33(8): 1914–1928.

[13] Dice, L.R. (1945). Measures of the amount of ecologic association between species, Ecology 26(3): 297–302.

[14] Górecki, T. and Łuczak, M. (2013). Linear discriminant analysis with a generalization of the Moore–Penrose pseudoinverse, International Journal of Applied Mathematics and Computer Science 23(2): 463–471, DOI: 10.2478/amcs-2013-0035.

[15] Graybill, F. (1983). Matrices with Applications to Statistics, Second Edition, Wadsworth, Belmont, CA.

[16] Greville, T.N.E. (1960). Some applications of the pseudo-inverse of matrix, SIAM Review 3(1): 15–22.

[17] Hansen, P.C., Nagy, J.G. and O’Leary, D.P. (2006). Deblurring Images: Matrices, Spectra, and Filtering, SIAM, Philadelphia, PA.

[18] Hillebrand, M. and Muller, C.H. (2007). Outlier robust corner-preserving methods for reconstructing noisy images, The Annals of Statistics 35(1): 132–165.

[19] Hufnagel, R.E. and Stanley, N.R. (1964). Modulation transfer function associated with image transmission through turbulence media, Journal of the Optical Society of America 54(1): 52–60.

[20] Kalaba, R.E. and Udwadia, F.E. (1993). Associative memory approach to the identification of structural and mechanical systems, Journal of Optimization Theory and Applications 76(2): 207–223.

[21] Kalaba, R.E. and Udwadia, F.E. (1996). Analytical Dynamics: A New Approach, Cambridge University Press, Cambridge.

[22] Karanasios, S. and Pappas, D. (2006). Generalized inverses and special type operator algebras, Facta Universitatis, Mathematics and Informatics Series 21(1): 41–48.

[23] Katsikis, V.N., Pappas, D. and Petralias, A. (2011). An improved method for the computation of the Moore–Penrose inverse matrix, Applied Mathematics and Computation 217(23): 9828–9834.

[24] Katsikis, V. and Pappas, D. (2008). Fast computing of the Moore–Penrose inverse matrix, Electronic Journal of Linear Algebra 17(1): 637–650.

[25] MathWorks (2009). Image Processing Toolbox User’s Guide, The Math Works, Inc., Natick, MA.

[26] MathWorks (2010). MATLAB 7 Mathematics, The Math Works, Inc., Natick, MA.

[27] Noda, M.T., Makino, I. and Saito, T. (1997). Algebraic methods for computing a generalized inverse, ACM SIGSAM Bulletin 31(3): 51–52.

[28] Penrose, R. (1956). On a best approximate solution to linear matrix equations, Proceedings of the Cambridge Philosophical Society 52(1): 17–19.

[29] Prasath, V.B.S. (2011). A well-posed multiscale regularization scheme for digital image denoising, International Journal of Applied Mathematics and Computer Science 21(4): 769–777, DOI: 10.2478/v10006-011-0061-7.

[30] Rao, C. (1962). A note on a generalized inverse of a matrix with applications to problems in mathematical statistics, Journal of the Royal Statistical Society, Series B 24(1): 152–158.

[31] Röbenack, K. and Reinschke, K. (2011). On generalized inverses of singular matrix pencils, International Journal of Applied Mathematics and Computer Science 21(1): 161–172, DOI: 10.2478/v10006-011-0012-3.

[32] Schafer, R.W., Mersereau, R.M. and Richards, M.A. (1981). Constrained iterative restoration algorithms, Proceedings of the IEEE 69(4): 432–450.

[33] Shinozaki, N., Sibuya, M. and Tanabe, K. (1972). Numerical algorithms for the Moore–Penrose inverse of a matrix: Direct methods, Annals of the Institute of Statistical Mathematics 24(1): 193–203.

[34] Smoktunowicz, A. and Wróbel, I. (2012). Numerical aspects of computing the Moore–Penrose inverse of full column rank matrices, BIT Numerical Mathematics 52(2): 503–524.

[35] Stojanović, I., Stanimirović, P. and Miladinović, M. (2012). Applying the algorithm of Lagrange multipliers in digital image restoration, Facta Universitatis, Mathematics and Informatics Series 27(1): 41–50.

[36] Udwadia, F.E. and Kalaba, R.E. (1997). An alternative proof for Greville’s formula, Journal of Optimization Theory and Applications 94(1): 23–28.

[37] Udwadia, F.E. and Kalaba, R.E. (1999). General forms for the recursive determination of generalized inverses: Unified approach, Journal of Optimization Theory and Applications 101(3): 509–521.