2022

Speeding Up Sparsification using Inner Product Search Data Structures

Song, Zhao, Xu, Zhaozhuo, Zhang, Lichen

Understand

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 $\Omega(d^4)$ time.

Built on

The stability of out-input matrices
Max A Woodbury · 1949
Earlier work this paper cites.
Inverting modified matrices
Max A Woodbury · 1950
Earlier work this paper cites.
Multidimensional binary search trees used for associative searching
Jon Louis Bentley · 1975
Earlier work this paper cites.
Universal classes of hash functions
J.Lawrence Carter and Mark N. Wegman · 1979
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
ε \varepsilon -nets and simplex range queries
David Haussler and Emo Welzl · 1987
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets
Pravin M Vaidya · 1989
Earlier work this paper cites.
Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Piotr Indyk · 2003
Earlier work this paper cites.
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni · 2004
Earlier work this paper cites.
A randomized polynomial-time simplex algorithm for linear programming
Jonathan A. Kelner and Daniel A. Spielman · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I. Daitch and Daniel A. Spielman · 2008
Earlier work this paper cites.
A sparse johnson: Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlos · 2010
Earlier work this paper cites.
A derandomized sparse johnson-lindenstrauss transform
Daniel M Kane and Jelani Nelson · 2010
Earlier work this paper cites.
Spectral Sparsification and Restricted Invertibility
Nikhil Srivastava · 2010
Earlier work this paper cites.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng · 2011
Earlier work this paper cites.
Fast Approximation Algorithms for Graph Partitioning using Spectral and Semidefinite-Programming Techniques
Lorenzo Orecchia · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
Daniel A Spielman and Shang-Hua Teng · 2011
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Earlier work this paper cites.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2012
Earlier work this paper cites.
The power of simple tabulation hashing
Mihai Pundefinedtraşcu and Mikkel Thorup · 2012
Earlier work this paper cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Earlier work this paper cites.

Similar

A matrix hyperbolic cosine algorithm and applications
Original
Anastasios Zouzias · 2012
Cited alongside, same era.
Near-optimal coresets for least-squares regression
Christos Boutsidis, Petros Drineas, and Malik Magdon-ismail · 2013
Cited alongside, same era.
A simple, combinatorial algorithm for solving sdd systems in nearly-linear time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Madry · 2013
Cited alongside, same era.
Compressed matrix multiplication
Rasmus Pagh · 2013
Cited alongside, same era.
The Kadison–Singer problem in discrepancy theory, ii
Original
Nik Weaver · 2013
Cited alongside, same era.
Subspace embeddings for the polynomial kernel
Haim Avron, Huy Nguyen, and David Woodruff · 2014
Cited alongside, same era.
Optimal cur matrix decompositions
Christos Boutsidis and David P. Woodruff · 2014
Cited alongside, same era.
Solving sdd linear systems in nearly m log 1 / 2 n m\log^{1/2}n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu · 2014
Cited alongside, same era.
Sparser johnson-lindenstrauss transforms
Daniel M Kane and Jelani Nelson · 2014
Cited alongside, same era.
Powers of tensors and fast matrix multiplication
François Le Gall · 2014
Cited alongside, same era.
Spectral sparsification and regret minimization beyond matrix multiplicative updates
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia · 2015
Cited alongside, same era.

Then

Simple analyses of the sparse johnson-lindenstrauss transform
Michael B Cohen, TS Jayram, and Jelani Nelson · 2018
Later among the works it cites.
On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity
Ryan Williams · 2018
Later among the works it cites.
An illuminating algorithm for the light bulb problem
Josh Alman · 2019
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B Cohen, Yin Tat Lee, and Zhao Song · 2019
Later among the works it cites.
Active regression via linear-sample sparsification
Xue Chen and Eric Price · 2019
Later among the works it cites.
An equivalence class for orthogonal vectors
Lijie Chen and Ryan Williams · 2019
Later among the works it cites.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Later among the works it cites.
Relative error tensor low rank approximation
Zhao Song, David P Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
Oblivious sketching of high-degree polynomial kernels
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh · 2020
Later among the works it cites.
Near-optimal discrete optimization for experimental design: A regret minimization approach
Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang · 2020
Later among the works it cites.
On adaptive distance estimation
Yeshwanth Cherapanamjeri and Jelani Nelson · 2020
Later among the works it cites.
An improved cutting plane method for convex optimization, convex-concave games, and its applications
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong · 2020
Later among the works it cites.
A spectral approach to network design, 2020
Lap Chi Lau and Hong Zhou · 2020
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Terminal embeddings in sublinear time
Yeshwanth Cherapanamjeri and Jelani Nelson · 2021
Later among the works it cites.
A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path
Sally Dong, Yin Tat Lee, and Guanghao Ye · 2021
Later among the works it cites.
Solving sdp faster: A robust ipm framework and efficient implementation, 2021
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2021
Later among the works it cites.
Faster dynamic matrix inverse for faster lps
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2021
Later among the works it cites.
Fast sketching of polynomial kernels of polynomial degree
Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang · 2021
Later among the works it cites.
Oblivious sketching-based central path method for solving linear programming problems
Zhao Song and Zheng Yu · 2021
Later among the works it cites.
Fast Algorithm for Solving Structured Convex Programs
Guanghao Ye · 2021
Later among the works it cites.
Uniform approximations for randomized hadamard transforms with applications
Original
Yeshwanth Cherapanamjeri and Jelani Nelson · 2022
Closest in time.
A faster interior-point method for sum-of-squares optimization, 2022
Shunhua Jiang, Bento Natura, and Omri Weinstein · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…