<p><a href="https://arxiv.org/pdf/1810.08171.pdf" rel="nofollow noreferrer">Here</a> is a fairly recent paper by Balcan et. al. from SODA'19 that gives a sample-optimal algorithm to test matrix rank. Note, in the query complexity setting, you need to have an appropriate notion of gap, which is exactly what they consider here. The paper should also list most of the relevant references.</p>

CC BY-SA 4.0
2020-02-06T01:25:58.287Z
2020-02-06T01:25:58.287Z
Ainesh Bakshi
<p>I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:</p>

<p>What is the status of approximating rank of a matrix in these models (e.g., communication complexity, query complexity, streaming etc)? Here the goal is to output a number which is approximately the rank of the matrix. Is there a paper(s) which presents the state-of-the-art regarding this?</p>

<p>A quick Google search points only to the papers involving low rank approximation. The exact rank problem, however, has high lower bound (in randomized communication complexity) which follows from a reduction from singularity problem (i.e., whether a matrix is of full rank or not).</p>

<cc.complexity-theory><communication-complexity>
Matrix rank approximation
withhighprob
# Matrix rank approximation

(Asked by: username_0 on 2020-02-05)

I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:

What is the status of approximating rank of a matrix in these models (e.g., communication complexity, query complexity, streaming etc)? Here the goal is to output a number which is approximately the rank of the matrix. Is there a paper(s) which presents the state-of-the-art regarding this?

A quick Google search points only to the papers involving low rank approximation. The exact rank problem, however, has high lower bound (in randomized communication complexity) which follows from a reduction from singularity problem (i.e., whether a matrix is of full rank or not).

**Tags:** cc.complexity-theory, communication-complexity


---

## 1 answers

### Answer by username_1 on 2020-02-06. Score: 1

[Here](https://arxiv.org/pdf/1810.08171.pdf) is a fairly recent paper by Balcan et. al. from SODA'19 that gives a sample-optimal algorithm to test matrix rank. Note, in the query complexity setting, you need to have an appropriate notion of gap, which is exactly what they consider here. The paper should also list most of the relevant references.


---

