Apr, 2015

傅里叶稀疏布尔函数的列表译码大小

PDF
TL;DR该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限，证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限，同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。
boolean hypercubefourier-sparseboolean functionslearningquery complexity
发现论文，激发创造
  • 在亚线性时间内在任何常数维度上使用近乎最优采样复杂度进行稀疏傅立叶变换

    该研究考虑了通过时间域采样来计算 $N$ 长度信号的 $k$- 稀疏傅里叶变换近似的问题，提出了一种基于随机化算法的解决方案。

    Apr, 2016

  • 傅立叶稀疏杠杆分数与近似核学习

    在近似理论中，限制 Fourier 稀疏函数的杠杆分数是纯数学兴趣的研究内容之一。本文扩展了先前对于均匀分布的不同研究结果，证明了 Guassian 和 Laplace 分布中 Fourier 稀疏函数的杠杆分数的上限，并且针对这一结果，提出了两种机器学习的应用：核近似算法和活跃学习。

    Jun, 2020

  • 一个稳健的 Khintchine 不等式，以及计算傅里叶分析和高维几何中最优常数的算法

    本文针对傅里叶分析与高维几何中的一些经典问题做出了两个贡献，一个是证明了线性阈值函数最小傅里叶质量向量的一个下界，另一个则构建了一个算法来准确估算 Tomaszewski 常数。

    Jul, 2012

  • 量子布尔函数

    本文介绍了量子布尔函数的研究，包括量子性质测试、寻找布尔函数的大傅里叶系数的 Goldreich-Levin 算法的量子版本和 Friedgut，Kalai 和 Naor 关于布尔函数傅里叶谱的一个定理的两个量子版本。为了得到其中的一个推广，我们证明了 Bonami、Gross 和 Beckner 的超协调不等式的量子扩展。

    Oct, 2008

  • 稀疏多项式学习和图形草图

    该论文提出了一个算法来精确重建具有少数非零实系数的多项式，该算法以 $n$ 和 $2s$ 的多项式时间运行，并成功地满足了唯一符号属性。此外，根据实验验证，该算法适用于从随机样本中学习两个重要的应用程序：稀疏多项式恢复和超图草图。

    Feb, 2014

  • 概率多项式和汉明最近邻

    本文提出了一种利用概率多项式计算对数域上任意对称布尔函数并控制误差的低阶多项式方案，借此算法可在超对数维度中在真正的亚二次时间内求解汉明距离，并且能够对内积最大的向量，有最近的 ell1 对和杰卡德系数最大的向量对进行计算。

    Jul, 2015

  • 频率向量上单变量几乎所有函数的流空间复杂度

    研究数据流近似算法中的函数近似问题，给出了一个条件，满足条件的函数可以进行有效的空间近似算法，解决了 Alon 等人 1996 年论文中的开放问题，并对几乎所有单变量函数进行了表征。

    Jan, 2016

  • 分布式功能监测的严格界限

    通过新的直接求和定理，我们解决了数据流模型中估计频率矩阵和其它问题时的基础问题，并通过改进算法显著提高了界限。

    Dec, 2011

  • 模型适应型傅里叶采样用于生成式压缩感知

    研究了当测量矩阵从一个酉矩阵中随机子采样时的生成式压缩感知，提出了一个改进的样本复杂度的模型适应采样策略，利用非均匀随机采样分布提出了新的理论恢复保证，并优化采样分布以最小化所需测量数目，并验证了 CelebA 数据集上的恢复实验的性能。

    Oct, 2023

  • 通过凸松弛：傅里叶和高斯测量的稀疏重建

    研究如何通过几个稀疏信号线性测量（与一些固定向量的内积）的结果精确重构出稀疏的信号，并考虑了两种测量方法：高斯测量和傅里叶测量。通过几何函数分析和 Banach 空间中的随机性证明了这两种方法的最佳测量数量。

    Feb, 2006