Abstract: Sparsity is a basic property of real vectorsthat is exploited in a wide variety of ma-chine learning applications. In this work, wedescribe property testing algorithms for spar-sity that observe a low-dimensional projec-tion of the input. We consider two settings.In the first setting, we test sparsity with re-spect to an unknown basis: given input vec-tors $y_1 ,...,y_p \in R^d$ whose concatenation ascolumns forms $Y \in R^{d \times p}$ , does $Y = AX$for matrices $A \in R^{d\times m}$ and $X \in R^{m \times p}$ suchthat each column of $X$ is $k$-sparse, or is $Y$“far” from having such a decomposition? Inthe second setting, we test sparsity with re-spect to a known basis: for a fixed design ma-trix $A \in R^{d \times m}$ , given input vector $y \in R^d$ ,is $y = Ax$ for some $k$-sparse vector $x$ or is$y$ “far” from having such a decomposition?We analyze our algorithms using tools fromhigh-dimensional geometry and probability.