Qi Luan

Superfast Approximate Linear Least Squares Solution of a Highly Overdetermined Linear System of Equations

2019 · arXiv (Cornell University)

With a high probability the Sarlos randomized algorithm of 2006 outputs a nearly optimal least squares solution of a highly overdeterminedlinear system of equations. We propose its simple deterministic variation which computes such a solution …