  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 scheme
discussed in Fazel et al. (2008), which is based on an approach by Woolfe 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.
