Testing Sparsity over Known and Unknown Bases
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:500509, 2018.
Abstract
Sparsity is a basic property of real vectorsthat is exploited in a wide variety of machine learning applications. In this work, wedescribe property testing algorithms for sparsity that observe a lowdimensional projection 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 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 respect to a known basis: for a fixed design matrix $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 fromhighdimensional geometry and probability.
Related Material


