# Estimating the rank of a large sparse matrix

Consider a large sparse n by n matrix. Are there any methods to estimate its rank in time roughly proportional the number of elements in the matrix?

One thing they show is that one can test (with high probability) if an $n \times n$ matrix has rank $\leq r$ or requires an $\varepsilon$ fraction of its entries to be changed in order to get rank $\leq r$ by querying only $O(r^2 / \varepsilon)$ entries of the matrix.
There is a very neat randomized algorithm by Cheung, Kwok, and Lau, which computes the rank of an $n\times m$ matrix $A$, $n\le m$, in time $O(\mathrm{nnz}(A) + \min\{n^\omega, n\cdot\mathrm{nnz}(A)\})$. Here $\mathrm{nnz}(A)$ is the number of nonzero elements of $A$, and $\omega$ is the matrix multiplication exponent. Not quite what you are asking for, but it does improve on fast matrix multiplication based methods for $\mathrm{nnz}(A) = o(n^{\omega - 1})$.
• I realize that. A trivial observation: you cannot hope for anything better than $O(\mathrm{nnz}(A)^\omega)$, because you can always embed an $n\times n$ matrix into a bigger matrix padded with zeros. – Sasho Nikolov Aug 24 '16 at 19:42