Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches

Kurzfassung/Abstract

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. [Compressed sensing and robust recovery of low rank matrices, in Proceedings of the 42nd IEEE Asilomar Conference on Signals, Systems and Computers, 2008, pp. 1043–1047], which is based on an approach by Woolfe et al. [Appl. Comput. Harmon. Anal., 25 (2008), pp. 335–366]. Using tools from nonasymptotic 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.