We study the following generalized matrix rank estimation problem: given an n×n matrix and a constant c≥0, estimate the number of eigenvalues that are greater than c. In the distributed setting, the matrix of interest is the sum of m matrices held by separate machines. We show that any deterministic algorithm solving this problem must communicate Ω(n^2) bits, which is order-equivalent to transmitting the whole matrix. In contrast, we propose a randomized algorithm that communicates only O(n) bits. The upper bound is matched by an Ω(n) lower bound on the randomized communication complexity. We demonstrate the practical effectiveness of the proposed algorithm with some numerical experiments.
Yuchen Zhang is a Ph.D. candidate in computer science at University of California, Berkeley. His research interests span machine learning, optimization and statistics. At Berkeley, he works in the Statistical Artificial Intelligence Lab (SAIL) under the joint supervision of Michael Jordan and Martin Wainwright. He obtained his MA in statistics from Berkeley and received a BS in computer science from Tsinghua University.