Testing Matrix Rank, Optimally
share
We show that for the problem of testing if a matrix A ∈ F^n × n has rank at most d, or requires changing an ϵ-fraction of entries to have rank at most d, there is a non-adaptive query algorithm making O(d^2/ϵ) queries. Our algorithm works for any field F. This improves upon the previous O(d^2/ϵ^2) bound (SODA'03), and bypasses an Ω(d^2/ϵ^2) lower bound of (KDD'14) which holds if the algorithm is required to read a submatrix. Our algorithm is the first such algorithm which does not read a submatrix, and instead reads a carefully selected non-adaptive pattern of entries in rows and columns of A. We complement our algorithm with a matching query complexity lower bound for non-adaptive testers over any field. We also give tight bounds of Θ(d^2) queries in the sensing model for which query access comes in the form of 〈 X_i, A〉:=tr(X_i^ A); perhaps surprisingly these bounds do not depend on ϵ. We next develop a novel property testing framework for testing numerical properties of a real-valued matrix A more generally, which includes the stable rank, Schatten-p norms, and SVD entropy. Specifically, we propose a bounded entry model, where A is required to have entries bounded by 1 in absolute value. We give upper and lower bounds for a wide range of problems in this model, and discuss connections to the sensing model above.
READ FULL TEXT