sum-of-squares method | BriefGPT

关键词sum-of-squares method

搜索结果 - 8

列表可解线性回归
该研究为第一篇在 list-decodable 设置中，给出了一种鲁棒的回归问题的多项式时间算法，当假设内点分布是 certifiably anti-concentrated 分布时，该算法能够成功地给出一个接近于真解的目标函数。
PDF5 years ago
MM对异常数据鲁棒的回归的高效算法
本文首次给出了一个多项式时间算法，用于在示例和标签中对抗性堕落下执行线性或多项式回归，并基于 SoS 方法提出了一种自然的凸松弛方法来解决非凸优化问题。
PDF6 years ago
具有平方和形式的张量精确完成
本研究使用最优的多项式算法，仅依靠少量随机观察数据完成张量解析，并将通过球上的正交全局极值证明的事实证明到可以在和方法证明系统内进行。
PDF7 years ago
多项式时间的带有平方和项的张量分解
本文基于平方和方法给出了用于张量分解的新算法，结果改进了多个问题的运行时间，包括对超完备三元组分解和具有常数相对稀疏度的超完备字典的学习等问题的算法，同时首次在平滑分析模型中给出了超完备四元组分解的稳健性分析。而此分析的关键因素在于在由平方
PDF8 years ago
基于平方和证明的快速谱算法：张量分解和种植稀疏向量
研究了两个基于机器学习应用中的问题：在随机线性子空间中恢复种植稀疏向量的问题以及分解随机低秩超完备三阶张量的问题。通过分析和受到二次和方法的启发，提出了新的算法，其可以在更快的时间内实现与二次和方案相似的保证
PDF9 years ago
基于平方和证明的张量主成分分析
研究了一个针对张量主成分分析问题的统计模型，通过基于四次幂和松弛的舍入算法，证明了随机噪声张量的种植向量可以在高概率下被回收，还证明了四次幂和松弛在一定程度下是不起作用的，研究并利用了额外的问题结构来求解我们的平方和松弛。
PDF9 years ago
平方和证明及其应用于最优算法问题的探索
该研究讨论了最近发现的唯一游戏猜想与和平方方法之间的联系，并探讨了和平方方法在解决许多计算问题时提供新保证的潜力，同时还可能驳回 UGC。
PDF10 years ago
舍入平方和松弛问题
通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多
PDF11 years ago