A Preconditioner based on Non-uniform Row Sampling for Linear Least Squares Problems
For practitioners solving large-scale least squares problems, this method offers a preconditioner that maintains sparsity and handles ill-conditioned matrices, though it is an incremental improvement over existing randomized sampling approaches.
The paper proposes a preconditioner for linear least squares problems using non-uniform row sampling and Gauss-Seidel iterations, which preserves sparsity and improves conditioning for highly overdetermined matrices, demonstrated on various synthetic datasets.
Least squares method is one of the simplest and most popular techniques applied in data fitting, imaging processing and high dimension data analysis. The classic methods like QR and SVD decomposition for solving least squares problems has a large computational cost. Iterative methods such as CG and Kaczmarz can reduce the complexity if the matrix is well conditioned but failed for the ill conditioned cases. Preconditioner based on randomized row sampling algorithms have been developed but destroy the sparsity. In this paper, a new preconditioner is constructed by non-uniform row sampling with a probability proportional to the squared norm of rows. Then Gauss Seidel iterations are applied to the normal equation of the sampled matrix which aims to grab the high frequency component of solution. After all, PCG is used to solve the normal equation with this preconditioner. Our preconditioner can keep the sparsity and improve the poor conditioning for highly overdetermined matrix. Experimental studies are presented on several different simulations including dense Gaussian matrix, `semi Gaussian' matrix, sparse random matrix, `UDV' matrix, and random graph Laplacian matrix to show the effectiveness of the proposed least square solver.