Applications of the Shannon-Hartley theorem to data streams and sparse recovery

The Shannon-Hartley theorem bounds the maximum rate at which information can be transmitted over a Gaussian channel in terms of the ratio of the signal to noise power. We show two unexpected applications of this theorem in computer science: (1) we give a much simpler proof of an Ω(η^1-2/ρ) bound on the number of linear measurements required to approximate the p-th frequency moment in a data stream, and show a new distribution which is hard for this problem, (2) we show that the number of measurements needed to solve the k-sparse recovery problem on an n-dimensional vector x with the C-approximate ℓ₂/ℓ₂ guarantee is Ω(k log(n/k)/log C). We complement this result with an almost matching O(k log* k log(n/k)/log C) upper bound.