Abstract

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 bits, which is orderequivalent to transmitting the whole matrix. In contrast, we propose a randomized algorithm that communicates only 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.