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

<blockquote>
  <p>Li, Wang, &amp; Woodruff. <a href="http://dx.doi.org/10.1145/2623330.2623736" rel="noreferrer">Improved Testing of Low Rank Matrices</a>, KDD '14. (Freely available version from author <a href="http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/lwwKDD.pdf" rel="noreferrer">here</a>.)</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2016-08-23T15:24:29.947Z
2016-08-23T15:24:29.947Z
Joshua Grochow
<p>There is a very neat randomized algorithm by <a href="http://arxiv.org/abs/1203.6705">Cheung, Kwok, and Lau</a>, 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})$.</p>

CC BY-SA 3.0
2016-08-24T09:51:28.557Z
Thank you. This is relevant but much slower than I was looking for.
Simd
CC BY-SA 3.0
2016-08-24T19:42:33.313Z
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
CC BY-SA 3.0
2016-08-25T06:46:45.827Z
That observation is for the exact rank right? I would be happy with an approximation.
Simd
CC BY-SA 3.0
2016-08-25T07:44:48.040Z
I see. This is not very clear from your question.
Sasho Nikolov
CC BY-SA 3.0
2016-08-22T15:46:34.890Z
2016-08-22T15:46:34.890Z
Sasho Nikolov
<p>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? </p>

<linear-algebra>
Estimating the rank of a large sparse matrix
Simd
# Estimating the rank of a large sparse matrix

(Asked by: username_0 on 2016-08-22)

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?

**Tags:** linear-algebra

---

## 2 answers

### Answer by username_1 on 2016-08-23. Score: 5 | Accepted answer

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](http://dx.doi.org/10.1145/2623330.2623736), KDD '14. (Freely available version from author [here](http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/lwwKDD.pdf).)

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.


---

### Answer by username_2 on 2016-08-22. Score: 12

There is a very neat randomized algorithm by [Cheung, Kwok, and Lau](http://arxiv.org/abs/1203.6705), 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})$.

> **Comments:**
> **username_0**: Thank you. This is relevant but much slower than I was looking for.  
> **username_2**: 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.  
> **username_0**: That observation is for the exact rank right? I would be happy with an approximation.  
> **username_2**: I see. This is not very clear from your question.  

---

