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 |
|
Department |
|
Degree |
|
Submission |
|
Language |
|
Research Field |
|
关键词 |
|
Committee Chair / Thesis Advisor |
|
Committee Members |
|