We consider the matrix least squares problem of the form $| \mathbf{A} \mathbf{X}-\mathbf{B} |_F^2$ where the design matrix $\mathbf{A} \in \mathbb{R}^{N \times r}$ is tall and skinny with $N \gg r$. We propose to create a sketched version $| \tilde{\mathbf{A}}\mathbf{X}-\tilde{\mathbf{B}} |_F^2$ where the sketched matrices $\tilde{\mathbf{A}}$ and $\tilde{\mathbf{B}}$ contain weighted subsets of the rows of $\mathbf{A}$ and $\mathbf{B}$, respectively. The subset of rows is determined via random sampling based on leverage score estimates for each row. We say that the sketched problem is $\epsilon$-accurate if its solution $\tilde{\mathbf{X}}_{\rm \text{opt}} = \text{argmin } | \tilde{\mathbf{A}}\mathbf{X}-\tilde{\mathbf{B}} |_F^2$ satisfies $|\mathbf{A}\tilde{\mathbf{X}}_{\rm \text{opt}}-\mathbf{B} |_F^2 \leq (1+\epsilon) \min | \mathbf{A}\mathbf{X}-\mathbf{B} |_F^2$ with high probability. We prove that the number of samples required for an $\epsilon$-accurate solution is $O(r/(\beta \epsilon))$ where $\beta \in (0,1]$ is a measure of the quality of the leverage score estimates.
math.NA, cs.DS, cs.NA
This is detailed and standalone derivation of a result that already appears in Appendix A of Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition, arXiv:2006.16438.
@misc{arXiv-LaKo22,
author = {Brett W. Larsen and Tamara G. Kolda},
title = {Sketching Matrix Least Squares via Leverage Scores Estimates},
month = {January},
year = {2022},
eprint = {2201.10638},
eprintclass = {math.NA},
}