Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
arXiv:2205.06228 · doi:10.1109/TIT.2023.3273181
Abstract
We consider the problem of recovering an low-rank matrix with -sparse singular vectors from a small number of linear measurements (sketch). We propose a sketching scheme and an algorithm that can recover the singular vectors with high probability, with a sample complexity and running time that both depend only on and not on the ambient dimensions and . Our sketching operator, based on a scheme for compressed sensing by Li et al. and Bakshi et al., uses a combination of a sparse parity check matrix and a partial DFT matrix. Our main contribution is the design and analysis of a two-stage iterative algorithm which recovers the singular vectors by exploiting the simultaneously sparse and low-rank structure of the matrix. We derive a nonasymptotic bound on the probability of exact recovery, which holds for any sparse, low-rank matrix. We also show how the scheme can be adapted to tackle matrices that are approximately sparse and low-rank. The theoretical results are validated by numerical simulations and comparisons with existing schemes that use convex programming for recovery.
arXiv comment46 pages, 14 figures. A shorter version appeared at the 2022 IEEE International Symposium on Information Theory
References in corpus (8)
- Community structure in social and biological networks
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Sketching as a Tool for Numerical Linear Algebra
- An overview of low-rank matrix recovery from incomplete observations
- Practical sketching algorithms for low-rank matrix approximation
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Estimation of Simultaneously Sparse and Low Rank Matrices
- A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain