Jointly clustering rows and columns of binary matrices: Algorithms and trade-offs

Jiaming Xu, Rui Wu, Kai Zhu, Bruce Hajek, R. Srikant, Lei Ying

Research output: Contribution to journalConference articlepeer-review


In standard clustering problems, data points are represented by vectors, and by stacking them together, one forms a data matrix with row or column cluster structure. In this paper, we consider a class of binary matrices, arising in many applications, which exhibit both row and column cluster structure, and our goal is to exactly recover the underlying row and column clusters by observing only a small fraction of noisy entries. We first derive a lower bound on the minimum number of observations needed for exact cluster recovery. Then, we study three algorithms with different running time and compare the number of observations needed by them for successful cluster recovery. Our analytical results show smooth time-data trade-offs: one can gradually reduce the computational complexity when increasingly more observations are available.

Original languageEnglish (US)
Pages (from-to)29-41
Number of pages13
JournalPerformance Evaluation Review
Issue number1
StatePublished - Jun 20 2014
EventACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2014 - Austin, United States
Duration: Jun 16 2014Jun 20 2014


  • Clustering
  • Low-rank matrix recovery
  • Spectral method

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Jointly clustering rows and columns of binary matrices: Algorithms and trade-offs'. Together they form a unique fingerprint.

Cite this