MATH Seminar
| Title: Truncated Singular Value Decomposition Approximation for Structured Matrices via Kronecker Product Summation Decomposition |
|---|
| Defense: Dissertation |
| Speaker: Clarissa Garvey of Emory University |
| Contact: James Nagy, jnagy@emory.edu |
| Date: 2018-04-02 at 4:30PM |
| Venue: MSC W301 |
| Download Flyer |
| 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. |
See All Seminars