Testing noisy linear functions for sparsity
Testing noisy linear functions for sparsity
复制标题
测试噪声线性函数的稀疏性
DOI：
10.1145/3357713.3384239
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Servedio, Rocco A.
中科院分区：
文献类型：
--
作者：
Chen, Xue;De, Anindya;Servedio, Rocco A.
我们考虑如下基本推理问题：存在未知的高维向量w ∈ n，给出一个算法访问标记对（x，y），其中x ∈ n是一个测量，且y =w·x+noise.判断目标向量是否（近似）k-稀疏的复杂度是多少？这个问题的恢复模拟-给定稀疏的承诺，找到或近似的向量w-是著名的稀疏恢复问题，在信号处理，统计学和计算机科学中有着丰富的工作，我们研究这个问题的决策版本（即决定是否未知wisk-sparse）从属性测试的Vantage位置。我们的重点是回答以下高层次的问题：什么时候可以有效地测试是否未知的目标vectorwis稀疏与远离稀疏使用的样本数是完全独立的dimensionn？我们考虑的自然设置中，从一个i.i.d.产品分布dover得出的噪声过程是独立的输入x。作为我们的主要结果，我们给出了一个通用的算法，它解决了上述测试问题，使用的样本数是完全独立的环境维数n，只要asD不是高斯。事实上，我们的算法是完全噪声容忍的，在这个意义上，对于任意的w，它近似计算的距离wo最近的k-稀疏向量。为了补充这一算法的结果，我们表明，削弱我们的任何条件，使其信息理论上不可能foranyalgorithm解决测试问题，少于基本上logn样本。因此，我们的条件本质上是表征当它是可能的测试噪声线性函数的稀疏性与恒定的样本complexity.Our算法的方法是基于有关的输出分布（即ofy）的累积量与初等幂和对称多项式inwand使用后者来衡量的稀疏性ofw。这种方法主要依赖于概率论中的Marcinkiewicz定理。事实上，为了获得有效的样本复杂度界限与我们的方法，我们证明了一个新的有限版本的Marcinkiewicz定理。这涉及到用有关整函数零点分布的结果来扩展原始证明中使用的复杂分析论证。
We consider the following basic inference problem: there is an unknown high-dimensional vectorw∈ ℝn, and an algorithm is given access to labeled pairs (x,y) wherex∈ ℝnis a measurement andy=w·x+noise. What is the complexity of deciding whether the target vectorwis (approximately)k-sparse? The recovery analogue of this problem — given the promise thatwis sparse, find or approximate the vectorw— is the famoussparse recoveryproblem, with a rich body of work in signal processing, statistics, and computer science.We study the decision version of this problem (i.e. deciding whether the unknownwisk-sparse) from the vantage point ofproperty testing. Our focus is on answering the following high-level question: when is it possible to efficientlytestwhether the unknown target vectorwis sparse versus far-from-sparse using a number of samples which iscompletely independentof the dimensionn? We consider the natural setting in whichxis drawn from an i.i.d. product distributionDover ℝnand thenoiseprocess is independent of the inputx. As our main result, we give a general algorithm which solves the above-described testing problem using a number of samples which is completely independent of the ambient dimensionn, as long asDis not a Gaussian. In fact, our algorithm isfully noise tolerant, in the sense that for an arbitraryw, it approximately computes the distance ofwto the closestk-sparse vector. To complement this algorithmic result, we show that weakening any of our conditions makes it information-theoretically impossible foranyalgorithm to solve the testing problem with fewer than essentially lognsamples. Thus our conditions essentially characterize when it is possible to test noisy linear functions for sparsity with constant sample complexity.Our algorithmic approach is based on relating the cumulants of the output distribution (i.e. ofy) with elementary power sum symmetric polynomials inwand using the latter to measure the sparsity ofw. This approach crucially relies on a theorem of Marcinkiewicz from probability theory. In fact, to obtain effective sample complexity bounds with our approach, we prove a new finitary version of Marcinkiewicz’s theorem. This involves extending the complex analytic arguments used in the original proof with results about the distribution of zeros of entire functions.
登录
查看更多内容
基于样本的高维凸性测试
DOI：
--
发表时间：
2017
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Xi Chen;Adam Freilich;R. Servedio;Timothy Sun
通讯作者：
Timothy Sun
测试低复杂度仿射不变属性
DOI：
10.1137/1.9781611973105.97
发表时间：
2012
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Arnab Bhattacharyya;E. Fischer;Shachar Lovett
通讯作者：
Shachar Lovett
DOI：
10.1002/rsa.20507
发表时间：
2010
期刊：
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Arnab Bhattacharyya;Elena Grigorescu;A. Shapira
通讯作者：
A. Shapira
DOI：
--
发表时间：
1939
期刊：
影响因子：
--
作者：
J. Marcinkiewicz
通讯作者：
J. Marcinkiewicz
香农-哈特利定理在数据流和稀疏恢复中的应用
DOI：
10.1109/isit.2012.6283954
发表时间：
2012
期刊：
2012 IEEE International Symposium on Information Theory Proceedings
影响因子：
--
作者：
Eric Price;David P. Woodruff
通讯作者：
David P. Woodruff