# Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds

arXiv: https://arxiv.org/abs/1502.01403 · HTML: https://mlsanity.com/paper/1502.01403/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)

## Abstract (arXiv)

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 Omega(n2) bits, which is order-equivalent to transmitting the whole matrix. In contrast, we propose a randomized algorithm that communicates only widetilde O(n) bits. The upper bound is matched by an Omega(n) lower bound on the randomized communication complexity. We demonstrate the practical effectiveness of the proposed algorithm with some numerical experiments.