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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.