Apr, 2020
非自适应自适应抽样的转门流
Non-Adaptive Adaptive Sampling on Turnstile Streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, Samson Zhou
TL;DR该研究提出了一种适应性采样算法,能够在单处理器计算中对数据进行概括,同时提供了一种在旋门流数据上执行的采样算法,同时进行了容器选择、子空间逼近、投影聚类和体积最大化等各种类型的数据概括算法。
Abstract
adaptive sampling is a useful algorithmic tool for data summarization
problems in the classical centralized setting, where the entire dataset is
available to the single processor performing the computation.
发现论文,激发创造
稀疏字典学习的素描算法:PTAS 和转轴流式处理
通过新技术扩展基于草图的方法,开展了稀疏字典学习和欧氏 k-means 聚类问题的研究,在快速算法方面获得了对 $k$-means 聚类问题的新方法,并推广到稀疏字典学习问题。在流算法方面,得到了字典学习和 $k$-means 聚类的新上界和下界。
Oct, 2023
自适应随机子空间中的高维优化
提出了一种新的高维随机优化方法,将坐标下降法推广到随机子空间,证明了使用自适应采样策略的随机子空间可以显著优于最近文献中常见的盲目采样方法,可以通过相关随机矩阵集合有效生成自适应子空间;在具有不同谱衰减的数据矩阵上验证了该方法在机器学习问题中的速度优势,包括逻辑回归、带随机卷积层的核分类和具有修正线性单元的浅神经网络。
Jun, 2019
双重体积采样的多项式时间算法
通过发展精确(随机)多项式时间抽样算法,使用实稳定多项式理论研究双重体积抽样的概率分布,证明了它满足 “强瑞利” 属性,并实现了快速混合马尔可夫链采样器,该采样器与常见的实验设计方法相关,是更多实践者的首选。
Mar, 2017
在线和滑动窗口模型下的近似最优线性代数
本研究讨论了滑动窗口模型下的数值线性代数问题,提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题,同时通过与在线模型的联系,提出了正文算法,并应用于列 / 行选择、主成分分析等问题。此外,研究还提出了一种新的框架,包括了融合和减少范式和在线核的概念,并且通过行到达在线模型给出了在线核,最终得到了差不多最优空间的定向算法。
May, 2018
行 / 列子集选择的高效体积抽样
通过选择相应的行,并按照其自身以及原点形成的单形的体积进行概率比例采样,给出了有效的算法。这些算法解决了 Kannan 和 Vempala 的有关谱算法的专著中的一个问题,并且还对低秩矩阵逼近提供了几个有趣的结果。
Apr, 2010