We report some fast least square solvers using random sampling. The matrix is transformed by Randomized Hadamard transform and then uniformly randomly sampled. The reduced smaller problem are solved to provide an approximation or a preconditioner.
The complexity for solving a m by n least square is reduced to O(mn log (n)). |