Sketching sparse matrices, covariances, and graphs via tensor products

Gautam Dasarathy, Parikshit Shah, Badri Narayan Bhaskar, Robert D. Nowak

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


This paper considers the problem of recovering an unknown sparse p × p matrix X from an m × m matrix Y = AXBT, where A and B are known m × p matrices with m 蠐 p. The main result shows that there exist constructions of the sketching matrices A and B so that even if X has O{script} (p) nonzeros, it can be recovered exactly and efficiently using a convex program as long as these nonzeros are not concentrated in any single row/column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as O{script}(√# nonzeros in X × log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require nonstandard techniques. Indeed, our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p × n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DDT is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S = AD with A ∈ Rm × p.

Original languageEnglish (US)
Article number7008533
Pages (from-to)1373-1388
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - Mar 1 2015
Externally publishedYes


  • 1 minimization
  • compressed sensing
  • covariance sketching
  • distributed sparsity
  • graph sketching
  • multi-dimensional signal processing
  • sketching
  • tensor products

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Sketching sparse matrices, covariances, and graphs via tensor products'. Together they form a unique fingerprint.

Cite this