Abstract: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.
| Comments: | 19 pages, 3 figures |
| Subjects: | Numerical Analysis (math.NA); Computation (stat.CO) |
| MSC classes: | 65F20, 65C05, 65Y20, 62J05 |
| Cite as: | arXiv:2605.25809 [math.NA] |
| (or arXiv:2605.25809v1 [math.NA] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25809 arXiv-issued DOI via DataCite (pending registration) |
From: Irina-Beatrice Haas [view email]
[v1]
Mon, 25 May 2026 13:02:43 UTC (187 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。