论文标题
通过杠杆分数估计来绘制矩阵最小二乘
Sketching Matrix Least Squares via Leverage Scores Estimates
论文作者
论文摘要
我们考虑$ \ |的矩阵最小二乘问题问题\ Mathbf {a} \ Mathbf {X} - \ Mathbf {B} \ | _f^2 $其中，设计矩阵$ \ Mathbf {a} \ in \ in \ Mathbb {r}^{r}^{n \ times r}^{我们建议创建一个素描的版本$ \ | \ tilde {\ MathBf {a}} \ MathBf {X} - \ tilde {\ MathBf {b}}} \ | _f^2 $，其中绘制的矩阵$ \ tilde {\ tilde {\ tilde {\ tillbf {\ mathbf {a}}} $ and $ \ tilde covere $ \ mathbf {a} $和$ \ mathbf {b} $。行的子集是通过基于每行的杠杆得分估计值的随机采样来确定的。我们说，如果其解决方案$ \ tilde {\ mathbf {x}} _ {\ rm \ text {opt}} = \ text {argmin} \ | \ tilde {\ MathBf {a}} \ MathBf {X} - \ tilde {\ MathBf {\ MathBf {b}}} \ | _f^2 $满足$ \ | \ | \ | \ Mathbf {a} a} \ tilde {\ tilde { \ text {opt}} - \ mathbf {b} \ | _f^2 \ leq（1+ε）\ min \ | \ Mathbf {a} \ Mathbf {X} - \ Mathbf {B} \ | _f^2 $具有高概率。我们证明，$ε$ - 精制解决方案所需的样品数量为$ O（r/（βε））$，其中$β\ in（0,1] $是衡量杠杆评分估计质量的量度。
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 $ε$-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+ε) \min \| \mathbf{A}\mathbf{X}-\mathbf{B} \|_F^2$ with high probability. We prove that the number of samples required for an $ε$-accurate solution is $O(r/(βε))$ where $β\in (0,1]$ is a measure of the quality of the leverage score estimates.
