1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Here 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.

| cite | improve this answer | |
$\endgroup$

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.