Compressed learning of high-dimensional sparse functions

This paper presents a simple randomised algorithm for recovering high-dimensional sparse functions, i.e. functions ƒ : [0, 1]^d → ℝ which depend effectively only on k out of d variables, meaning ƒ(x1, …, xd) = g(xi1, …, xik ), where the indices 1 ≤ i1 < i2 < … < ik ≤ d are unknown. It is shown that (under certain conditions on g) this algorithm recovers the k unknown coordinates with probability at least 1–6 exp(−L) using only O(k(L+log k)(L+log d)) samples of ƒ.