A multilevel sketch-and-solve method for overdetermined least squares problems
For practitioners solving large least squares problems, this work provides a theoretical analysis of multilevel sketching but shows it offers no computational advantage over simpler averaging methods.
The authors propose a multilevel sketch-and-solve method for overdetermined least squares problems, combining solutions from small and large sketches to improve accuracy. However, the overall computational cost is slightly higher than simple averaging, making the naive application unattractive.
Sketch-and-solve (SAS) is a very successful method to efficiently estimate the solution of heavily overdetermined large linear least squares problems. It uses random sketching to reduce the size of the problem, hence reducing the computational cost. Several authors have shown that averaging several solutions from SAS further improves the accuracy, which is measured by the residual associated to the approximate solution. Going further, we combine solutions from sketch-and-solve in a multilevel manner, such that the approximate solution is a combination of SAS samples obtained from small sketches and more accurate correction terms obtained from larger sketches. We first consider the variance of the estimator, which depends on the variance of the coarse samples and the correction terms. We show that the variance of the correction terms on each level follows a trend and decreases faster than the variance of the simple SAS estimator. However, we then show that the overall computational cost of our multilevel framework is slightly higher than that of the simple average estimator, so a naive application of multilevel methods appears unattractive for least squares problems.