The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
Open accessAbstract
We study randomized variants of two classical algorithms: coordinate descent for systems of linear equations and iterated projections for systems of linear inequalities. Expanding on a recent randomized iterated projection algorithm of Strohmer and Vershynin (Strohmer, T., R. Vershynin. 2009. A randomized Kaczmarz algorithm with exponential convergence. J. Fourier Anal. Appl. 15 262–278) for systems of linear equations, we show that, under appropriate probability distributions, the linear rates of convergence (in expectation) can be bounded in terms of natural linear-algebraic condition numbers for the problems. We relate these condition measures to distances to ill-posedness and discuss generalizations to convex systems under metric regularity assumptions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
PE, & Billingsley, P. (1996) · Journal of the American Statistical Association · doi:10.2307/2291440 · Cited by 6,481
Rockafellar, R. T., & Wets, R. J. B. (1998) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-642-02431-3 · Cited by 4,086
The Approximation of One Matrix by Another of Lower Rank
Eckart, C., & Young, G. (1936) · Psychometrika · doi:10.1007/bf02288367 · Cited by 3,800
On Projection Algorithms for Solving Convex Feasibility Problems
Bauschke, H. H., & Borwein, J. M. (1996) · SIAM Review · doi:10.1137/s0036144593251710 · Cited by 1,654
Chaghaghi, F. S., & Billingsley, P. (1986) · The Statistician · doi:10.2307/2987970 · Cited by 1,217
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
A Randomized Kaczmarz Algorithm with Exponential Convergence
Strohmer, T., & Vershynin, R. (2009) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9030-4 · Cited by 903
The method of projections for finding the common point of convex sets
Gubin, L. G., Polyak, B. T., & Raik, E. V. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90113-9 · Cited by 828
Bradley, R. C., & Billingsley, P. (1987) · Journal of the American Statistical Association · doi:10.2307/2288811 · Cited by 774
On the convergence of the coordinate descent method for convex differentiable minimization
Luo, Z. Q., & Tseng, P. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00939948 · Cited by 502
Error bounds in mathematical programming
Pang, J.-S. (1997) · Mathematical Programming · doi:10.1007/bf02614322 · Cited by 441
Error bounds and convergence analysis of feasible descent methods: a general approach
Luo, Z.-Q., & Tseng, P. (1993) · Annals of Operations Research · doi:10.1007/bf02096261 · Cited by 420
On condition numbers and the distance to the nearest ill-posed problem
Demmel, J. W. (1987) · Numerische Mathematik · doi:10.1007/bf01400115 · Cited by 302
Linear programming, complexity theory and elementary functional analysis
Renegar, J. (1995) · Mathematical Programming · doi:10.1007/bf01585941 · Cited by 229
The probability that a numerical analysis problem is difficult
Demmel, J. W. (1988) · Mathematics of Computation · doi:10.1090/s0025-5718-1988-0929546-7 · Cited by 221
Some perturbation theory for linear programming
Renegar, J. (1994) · Mathematical Programming · doi:10.1007/bf01581690 · Cited by 205
On linear convergence of iterative methods for the variational inequality problem
Tseng, P. (1995) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(94)00094-h · Cited by 195
On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
Luo, Z.-Q., & Tseng, P. (1992) · SIAM Journal on Control and Optimization · doi:10.1137/0330025 · Cited by 190
Incorporating Condition Measures into the Complexity Theory of Linear Programming
Renegar, J. (1995) · SIAM Journal on Optimization · doi:10.1137/0805026 · Cited by 172
On the Convergence of the LMS Algorithm with Adaptive Learning Rate for Linear Feedforward Networks
Luo, Z.-Q. T. (1991) · Neural Computation · doi:10.1162/neco.1991.3.2.226 · Cited by 161
On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
Luo, Z.-Q. T., & Tseng, P. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.4.846 · Cited by 74
Cited by
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., & Nocedal, J. (2018) · SIAM Review · doi:10.1137/16m1080173 · Cited by 3,128
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Richtárik, P., & Takáč, M. (2014) · Mathematical Programming · doi:10.1007/s10107-012-0614-z · Cited by 654
Parallel coordinate descent methods for big data optimization
Richtárik, P., & Takáč, M. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0901-6 · Cited by 396
Metadata
- Authors
- Leventhal, D., & Lewis, A. S.
- Venue
- Mathematics of Operations Research
- Published
- 2010-08
- Volume
- 35
- Issue
- 3
- Pages
- 641-654
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2167820643
- Cited by
- 349
- References
- 23
- FWCI
- 7.77
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.