Singular Value Decompositions Sample Clauses

Singular Value Decompositions. ‌ The problem formulation (2.1) is a linear inverse problem. One method of solving linear inverse problems is to compute a factorization of the matrix K into a product of matrices for which solving a linear system is easy. It may not be easy to compute K−1 directly (if it exists), but computing an explicit or implicit approximate inverse of the factorization can be much more tractable. There are many factorization techniques. The particular choice of factorization can depend on the structure of the matrix K. For example, Cholesky factorization can only be used on matrices which are symmetric positive definite. The singular value decomposition (SVD) is an attractive factorization in part because it enables straightforward solution of linear systems and, as we will see, particularly makes it easy to adjust the solution via regularization if needed. The singular value decomposi- tion decomposes a matrix K into a product U ΣV T (or V ∗, the conjugate transpose, for complex K; we assume K is real), where U and V are orthonormal and Σ is a non-negative diagonal matrix, typically chosen so that the entries are sorted in de- scending order going down the diagonal. If and only if the diagonal entries of Σ are nonzero, the matrix K is full rank, and the inverse of K is K−1 = V Σ−1U T [21]. There are several factors that prohibit the SVD from being used commonly on general problems. The foremost limitation is that computing the singular value de- composition is costly in storage and computation time. The factorization at least doubles the amount of data used to store a matrix (and is much worse for sparse matrices due to loss of sparsity), and the computation takes O(N 3) time to compute for a N × N matrix, with a larger constant than other factorization methods [21]. For very large matrices, this is prohibitively expensive. An added difficulty that is not unique to the SVD arises if K is not numerically full rank. The matrix K may be ill-conditioned, being either rank deficient or having singular values that decay towards zero without a significant gap between values. In the former case, K is not invertible. In the latter case, trying to compute Σ−1 results in extremely large values on the diagonal. If the ith diagonal entry of Σ σ is σi, then the ith entry on the diagonal of Σ−1 is 1 which is large for small σi. When then solving the image deconvolution problem (2.1), the restored solution has amplified noise: using ui to denote the ith column of U (and similarly f...