Comparing RSVD and Krylov methods for linear inverse problems Abstract   In this work we address regularization parameter estimation for illposed linear inverse problems with an      l    2      penalty. Regularization parameter selection is of utmost importance for all of inverse problems and estimating it generally relies on the experience of the practitioner. For regularization with an      l    2      penalty there exist a lot of parameter selection methods that exploit the fact that the solution and the residual can be written in explicit form. Parameter selection methods are functionals that depend on the regularization parameter where the minimizer is the desired regularization parameter that should lead to a good solution. Evaluation of these parameter selection methods still requires solving the inverse problem multiple times. Efficient evaluation of the parameter selection methods can be done through model order reduction. Two popular model order reduction techniques are Lanczos based methods (a Krylov subspace method) and the Randomized Singular Value Decomposition (RSVD). In this work we compare the two approaches. We derive error bounds for the parameter selection methods using the RSVD. We compare the performance of the Lanczos process versus the performance of RSVD for efficient parameter selection. The RSVD algorithm we use is based on the Adaptive Randomized Range Finder algorithm which allows for easy determination of the dimension of the reduced order model. Some parameter selection also require the evaluation of the trace of a large matrix. We compare the use of a randomized trace estimator versus the use of the Ritz values from the Lanczos process. The examples we use for our experiments are two model problems from geosciences.

Efficient Parallel Stochastic Variance Reduction Algorithms for LargeScale SVD In recent years, the stochastic variance reduced gradient (SVRG) method has been used for singular vector decomposition (SVD), called VRSVD, and VRSVD only uses simple variance reduction iterations, yet can obtain an exponential convergence rate to the optimal solution. Considering that recent years have witnessed great application prospects in largescale SVD, this paper proposes two efficient asynchronous parallel stochastic variance reduction algorithms. Moreover we analyze their convergence properties in theory, and both dense and sparse asynchronous parallel variants can converge with the rate of O(1T). Finally, we extend our algorithms for the SVD problems with multiple singular vectors. Our extensive experimental results show that our algorithms attain ideal parallel speedup ratios and achieve the same PSNR values in a shorter time, and thus they can be widely used in practice.