Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913410838429696 |
|---|---|
| author | Liu, Xiaoqi Venkataramanan, Ramji |
| author_facet | Liu, Xiaoqi Venkataramanan, Ramji |
| contents | We consider the problem of recovering an $n_1 \times n_2$ low-rank matrix with $k$-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 $k$ and not on the ambient dimensions $n_1$ and $n_2$. 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 $n_1\times n_2 $ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_06228 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing Liu, Xiaoqi Venkataramanan, Ramji Information Theory Signal Processing E.4 We consider the problem of recovering an $n_1 \times n_2$ low-rank matrix with $k$-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 $k$ and not on the ambient dimensions $n_1$ and $n_2$. 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 $n_1\times n_2 $ 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. |
| title | Sketching sparse low-rank matrices with near-optimal sample- and time-complexity using message passing |
| topic | Information Theory Signal Processing E.4 |
| url | https://arxiv.org/abs/2205.06228 |