Abstract
We show that for the problem of testing if a matrix $A \in F^{n \times n}$has rank at most $d$, or requires changing an $\epsilon$-fraction of entries tohave rank at most $d$, there is a non-adaptive query algorithm making$\widetilde{O}(d^2/\epsilon)$ queries. Our algorithm works for any field $F$.This improves upon the previous $O(d^2/\epsilon^2)$ bound (SODA'03), andbypasses an $\Omega(d^2/\epsilon^2)$ lower bound of (KDD'14) which holds if thealgorithm is required to read a submatrix. Our algorithm is the first suchalgorithm which does not read a submatrix, and instead reads a carefullyselected non-adaptive pattern of entries in rows and columns of $A$. Wecomplement our algorithm with a matching query complexity lower bound fornon-adaptive testers over any field. We also give tight bounds of$\widetilde{\Theta}(d^2)$ queries in the sensing model for which query accesscomes in the form of $\langle X_i, A\rangle:=tr(X_i^\top A)$; perhapssurprisingly these bounds do not depend on $\epsilon$. We next develop a novel property testing framework for testing numericalproperties of a real-valued matrix $A$ more generally, which includes thestable rank, Schatten-$p$ norms, and SVD entropy. Specifically, we propose abounded entry model, where $A$ is required to have entries bounded by $1$ inabsolute value. We give upper and lower bounds for a wide range of problems inthis model, and discuss connections to the sensing model above.