论文标题
使用内部产品搜索数据结构加快稀疏性
Speeding Up Sparsification using Inner Product Search Data Structures
论文作者
论文摘要
我们提出了一个一般框架，该框架利用不同的有效数据结构来改善涉及迭代过程的各种稀疏问题。我们还为不同的迭代过程提供了洞察力和表征，并回答何时应该在哪种类型的问题中使用哪些数据结构。对于以下问题，我们获得了改善的运行时间。 *用于构建线性尺寸的光谱弹药仪（Batson，Spielman和Srivastava，2012年），所有现有的确定性算法都需要$ω（d^4）$时间。在这项工作中，我们提供了第一种确定性算法，它破坏了以$ O（d^{ω+1}）$时间运行的障碍，其中$ω$是矩阵乘法的指数。 *对于单方面的Kadison-Singer型差异问题，我们为小型和大量迭代提供了快速的算法。 *对于实验设计问题，我们加快了一个键交换过程。 我们作品的核心是设计各种具有有效初始化，查询和更新时间的不同内部产品搜索数据结构，与降低尺寸的降低和适应性对手相兼容。
We present a general framework that utilizes different efficient data structures to improve various sparsification problems involving an iterative process. We also provide insights and characterization for different iterative process, and answer that when should we use which data structures in what type of problem. We obtain improved running time for the following problems. * For constructing linear-sized spectral sparsifier (Batson, Spielman and Srivastava, 2012), all the existing deterministic algorithms require $Ω(d^4)$ time. In this work, we provide the first deterministic algorithm that breaks that barrier which runs in $O(d^{ω+1})$ time, where $ω$ is the exponent of matrix multiplication. * For one-sided Kadison-Singer-typed discrepancy problem, we give fast algorithms for both small and large number of iterations. * For experimental design problem, we speed up a key swapping process. In the heart of our work is the design of a variety of different inner product search data structures that have efficient initialization, query and update time, compatible to dimensionality reduction and robust against adaptive adversary.
