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.
We first study the rank testing problem when we can only non-adaptively query entries. The goal is to design a sampling scheme on the entries of the unknown matrix @math and an algorithm so that we can distinguish whether @math is of rank @math , or at least an @math -fraction of entries of @math should be modified in order to reduce the rank to @math . This problem was first proposed by Krauthgamer and Sasson in @cite_49 with a sample complexity upper bound of @math . In this work, we improve this to @math for every @math and @math , and complement this with a matching lower bound, showing that any algorithm with constant success probability requires at least @math samples:
@cite_49
2075290628
Data dimensionality is a crucial issue in a variety of settings, where it is desirable to determine whether a data set given in a high-dimensional space adheres to a low-dimensional structure. We study this problem in the framework of property testing: Given a query access to a data set S, we wish to determine whether S is low-dimensional, or whether it should be modified significantly in order to have the property. Allowing a constant probability of error, we aim at algorithms whose complexity does not depend on the size of S.We present algorithms for testing the low-dimensionality of a set of vectors and for testing whether a matrix is of low rank. We then address low-dimensionality in metric spaces. For vectors in the metric space l 1 , we show that low-dimensionality is not testable. For l 2 , we show that a data set can be tested for having a low-dimensional structure, but that the property of approximately having such a structure is not testable.