Fast Fourier Sparsity Testing
Fast Fourier Sparsity Testing
复制标题
快速傅立叶稀疏性测试
DOI：
10.1137/1.9781611976014.10
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhou, Samson
中科院分区：
文献类型：
--
作者：
Yaroslavtsev, Grigory;Zhou, Samson
一个函数是稀疏的，如果它至多有非零的傅立叶系数。受快速稀疏傅立叶变换应用的启发，我们研究了从给定函数到最接近稀疏函数的逼近问题的有效算法。虽然以前的作品（例如，Gopalanet al.SICOMP 2011）研究了汉明距离下远离稀疏的那些稀疏函数的稀疏函数的问题，据我们所知，没有先前的工作明确地集中在更一般的距离估计问题上，这对于有噪声的傅立叶谱特别有意义。考虑到对效率的关注，我们的主要结果是一个算法，解决了这个问题的查询复杂度（S）为常数的准确性和错误参数，这只是二次差于适用的下限。
A function iss-sparseif it has at mostsnon-zero Fourier coefficients. Motivated by applications to fast sparse Fourier transforms over , we study efficient algorithms for the problem of approximating theℓ2-distance from a given function to the closests-sparse function. While previous works (e.g., Gopalanet al.SICOMP 2011) study the problem of distinguishings-sparse functions from those that are far froms-sparse under Hamming distance, to the best of our knowledge no prior work has explicitly focused on the more general problem of distance estimation in theℓ2setting, which is particularly well-motivated for noisy Fourier spectra. Given the focus on efficiency, our main result is an algorithm that solves this problem with query complexity (s) for constant accuracy and error parameters, which is only quadratically worse than applicable lower bounds.
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP)
影响因子：
--
作者：
Karl Wimmer;Yuichi Yoshida
通讯作者：
Yuichi Yoshida
DOI：
--
发表时间：
2013
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Hamed Hatami;Shachar Lovett
通讯作者：
Shachar Lovett
测试已知和未知碱基的稀疏性
DOI：
--
发表时间：
2016
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
Siddharth Barman;Arnab Bhattacharyya;Suprovat Ghoshal
通讯作者：
Suprovat Ghoshal
随机性和非确定性
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
L. Levin
通讯作者：
L. Levin
影响因子：
1.4
作者：
Amir Shpilka;Avishay Tal;Ben lee Volk
通讯作者：
Ben lee Volk