Testing Sparsity over Known and Unknown Bases
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:491500, 2018.
Abstract
Sparsity is a basic property of real vectors that is exploited in a wide variety of machine learning applications. In this work, we describe property testing algorithms for sparsity that observe a lowdimensional projec tion of the input. We consider two settings. In the first setting, we test sparsity with respect to an unknown basis: given input vectors $y_1 ,...,y_p \in R^d$ whose concatenation as columns 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}$ 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 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 from highdimensional geometry and probability.
Related Material


