  As the scale of problems and data used for experimental design, signal
processing and data assimilation grow, the oft-occuring least squares
subproblems are correspondingly growing in size. As the scale of these least
squares problems creates prohibitive memory movement costs for the usual
incremental QR and Krylov-based algorithms, randomized least squares problems
are garnering more attention. However, these randomized least squares solvers
are difficult to integrate application algorithms as their uncertainty limits
practical tracking of algorithmic progress and reliable stopping. Accordingly,
in this work, we develop theoretically-rigorous, practical tools for
quantifying the uncertainty of an important class of iterative randomized least
squares algorithms, which we then use to track algorithmic progress and create
a stopping condition. We demonstrate the effectiveness of our algorithm by
solving a 0.78 TB least squares subproblem from the inner loop of incremental
4D-Var using only 195 MB of memory.
