Fetching the paper…
Reading the bibliography…
We give improved algorithms for the $\ell_{p}$-regression problem, $\min_{x} \|x\|_{p}$ such that $A x=b,$ for all $p \in (1,2) \cup (2,\infty).$ Our algorithms obtain a high accuracy solution in $\tilde{O}_{p}(m^{\frac{|p-2|}{2p + |p-2|}}) \le \tilde{O}_{p}(m^{\frac{1}{3}})$ iterations, where each iteration requires solving an $m \times m$ linear system, $m$ being the dimension of the ambient space.
“Speeding-up linear programming using fast matrix multiplication”
P.. Vaidya · 1989
Earlier work this paper cites.
“Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners.” Unpublished manuscript UIUC 1990. A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, October 1991, Minneapolis., 1990
Pravin. Vaidya · 1990
Earlier work this paper cites.
“Iterative Solution Methods”
Owe Axelsson · 1994
Earlier work this paper cites.
“Interior-Point Polynomial Algorithms in Convex Programming”
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
“Iterative methods for optimization”
Carl Kelley · 1999
Earlier work this paper cites.
“Multigrid methods nonlinear problems: an overview”
Van Henson · 2003
Earlier work this paper cites.
“Iterative Methods for Sparse Linear Systems” Available at http://www-users.cs.umn.edu/~saad/toc.pdf
Y. Saad · 2003
Earlier work this paper cites.
“Jacobian-free Newton–Krylov methods: a survey of approaches and applications”
Dana Knoll and David Keyes · 2004
Earlier work this paper cites.
“Nonlinear Equations”
Jorge Nocedal and Stephen Wright · 2006
Earlier work this paper cites.
Samuel. Daitch and Daniel. Spielman · 2008
Earlier work this paper cites.
“The Laplacian Paradigm: Emerging Algorithms for Massive Graphs”
Shang-Hua Teng · 2010
Earlier work this paper cites.
Paul Christiano et al · 2011
Earlier work this paper cites.
“A Nearly-m log n Time Solver for SDD Linear Systems” Available at http://arxiv.org/abs/1102.4842
Ioannis Koutis, Gary. Miller and Richard Peng · 2011
Earlier work this paper cites.
Aleksander Madry, Private Communication, 2011
2011
Earlier work this paper cites.
“The Multiplicative Weights Update Method: a Meta-Algorithm and Applications.”
Sanjeev Arora, Elad Hazan and Satyen Kale · 2012
Earlier work this paper cites.
Jonathan. Kelner, Gary. Miller and Richard Peng · 2012
Earlier work this paper cites.
“Multiplying Matrices Faster Than Coppersmith-winograd”
Virginia Williams · 2012
Earlier work this paper cites.
“Runtime guarantees for regression problems” Available at http://arxiv.org/abs/1110.1358
Hui Chin, Aleksander Madry, Gary. Miller and Richard Peng · 2013
Cited alongside, same era.
Manoj Gupta and Richard Peng · 2013
Cited alongside, same era.
“A simple, combinatorial algorithm for solving sdd systems in nearly-linear time”
J.. Kelner, L. Orecchia, A. Sidford and Z.. Zhu · 2013
Cited alongside, same era.
“A new approach to computing maximum flows using electrical flows”
Y.. Lee, S. Rao and N. Srivastava · 2013
Cited alongside, same era.
“Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back”
A. Madry · 2013
Cited alongside, same era.
Yin Lee and Aaron Sidford · 2015
Later among the works it cites.
Yin Lee, Aaron Sidford and Sam-wai Wong · 2015
Later among the works it cites.
“Equivalence of Linear Programming and Basis Pursuit”
Andreas Tillmann · 2015
Later among the works it cites.
“On Fully Dynamic Graph Sparsifiers” Available at: http://arxiv.org/abs/1604.02094
Ittai Abraham et al · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Jonah Sherman · 2013
Cited alongside, same era.
“Computational aspects of compressed sensing”
Andreas Tillmann · 2013
Cited alongside, same era.
“Solving SDD Linear Systems in Nearly Mlog1/2N Time”
Michael. Cohen et al · 2014
Cited alongside, same era.
Jonathan. Kelner, Yin Lee, Lorenzo Orecchia and Aaron Sidford · 2014
Cited alongside, same era.
“Approaching Optimality for Solving SDD Linear Systems” Available at http://arxiv.org/abs/1003.2958
I. Koutis, G. Miller and R. Peng · 2014
Cited alongside, same era.
“Powers of tensors and fast matrix multiplication” Available at: https://arxiv.org/abs/1401.7714
François Le · 2014
Cited alongside, same era.
“An Efficient Parallel Solver for SDD Linear Systems” Available at http://arxiv.org/abs/1311.3286
Richard Peng and Daniel. Spielman · 2014
Cited alongside, same era.
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
Rasmus Kyng et al · 2016
Later among the works it cites.
Aleksander Madry · 2016
Later among the works it cites.
“Much Faster Algorithms for Matrix Scaling” Available at: https://arxiv.org/abs/1704.02315
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael de Oliveira and Avi Wigderson · 2017
Later among the works it cites.
Michael. Cohen, Aleksander Madry, Dimitris Tsipras and Adrian Vladu · 2017
Later among the works it cites.
“Uniform Sampling and Inverse Maintenance” Talk at Michael Cohen Memorial Symposium, Available at: https://simons.berkeley.edu/talks/welcome-and-birds-eye-view-michaels-work, 2017
Yin Lee · 2017
Later among the works it cites.
“Area-convexity, l
Jonah Sherman · 2017
Later among the works it cites.
Jonah Sherman · 2017
Later among the works it cites.
“Michael Cohen and Oblivious Routing” Talk at Michael Cohen Memorial Symposium, Available at: https://simons.berkeley.edu/talks/tba-4, 2017
Aaron Sidford · 2017
Later among the works it cites.
“An Homotopy Method for Lp Regression Provably Beyond Self-concordance and in Input-sparsity Time”
Sébastien Bubeck, Michael. Cohen, Yin Lee and Yuanzhi Li · 2018
Later among the works it cites.
“Fast minimization of structured convex quartics” https://arxiv.org/abs/1812.10349
Brian Bullins · 2018
Later among the works it cites.
Michael. Cohen, Yin Lee and Zhao Song · 2018
Later among the works it cites.