Jointly clustering rows and columns of binary matrices
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 16, 2014
- Source ID
- 10.1145/2637364.2592005
Entities
People
- Bruce Hajek
- Jiaming Xu
- Kai Zhu
- Lei Ying
- R. Srikant
- Rui Wu
Organizations
- Air Force Office of Scientific Research
- Arizona State University
- National Science Foundation
- University of Illinois Urbana–Champaign