- 核范数中的快速谱密度估计与稀疏化
利用一种随机算法和核稀疏化的方法,该研究提出了一种新的图谱估计方法,可在线性时间和多项式查询复杂度下,准确估计归一化邻接矩阵的谱密度。这一方法在复杂度和准确性方面均具有优势,且创造性地解决了图的稀疏化和添加谱稀疏化的相关问题。
- 通过多阶段采样技术(MUST)增强隐私、效用和计算效率的平衡
应用一种随机算法对数据集的子集进行处理,而不是整个数据集,是提高发布信息隐私保护性的一种常见方法。我们提出了一种名为 MUltistage Sampling Technique(MUST)的子采样方法类别,用于差分隐私(DP)上的隐私增强( - 高维空间中更快的最大内积搜索
本文提出了一种名为 BanditMIPS 的随机算法,解决了在高纬度情况下复杂度至少为 O (根号 d) 的 MIPS 任务。此算法通过自适应子采样和多臂老虎机策略来估计每个原子的内积,并在理论和实验中都得到了证明。
- AAAI一种改进的在线最小和集合覆盖算法
本文探讨基于在线偏好聚合的基础模型,在评估算法的竞争力方面提出了一种新算法,能够实现更强的动态最优解,算法的竞争比由 $O (r^2)$ 到达。
- 随机序列模型下背包和 GAP 的改进在线算法
本研究中,我们研究了在随机顺序模型下,针对背包问题和广义分配问题的在线算法,提出了一种基于两个优化算法的新型算法,竞争比最高达到 1/6.65 和 1/6.99。
- Hutch++:最优随机迹估计
研究矩阵的迹估计问题,提出一种通过矩阵向量乘法计算正半定矩阵的迹的新的随机算法 Hutch ++,其利用低秩近似步骤降低估计值的方差,证明其复杂度在所有矩阵向量查询算法中是最优的。
- 解决最优度量失真猜想
研究度量扭曲问题:有两个点集 V 和 C,它们在相同的度量空间中,我们的目标是选择 C 中一点,其到 V 点的总距离尽可能小。我们提出了使用排名作为输入的算法,并提供了它们的扭曲界限。
- 在 $O (m\log^2 n)$ 时间复杂度内求最小割
该研究提供了一种随机算法,用于在具有 n 个顶点的 m 个边的无向带权图 G 中高概率地找到最小割,并通过确定性算法在 O (m log n) 时间内找到了 G 的最小割。
- CVPRSDRSAC: 基于半正定随机化方法的点云无对应项鲁棒配准
本文提出了一种无需对应的鲁棒点云配准随机算法,并将其视为图匹配的特例,通过使用有效的半定松弛和新颖的采样机制,在采样大小大于最小值的前提下,实现了对野值的快速拒绝,从而获得高质量的假设。通过实验,证明了该方法的有效性。
- 带期限的最大权重在线匹配
研究匹配到一个时间市场上的代理人的问题,该论文提出了不同的算法来解决顺序不同的场景,并在独立抽样的时间场景中实现 1/8-competitive 算法,对于随机顺序情况下提出了一个每 (d+1) 阶段计算最大加权匹配的 batching 算 - 图形摘要的可扩展近似算法
本文提出了一种有效的随机算法来计算图形摘要,旨在最小化重构误差,使用加权采样方案来合并顶点,提供算法运行时间的分析上限和得分计算的近似保证,并在几个真实世界图形上测试了算法以证明摘要的质量和与现有算法的比较,并使用摘要来回答有关原始图形的几 - 基于多尺度熵正则化的 k 服务器问题
本文提出了一种基于多尺度熵的在线镜像下降算法,可以在关于 $k$ 的对数平方的竞争比下解决基于分层分离树的 $k$- 服务器问题,并在动态和静态情况下获得较优解。
- 随机张量列奇异值分解
该研究针对层次张量表示,研究了随机矩阵分解方法在高阶张量中的推广,并提出分析了一种用于计算张量拓扑结构的随机算法。
- 可伸缩和强健的集合相似性连接
本文提出了一种新的集合相似性连接的随机算法,可以实现任何期望的召回率,这种方法在数据不具有罕见令牌结构时也具有鲁棒性,本文的方法在很大程度上提高了现有方法的效率。
- 一种用于低秩近似的快速频率方向算法
本文提出了一种使用随机化算法(稀疏子空间嵌入)以降低计算成本的快速频繁方向算法,它在低秩逼近问题中工作得很好并且利用了频繁方向的自然块结构和稀疏子空间嵌入向每个块发送更多信息,该算法有效且高效,通过在合成和真实数据集上的实验结果以及在网络分 - IJCAI大规模高维数据的单次 PCA
本文提出了一种基于单次随机算法的主成分分析法,适用于处理极大和高维度的数据,并且具有小的计算误差和低的存储成本。
- 大规模核机器的随机聚类 Nystrom
通过基于随机化 K-means 算法的优化 Nystrom 方法,本文提出了一种能适用于大规模数据集的低秩近似计算算法,使得在高维数据集上能够以较小的准确性损失实现更高的计算效率。
- 在线自由处理子模最大化:随机化对分割矩阵 0.25 优势
本文研究了带有破坏性(free disposal)的 matroid 约束下的在线次模最大化问题。针对 k-uniform matroids,本文提出了一个与以往最优算法竞争比例更高的确定性算法;同时,本文也探讨了在 partition m - 在亚线性时间内在任何常数维度上使用近乎最优采样复杂度进行稀疏傅立叶变换
该研究考虑了通过时间域采样来计算 $N$ 长度信号的 $k$- 稀疏傅里叶变换近似的问题,提出了一种基于随机化算法的解决方案。
- ICML基于动态连续索引的快速 K 最近邻搜索
提出一种新的无需数据空间分割的随机化算法来避免由于数据维度过高而导致的数据检索问题,并通过理论分析和实验结果来证明这种算法在数据近似性、速度和空间效率等方面优于传统的局部敏感哈希算法(LSH)