8
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
0
12
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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