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

NIPSFeb, 2014

Sparse Polynomial Learning and Graph Sketching

Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G. Dimakis, Adam Klivans

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

Abstract

Let $f:\{-1,1\}^n$ be a polynomial with at most $s$ non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distribution on $\{-1,1\}^n$ that runs in time polynomial in $n$ and $2s$ and succeeds if the function satisfies the unique sign property: there is one output value which corresponds to a uni

polynomial reconstruction unique sign property sparse polynomials hypergraph sketching random examples

发现论文，激发创造

逼近奇偶性解释适合学习中的相关变量数量

通过对相关变量进行逼近，我们证明在存在随机分类噪声的情况下，估算奇偶函数中相关变量数目的困难程度与正确学习奇偶函数的难度相当；进一步，我们展示通过估算相关变量数目的算法可以在多项式时间内解决正确学习具有少于等于 n 个相关变量的奇偶函数的难题，同时解决了在随机分类噪声下学习奇偶函数的困难问题。

Jul, 2024

关于绘制二次形式的草图

本研究对矩阵进行草图，着重探讨了矩阵的不同类型和查询所需的精度。特别地，我们尤其关注了具有特殊特性的正半定矩阵和图拉普拉斯矩阵，为其设计了更优秀的草图，并探讨了草图的实际应用。

Nov, 2015

线性草图的高效对称范数回归

提供了高效的算法来解决超定的线性回归问题，其中损失函数是对称范数（在符号反转和坐标置换下不变的范数），当损失函数为 Orlicz 范数时，算法产生一个 (1+ε)- 近似解，在输入稀疏时间内改进了先前已知的算法。

Oct, 2019

Gaussian 随机场的非线性函数 L∞恢复：多项式样本复杂度上界

通过利用高斯随机场中真实函数的随机性，证明了一些难以置信的结果，为高斯随机场中随机真实函数的多项式样本复杂度提供了一个有界上限。聚焦于球面谐波上，利用 L_inf 和 L_2 比率控制证明 L_inf-L_2 问题的解决方案。

Apr, 2023

对异常数据鲁棒的回归的高效算法

本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。

Mar, 2018

使用乘法权重学习图形模型

给出一种用于学习 Markov 随机场（MRF）或无向图模型的简单的、乘性权重更新算法 ——Sparsitron 算法，特别适用于学习 t 阶 MRFs 结构，并具有近乎最优的样本复杂度和多项式的运行时间。同时，该算法还可以学习 Ising 模型上的参数，生成接近真实 MRF 的统计距离假设，并给出了学习稀疏广义线性模型（GLMs）的解决方案。

Jun, 2017

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

该研究论文证明了具有至多 k 非零傅里叶系数的函数在布尔超立方体上的上限，证明了学习 k-Fourier-sparse 布尔函数类所需的随机样本数量上限，同时也得出了傅里叶稀疏函数的布尔性测试的查询复杂性的上界。

Apr, 2015

近线性时间内样本最优密度估计

设计了一种新的快速算法，用于对分段多项式函数进行密度估计，该算法具有采样最优和近线性时间的估计能力，并且在实践中表现良好。

Jun, 2015

基于几何图的线性代数算法与难度

该研究探讨了在一类称为 K - 图的特殊完全图上实现有效光谱图论的可能性，包括矩阵乘法，谱稀疏化，以及拉普拉斯系统解决方案等问题，并以多种函数为例进行算法开发和难度对比，并发现对于某些函数，即使采用著名的快速多极方法（Fast multipole method），在维度上存在无法克服的指数限制。

Nov, 2020

稀疏字典的精确恢复

本文介绍了一个多项式时间算法 ER-SpUD 来恢复使用稀疏矩阵的稀疏字典，证明了只需 O（nlog n）个样本即足以唯一确定系数矩阵，模拟结果表明 ER-SpUD 的恢复率优于当前众多算法

Jun, 2012