Direct Methods Clause Samples

Direct Methods. ‌ Consider a decomposition of the convolution matrix A A U ΣV H, (3.12) where U u1 u2 uN and V v1 v2 vN (3.13) are unitary matrices (N is the number of pixels in the image) and Σ Diag pσ1, σ2, . . . , σN q . (3.14) The classical spectral decomposition and singular value decomposition (SVD) are special cases of (3.12). Note that (3.12) is not necessarily a singular value decomposition, since we allow Σ to have negative diagonal entries. In general, we assume that Σ has nonzero entries on its diagonal. The solution to (3.2) is then given by x V Σ 1U Hy ▇ 1 uHy σk vk. (3.15) When U and V correspond to fast transforms, the solution given by (3.15) can be computed efficiently. For example, with periodic boundary conditions, from (3.3), we have U V F H. Thus multiplication by U H and V can be done with fast Fourier transforms, which has computational complexity Opn2 log nq, when x and y are vectorized versions of images of size n n. When reflective boundary conditions are used, U V CT , where C is the discrete cosine transform matrix. Multiplication with C and CT can also be done in Opn2 log nq. In PYRET, we implemented direct methods of the form (3.15) using Fourier and cosine transforms. When Σ contains some diagonal entries that are small in magnitude, equation (3.15) may lead to magnification of noise in y. In this situation, we need to use regularization. We have implemented the two most common regularization methods: truncated SVD (TSVD) and Tikhonov regulariza- tion. In TSVD regularization, we discard components corresponds to σk’s that are smaller than a threshold τ , xTSVD |σ k | τ uHy σk