We show that for the problem of testing if a matrix @math has rank at most @math , or requires changing an @math -fraction of entries to have rank at most @math , there is a non-adaptive query algorithm making @math queries. Our algorithm works for any field @math . This improves upon the previous @math bound (SODA'03), and bypasses an @math 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 @math . We complement our algorithm with a matching query complexity lower bound for non-adaptive testers over any field. We also give tight bounds of @math queries in the sensing model for which query access comes in the form of @math ; perhaps surprisingly these bounds do not depend on @math . We next develop a novel property testing framework for testing numerical properties of a real-valued matrix @math more generally, which includes the stable rank, Schatten- @math norms, and SVD entropy. Specifically, we propose a bounded entry model, where @math is required to have entries bounded by @math 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.
Our non-adaptive sample complexity bound of @math matches what is known with adaptive queries @cite_27 , and thus we show the best known upper bound might as well be non-adaptive.
@cite_27
1983068660
We study the problem of determining if an input matrix A eRm x n can be well-approximated by a low rank matrix. Specifically, we study the problem of quickly estimating the rank or stable rank of A, the latter often providing a more robust measure of the rank. Since we seek significantly sublinear time algorithms, we cast these problems in the property testing framework. In this framework, A either has low rank or stable rank, or is far from having this property. The algorithm should read only a small number of entries or rows of A and decide which case A is in with high probability. If neither case occurs, the output is allowed to be arbitrary. We consider two notions of being far: (1) A requires changing at least an e-fraction of its entries, or (2) A requires changing at least an e-fraction of its rows. We call the former the "entry model" and the latter the "row model". We show: For testing if a matrix has rank at most d in the entry model, we improve the previous number of entries of A that need to be read from O(d2 e2) (Krauthgamer and Sasson, SODA 2003) to O(d2 e). Our algorithm is the first to adaptively query the entries of A, which for constant d we show is necessary to achieve O(1 e) queries. For the important case of d = 1 we also give a new non-adaptive algorithm, improving the previous O(1 e2) queries to O(log2(1 e) e). For testing if a matrix has rank at most d in the row model, we prove an Ω(d e) lower bound on the number of rows that need to be read, even for adaptive algorithms. Our lower bound matches a non-adaptive upper bound of Krauthgamer and Sasson. For testing if a matrix has stable rank at most d in the row model or requires changing an e d-fraction of its rows in order to have stable rank at most d, we prove that reading θ(d e2) rows is necessary and sufficient. We also give an empirical evaluation of our rank and stable rank algorithms on real and synthetic datasets.