Sorry, you need to enable JavaScript to visit this website.

Sketching Discrete Valued Sparse Matrices

Citation Author(s):
Submitted by:
Lakshmi Narasim...
Last updated:
18 November 2018 - 12:01pm
Document Type:
Presentation Slides
Document Year:
2018
Event:
Presenters:
Lakshmi N Theagarajan
Paper Code:
1490
 

The problem of recovering a sparse matrix X from its sketchAXB T is referred to as the matrix sketching problem. Typically, the sketch is a lower dimensional matrix compared to X, and the sketching matrices A and B are known. Matrix sketching algorithms have been developed in the past to recover matrices from a continuous valued vectorspace (e.g., R^N×N ). However, employing such algorithms to recover discrete valued matrices may not be optimal. In this paper, we propose two novel algorithms that can efficiently recover a discrete valued sparse matrix from its sketch. We consider sparse matrices whose non-zero entries belong to a finite set. First, using the well known orthogonal matching pursuit (OMP), we present a matrix sketching algorithm. Second, we present a low-complexity message passing based recovery algorithm which exploits any sparsity structure that is present in X. Our simulation results verify that the proposed algorithms outperform the state-of-art matrix sketching algorithms in recovering discrete valued sparse matrices.

up
0 users have voted: