We introduce a "learning-based" algorithm for the low-rank decomposition
problem: given an $n \times d$ matrix $A$, and a parameter $k$, compute a
rank-$k$ matrix $A'$ that minimizes the approximation loss $\|A-A'\|_F$. The
algorithm uses a training set of input matrices in order to optimize its
performance. Specifically, some of the most efficient approximate algorithms
for computing low-rank approximations proceed by computing a projection $SA$,
where $S$ is a sparse random $m \times n$ "sketching matrix", and then
performing the singular value decomposition of $SA$. We show how to replace the
random matrix $S$ with a "learned" matrix of the same sparsity to reduce the
error.
Our experiments show that, for multiple types of data sets, a learned sketch
matrix can substantially reduce the approximation loss compared to a random
matrix $S$, sometimes by one order of magnitude. We also study mixed matrices
where only some of the rows are trained and the remaining ones are random, and
show that matrices still offer improved performance while retaining worst-case
guarantees.
Finally, to understand the theoretical aspects of our approach, we study the
special case of $m=1$. In particular, we give an approximation algorithm for
minimizing the empirical loss, with approximation factor depending on the
stable rank of matrices in the training set. We also show generalization bounds
for the sketch matrix learning problem.

本文介绍了一种基于学习的算法来解决低秩分解问题，并且通过学习用稀疏矩阵来代替随机矩阵可以减小近似误差。同时，给出了针对稀疏矩阵学习问题的泛化界及近似算法。