A common approach for compressing large-scale data is through matrix sketching. In this work, we consider the problem of recovering low-rank matrices from two noisy linear sketches using the double sketching algorithm discussed in Fazel et al. (2008). Using tools from non-asymptotic random matrix theory, we provide the first theoretical guarantees characterizing the error between the output of the double sketch algorithm and the ground truth low-rank matrix. We apply our result to the problems of low-rank matrix approximation and low-tubal-rank tensor recovery.

翻译：压缩大规模数据的一个共同办法是通过矩阵草图绘制。 在这项工作中,我们考虑了利用Fazel等人(2008年)讨论的双重草图算法从两个吵闹的线性草图中恢复低位矩阵的问题。我们利用非简易随机矩阵理论的工具,提供了第一个理论保障,说明双重草图算法产出与地面真相低位矩阵之间错误的特征。我们把结果应用于低位矩阵近似值和低音量回升问题。