Expressivity of expand-and-sparsify representations

Sanjoy Dasgupta, Christopher Tosh

A simple sparse coding mechanism appears in the sensory systems of several organisms: to a coarse approximation, an input $x\in {\mathbb{R}}^d$ is mapped to much higher dimension $m\gg d$…