Abstract

Sparsity is a basic property of real vectors that i exploited in a wide variety of machine learning applications. In this work, we describe property testing algorithms for sparsity that observe a lowdimensional projection of the input. We consider two settings. In the first setting, we test sparsit with respect to an unknown basis: given input vectors whose concatenation as columns forms does Y = AX for matrices and such that each column of X is k-sparse, or is Y “far” from having such a decomposition? In the second setting, we test sparsity with respect to a known basis: for a fixed design matrix given input vector is y = Ax for some ksparse vector x or is y “far” from having such a decomposition? We analyze our algorithms using tools from high-dimensional geometry and probability.