# 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?

This has also been studied from the property testing / query complexity point of view. For example:

Li, Wang, & Woodruff. Improved Testing of Low Rank Matrices, KDD '14. (Freely available version from author here.)

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})$.

• Thank you. This is relevant but much slower than I was looking for. – Lembik Aug 24 '16 at 9:51
• 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
• That observation is for the exact rank right? I would be happy with an approximation. – Lembik Aug 25 '16 at 6:46
• I see. This is not very clear from your question. – Sasho Nikolov Aug 25 '16 at 7:44