Fetching the paper…
Reading the bibliography…
This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss-Seidel method and can be transformed to Kaczmarz method and projection onto convex sets (POCS).
“Functional operators. volume II, the geometry of orthogonal spaces,”
John Von Neumann, · 1933
Earlier work this paper cites.
“Angenäherte auflösung von systemen linearer gleichungen,”
Stefan Kaczmarz, · 1937
Earlier work this paper cites.
“On rings of operators. reduction theory,”
John Von Neumann, · 1949
Earlier work this paper cites.
“Iterative methods for solving partial difference equations of elliptic type,”
David Young, · 1954
Earlier work this paper cites.
“On best conditioned matrices,”
George E Forsythe and Ernst G Straus, · 1955
Earlier work this paper cites.
“The product of projection operators,”
Israel Halperin, · 1962
Earlier work this paper cites.
“On the effects of scaling of the peaceman-rachford method,”
Olof B Widlund, · 1971
Earlier work this paper cites.
Hassler Whitney, · 1972
Earlier work this paper cites.
“On search directions for minimization algorithms,”
Michael JD Powell, · 1973
Earlier work this paper cites.
“Practical and mathematical aspects of the problem of reconstructing objects from radiographs,”
Kennan T Smith, Donald C Solmon, and Sheldon L Wagner, · 1977
Earlier work this paper cites.
“Error bounds for the method of alternating projections,”
Selahattin Kayalar and Howard L Weinert, · 1988
Earlier work this paper cites.
“Eigenvalues and condition numbers of random matrices,”
Alan Edelman, · 1988
Earlier work this paper cites.
“On the convergence of the coordinate descent method for convex differentiable minimization,”
Z.-Q. Luo and P. Tseng, · 1992
Earlier work this paper cites.
“The method of alternating orthogonal projections,”
Frank Deutsch, · 1992
Earlier work this paper cites.
“Triangular truncation and finding the norm of a hadamard multiplier,”
James R Angelos, Carl C Cowen, and Sivaram K Narayan, · 1992
Earlier work this paper cites.
“On the convergence rate of sor: a worst case estimate,”
Peteer Oswald, · 1994
Earlier work this paper cites.
“The quadratic formula made hard: A less radical approach to solving equations,”
M Lawrence Glasser, · 1994
Earlier work this paper cites.
“A unified approach to statistical tomography using coordinate descent optimization,”
Charles A Bouman and Ken Sauer, · 1996
Earlier work this paper cites.
Iterative methods for solving linear systems
Anne Greenbaum, · 1997
Earlier work this paper cites.
Iterative methods for solving linear systems
Anne Greenbaum, · 1997
Earlier work this paper cites.
“The rate of convergence for the method of alternating projections, ii,”
Frank Deutsch and Hein Hundal, · 1997
Earlier work this paper cites.
“The method of cyclic projections for closed convex sets in hilbert space,”
Heinz H Bauschke, Jonathan M Borwein, and Adrian S Lewis, · 1997
Earlier work this paper cites.
Nonlinear Programming, 2nd ed
D. P. Bertsekas, · 1999
Earlier work this paper cites.
“On the convergence of the block nonlinear Gauss-Seidel method under convex constraints,”
L. Grippo and M. Sciandrone, · 2000
Earlier work this paper cites.
“Convergence of a block coordinate descent method for nondifferentiable minimization,”
P. Tseng, · 2001
Earlier work this paper cites.
“Cyclic coordinate descent: A robotics algorithm for protein loop closure,”
Adrian A Canutescu and Roland L Dunbrack, · 2003
Earlier work this paper cites.
“PRIMES is in P,”
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, · 2004
Cited alongside, same era.
“Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time,”
Daniel A Spielman and Shang-Hua Teng, · 2004
Cited alongside, same era.
“Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems,”
Daniel A Spielman and Shang-Hua Teng, · 2004
Cited alongside, same era.
“On the rate of convergence of the alternating projection method in finite dimensional spaces,”
A Galántai, · 2005
Cited alongside, same era.
“A dual coordinate descent method for large-scale linear SVM,”
Cho-Jui Hsieh, Kai-Wei Chang, Chih-Jen Lin, S Sathiya Keerthi, and Sellamanickam Sundararajan, · 2008
Cited alongside, same era.
“Tensor decompositions and applications,”
Tamara G Kolda and Brett W Bader, · 2009
Projectors and projection methods
Aurél Galántai, · 2013
Later among the works it cites.
“Cross-layer provision of future cellular networks: A wmmse-based approach,”
Hadi Baligh, Mingyi Hong, Wei-Cheng Liao, Zhi-Quan Luo, Meisam Razaviyayn, Maziar Sanjabi, and Ruoyu Sun, · 2014
Later among the works it cites.
“Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function,”
P. Richtárik and M. Takáč, · 2014
Later among the works it cites.
“Randomized dual coordinate ascent with arbitrary sampling,”
Zheng Qu, Peter Richtárik, and Tong Zhang, · 2014
Later among the works it cites.
Qihang Lin, Zhaosong Lu, and Lin Xiao, · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
“A randomized kaczmarz algorithm with exponential convergence,”
Thomas Strohmer and Roman Vershynin, · 2009
Cited alongside, same era.
“A fast iterative shrinkage-thresholding algorithm for linear inverse problems,”
A. Beck and M. Teboulle, · 2009
Cited alongside, same era.
“Regularization paths for generalized linear models via coordinate descent,”
Jerome Friedman, Trevor Hastie, and Rob Tibshirani, · 2010
Cited alongside, same era.
“Randomized methods for linear constraints: convergence rates and conditioning,”
Dennis Leventhal and Adrian S Lewis, · 2010
Cited alongside, same era.
“Libsvm: a library for support vector machines,”
Chih-Chung Chang and Chih-Jen Lin, · 2011
Cited alongside, same era.
“Parallel coordinate descent for l1-regularized loss minimization,”
Joseph K Bradley, Aapo Kyrola, Danny Bickson, and Carlos Guestrin, · 2011
Cited alongside, same era.
“A coordinate majorization descent algorithm for
Yi Yang and Hui Zou, · 2014
Later among the works it cites.
“On the convergence rate of multi-block ADMM,”
T. Lin, S. Ma, and S. Zhang, · 2014
Later among the works it cites.
“The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex,”
X. Cai, D. Han, and X. Yuan, · 2014
Later among the works it cites.
“Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems,”
Daniel A Spielman and Shang-Hua Teng, · 2014
Later among the works it cites.
“Approaching optimality for solving sdd linear systems,”
Ioannis Koutis, Gary L. Miller, and Richard Peng, · 2014
Later among the works it cites.
“Coordinate descent algorithms,”
Stephen J Wright, · 2015
Later among the works it cites.
“Guaranteed matrix completion via nonconvex factorization,”
Ruoyu Sun and Zhi-Quan Luo, · 2015
Later among the works it cites.
“On the complexity analysis of randomized block-coordinate descent methods,”
Zhaosong Lu and Lin Xiao, · 2015
Later among the works it cites.
“Stochastic primal-dual coordinate method for regularized empirical risk minimization,”
Yuchen Zhang and Lin Xiao, · 2015
Later among the works it cites.
“Accelerated, parallel, and proximal coordinate descent,”
Olivier Fercoq and Peter Richtárik, · 2015
Later among the works it cites.
“An asynchronous parallel stochastic coordinate descent algorithm,”
Ji Liu, Stephen J Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar, · 2015
Later among the works it cites.
“Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization,”
Andrei Patrascu and Ion Necoara, · 2015
Later among the works it cites.
“Passcode: Parallel asynchronous stochastic dual co-ordinate descent,”
Cho-Jui Hsieh, Hsiang-Fu Yu, and Inderjit S Dhillon, · 2015
Later among the works it cites.
“Nearly-linear time positive lp solver with faster convergence rate,”
Zeyuan Allen-Zhu and Lorenzo Orecchia, · 2015
Later among the works it cites.
“On the expected convergence of randomly permuted ADMM,”
Ruoyu Sun, Zhi-Quan Luo, and Yinyu Ye, · 2015
Later among the works it cites.
“Improved iteration complexity bounds of cyclic block coordinate descent for convex problems,”
Ruoyu Sun and Mingyi Hong, · 2015
Later among the works it cites.
“On the convergence of alternating minimization with applications to iteratively reweighted least squares and decomposition schemes,”
A. Beck, · 2015
Later among the works it cites.
“Random permutations fix a worst case for cyclic coordinate descent,”
Ching-Pei Lee and Stephen J Wright, · 2016
Closest in time.
“The direct extension of admm for multi-block convex minimization problems is not necessarily convergent,”
Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan, · 2016
Closest in time.
Lin Xiao, Adams Wei Yu, Qihang Lin, and Weizhu Chen, · 2017
Closest in time.
“Randomized projection methods for convex feasibility problems: conditioning and convergence rates,”
Ion Necoara, Peter Richtarik, and Andrei Patrascu, · 2018
Closest in time.