Preconditioners for Synthetic Boundary Conditions Sample Clauses

Preconditioners for Synthetic Boundary Conditions. ‌ For synthetic boundary conditions, the matrix A does not have the kind of structure that allows efficient implementation of direct filtering type methods. This is similar to the situation when zero boundary conditions are used, or when reflective and anti-reflective boundary conditions are used with a non- symmetric PSF. In these situations it is necessary to use iterative methods, such as a conjugate gradient type approach (e.g., CG, MINRES, or LSQR). We remark that for conjugate gradient type methods, the matrix A need not be formed explicitly, all that is needed is an efficient approach to compute matrix-vector multiplications with A. This can be done by exploiting the structure of A T B; FFTs can be used to multiply T by accessing only the PSF, and B is a sparse matrix. Or, alternatively, FFTs can be used on appropriately padded image arrays. The latter is used in our implementation. The next issue, then, is to consider preconditioning. Note that for the various boundary conditions considered in this chapter, we have: Zero BC: AZ T BZ Periodic BC: AP T BP Reflective BC: AR T BR Anti-reflective BC: AA T BA Synthetic BC: AS T BS That is, the matrix structures are very similar, and thus we could consider using, for example, AP , or a symmetrized version of AR as a preconditioner for AS. The important property we need is that it is possible to efficiently compute the spectral decomposition of the preconditioner. Note that AP is the standard, and well studied, choice for preconditioning AZ; see, for example, [9, 44, 47]. For synthetic boundary conditions, if the PSF is symmetric, or close to being symmetric, then (the symmetrized) AR is likely to be the most effective preconditioner. If the PSF is far from being symmetric, then AP may be the best choice. Note that if we use AR as the preconditioner for AS, then R R AS AR BS BR AS A 1 I pBS BRq A 1 . If the reflective BC is a good approximation of the synthetic BC, then we expect BS BR to have small rank and small norm. Thus AR would be a good preconditioner for AS. Since the image deblurring problem is extremely ill-conditioned, some care needs to be taken when incorporating preconditioning so that noise in the observed data is not magnified when we solve systems with the pre- conditioner, R ARx AT x y (2.10) (the first equality is due to the symmetry of AR for a symmetrized PSF). This equation can be solved efficiently using the discrete cosine transform (DCT) [48]. However, since AR is usually ill-condi...