Truncated Singular Value Decomposition Approximation for Structured Matrices via Kronecker Product Summation Decomposition Open Access

Abstract

Singular value decompositions are a particularly attractive matrix factorization for ill-posed problems because singular value magnitudes reveal information about the relative importance of data in the matrix. However, computing a singular value decomposition is typically computationally infeasible for large problems, as the cost for traditional methods, such as Lanczos bidiagonalization-based approaches and randomized methods, scales linearly with the number of entries in the matrix times the number of singular values computed. In this work we present two new algorithms and one new hybrid approach for computing the singular value decomposition of matrices cheaply approximable as an ordered Kronecker summation decomposition. Unlike previous work using ordered Kronecker summation decompositions, the factorizations these methods produce are more accurate for certain classes of matrices and have nonnegative singular values. The three proposed methods are also faster, with lower computational and spatial complexity, although also lower accuracy, than traditional methods. Our Kronecker-based methods therefore enable singular value decomposition approximations on larger matrices than traditional methods, while providing more accurate results in many cases than previous Kronecker-based singular value decompositions. We demonstrate the efficacy of these methods on a variety of image deconvolution problems for which the image is modeled as a regular grid of data.

Table of Contents

1 Introduction                                                                    1 2 Background                                                                      6 2.1 Image Deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . .     6 2.2 Blind Deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . .     11 2.3 Singular Value Decompositions . . . . . . . . . . . . . . . . . . . . .       12 2.4 Kronecker Products . . . . . . . . . . . . . . . . . . . . . . . . . . . .    15 2.5 Kronecker Product Summation Decomposition . . . . . . . . . . . . .           16 2.6 SVDs of Kronecker Products . . . . . . . . . . . . . . . . . . . . . . .      19 2.7 A Note on Tensors . . . . . . . . . . . . . . . . . . . . . . . . . . . .     20 3 Baseline Diagonal Method                                                        27 3.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  27 3.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29 3.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     31 3.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   32 3.4.1 Direct Reconstruction . . . . . . . . . . . . . . . . . . . . . .           33 3.4.2 Approximated Singular Values . . . . . . . . . . . . . . . . . .            37 3.4.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . .         40 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     42 4 Kronecker Truncation Method                                                     43 4.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  43 4.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  46 4.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     48 4.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   50 4.4.1 Direct Reconstruction . . . . . . . . . . . . . . . . . . . . . .           50 4.4.2 Approximated Singular Values . . . . . . . . . . . . . . . . . .            54 4.4.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . .         56 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     58 5 Reordered Kronecker Method                                                      59 5.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  59 5.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  61 5.2.1 Algorithm Details . . . . . . . . . . . . . . . . . . . . . . . . .         63 5.2.2 Efficacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        66 5.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     67 5.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   69 5.4.1 Direct Reconstruction . . . . . . . . . . . . . . . . . . . . . .           69 5.4.2 Approximated Singular Values . . . . . . . . . . . . . . . . . .            73 5.4.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . .         75 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     76 6 Hybrid Method                                                                   78 6.1 Derivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  78 6.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  82 6.2.1 Permutation Matrix . . . . . . . . . . . . . . . . . . . . . . .            82 6.2.2 Efficacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        87 6.3 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     89 6.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   89 6.4.1 Direct Reconstruction . . . . . . . . . . . . . . . . . . . . . .           90 6.4.2 Approximated Singular Values . . . . . . . . . . . . . . . . . .            93 6.4.3 Preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . .         95 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     96 7 Comparison to Related Methods                                                   98 7.1 Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . . . . . .    99 7.2 Golub-Kahan-Lanczos Bidiagonalization . . . . . . . . . . . . . . . .        101 7.2.1 Experimental Comparison . . . . . . . . . . . . . . . . . . . .            103 7.2.2 Lanczos with Kronecker Products . . . . . . . . . . . . . . . .            105 7.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          111 7.3 Randomized Algorithms . . . . . . . . . . . . . . . . . . . . . . . . .      111 7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8 Blind Deconvolution                                                            116 8.1 Blind Deconvolution Framework . . . . . . . . . . . . . . . . . . . . .      116 8.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.3 Experimental Performance . . . . . . . . . . . . . . . . . . . . . . . .     120 8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    124 9 Conclusion                                                                     125 A Comparison of Reconstructions                                                  127 A.1 Satellite Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  127 A.2 Grain Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    128 A.3 Motion Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     129 B Comparison of Singular Values                                                  130 B.1 Singular Value Atmospheric Blur Example . . . . . . . . . . . . . . .        130 B.2 Singular Value Motion Example . . . . . . . . . . . . . . . . . . . . .      131 C Comparison of Preconditioners                                                  133 Bibliography                                                                     135

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Computer Science and Informatics
Degree	Ph.D.
Submission	Dissertation
Language	English
Research Field	Applied Mathematics Computer Science
Keyword	image deconvolution kronecker products singular value decomposition inverse problems
Committee Chair / Thesis Advisor	Nagy, James, Emory University
Committee Members	Ruthotto, Lars, Emory University Kong, Jun, Emory University Ettinger, Bree, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Truncated Singular Value Decomposition Approximation for Structured Matrices via Kronecker Product Summation Decomposition ()	2018-04-05 17:23:38 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions