Adaptive least-squares approximations using randomized singular value decomposition for image restoration problems

This dissertation focuses on new approaches for solving image restoration problems. These reconstruction approaches are based on matrices and tensors. Gray-scale images and color images employ matrix representation, while multi-array data such as color images and video can be represented as a tensor. The numerical experiments are performed on image restoration problems for gray-scale images, color images and videos.Based on the matrix, the reconstruction method applies the least-squares (LS) approximation for reconstructing missing data components which requires an optimal basis set, i.e. a proper orthogonal decomposition (POD) basis. The POD basis is an optimal low-rank basis set that can represent the overall characteristics of the available data. It can be computed by a singular value decomposition (SVD). To decrease the computational time of the standard SVD computation, we employ randomness to generate a low-dimensional basis for the subspace of available data, which allows us to work with a small matrix instead of a large matrix from high-dimensional data. The results of the reconstruction approach via the rSVD method are demonstrated to be efficient in reducing simulation time while preserving accuracy compared to the standard SVD. We create the randomized singular value decomposition (rSVD) by using the different methods: rSVD using QR method, rSVD using eigendecomposition and rSVD using SVD methods. We found that rSVD using eigendecomposition is faster than the others with the same order of accuracy. Also, we investigate the different random strategies, i.e. Gaussian, Uniform, Sparse, and K-mean for constructing the random matrices which are used in the rSVD algorithm. For the effectiveness of using the different strategies, K-mean is more accurate than the other three techniques while the other three have the same order of accuracy with less computation time. Moreover, we propose some modifications of the reconstruction approach by using different efficient techniques. First, we approximate the missing components by the known neighborhood pixels. Next, we apply the patch grouping technique for a set of the similar patches to compute the POD basis. The results show the improvements made by these proposed approaches.Based on tensor, we adapt the methods for the second order tensor (or matrix) to the third order tensor. We consider the tensor reconstruction. The LS approximation is applied for reconstructing missing data that is formed as a vector or multi- dimensional pixels. We also consider a tensor-rSVD and randomized tensor SVD for computing the POD tensor. The numerical experiments are performed on color images and video. The resulting tensor reconstruction approach when using tensor-rSVD and randomized tensor SVD is shown to reduce the computation time with some trade off on accuracy compared to tensor SVD.