Robust recovery of low-rank matrices and low-tubal-rank tensors from noisy sketches

2022/06/02 by Anna Ma, Ma, Anna, Dominik Stöger +3
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Medical Image Segmentation Techniques #Advanced Neural Network Applications

paper · pdf · doi:10.48550/arxiv.2206.00803

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. (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.

Related

• Sketching for Simultaneously Sparse and Low-Rank Covariance Matrices
• Sketching Low-Rank Plus Diagonal Matrices
• Practical Sketching Algorithms for Low-Rank Tucker Approximation of Large Tensors
• Sketching Sparse Matrices
• Precise expressions for random projections: Low-rank approximation and\n randomized Newton