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


Sketching Discrete Valued Sparse Matrices


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.

0 users have voted:

Paper Details

Submitted On:
18 November 2018 - 12:01pm
Short Link:
Presentation Slides
Presenter's Name:
Lakshmi N Theagarajan
Paper Code:
Document Year:

Document Files




[1] , "Sketching Discrete Valued Sparse Matrices", IEEE SigPort, 2018. [Online]. Available: Accessed: Apr. 23, 2019.
url = {},
author = { },
publisher = {IEEE SigPort},
title = {Sketching Discrete Valued Sparse Matrices},
year = {2018} }
T1 - Sketching Discrete Valued Sparse Matrices
AU -
PY - 2018
PB - IEEE SigPort
UR -
ER -
. (2018). Sketching Discrete Valued Sparse Matrices. IEEE SigPort.
, 2018. Sketching Discrete Valued Sparse Matrices. Available at:
. (2018). "Sketching Discrete Valued Sparse Matrices." Web.
1. . Sketching Discrete Valued Sparse Matrices [Internet]. IEEE SigPort; 2018. Available from :