Applications of the Shannon-Hartley theorem to data streams and sparse recovery
Applications of the Shannon-Hartley theorem to data streams and sparse recovery
复制标题
香农-哈特利定理在数据流和稀疏恢复中的应用
DOI：
10.1109/isit.2012.6283954
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
Eric Price;David P. Woodruff
Shannon-Hartley定理可以根据信号与噪声功率的比率在高斯通道上传输信息的最大速率。更简单的证明（η1-2/ρ）绑定在近似数据流中p-th频率矩的线性测量数的数量上，并显示了对于此问题很难的新分布，（2）我们显示那是用C-Approximateℓ2/ℓ2保证在N维矢量X上解决K-SPARSE恢复问题所需的测量值为ω（k log（n/k）/log c）。 （k log* k log（n/k）/log c）上限。
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 ℓ2/ℓ2 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.