Sampled limited memory methods for massive linear inverse problems. (English) Zbl 07371362
Summary: In many modern imaging applications the desire to reconstruct high resolution images, coupled with the abundance of data from acquisition using ultra-fast detectors, have led to new challenges in image reconstruction. A main challenge is that the resulting linear inverse problems are massive. The size of the forward model matrix exceeds the storage capabilities of computer memory, or the observational dataset is enormous and not available all at once. Row-action methods that iterate over samples of rows can be used to approximate the solution while avoiding memory and data availability constraints. However, their overall convergence can be slow. In this paper, we introduce a sampled limited memory row-action method for linear least squares problems, where an approximation of the global curvature of the underlying least squares problem is used to speed up the initial convergence and to improve the accuracy of iterates. We show that this limited memory method is a generalization of the damped block Kaczmarz method, and we prove linear convergence of the expectation of the iterates and of the error norm up to a convergence horizon. Numerical experiments demonstrate the benefits of these sampled limited memory row-action methods for massive 2D and 3D inverse problems in tomography applications.
MSC:
| 65Fxx | Numerical linear algebra |
| 90Cxx | Mathematical programming |
| 68Wxx | Algorithms in computer science |
| 65Kxx | Numerical methods for mathematical programming, optimization and variational techniques |
| 65Yxx | Computer aspects of numerical algorithms |
Keywords:
least squares problems; row-action methods; Kaczmarz methods; randomized methods; tomography; streaming dataReferences:
| [1] | Parkinson D Y, Pelt D M, Perciano T, Ushizima D, Krishnan H, Barnard H S, MacDowell A A and Sethian J 2017 Machine Learning for Micro-Tomography((Developments in x-ray tomography XI, volume 10391)) pp 103910J · doi:10.1117/12.2274731 |
| [2] | Parkinson D Y, Pacold J I, Gross M, McDougall T D, Jones C, Bows J, Hamilton I, Smiles D E, De Santis S, Ratti A et al 2018 Achieving Fast High-Resolution 3D Imaging by Combining Synchrotron X-ray Micro CT, Advanced Algorithms, and High Performance Data Management(Image Sensing Technologies: Materials, Devices, Systems, and Applications V106560S, vol 10656) https://doi.org/10.1117.12.2307272 · doi:10.1117/12.2307272 |
| [3] | Paige C C and Saunders M A 1982 LSQR: an algorithm for sparse linear equations and sparse least squares ACM Trans. Math. Softw.8 43-71 · Zbl 0478.65016 · doi:10.1145/355984.355989 |
| [4] | Avron H, Maymounkov P and Blendenpik S T 2010 Supercharging LAPACK’s least-squares solver SIAM J. Sci. Comput.32 1217-36 · Zbl 1213.65069 · doi:10.1137/090767911 |
| [5] | Halko N, Martinsson P G and Tropp J A 2011 Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions SIAM Rev.53 217-88 · Zbl 1269.65043 · doi:10.1137/090771806 |
| [6] | Bottou L and Cun Y L 2004 Large scale online learning Advances in Neural Information Processing Systems pp 217-24 |
| [7] | Hand D J, Blunt G, Kelly M G, Adams N M et al 2000 Data mining for fun and profit Stat. Sci.15 111-31 · doi:10.1214/ss/1009212753 |
| [8] | Rajaraman A and Ullman J D 2011 Mining of Massive Datasets (New York: Cambridge University Press) · doi:10.1017/CBO9781139058452 |
| [9] | Zeng X Q and Li G Z 2014 Incremental partial least squares analysis of big streaming data Pattern Recognit.47 3726-35 · doi:10.1016/j.patcog.2014.05.022 |
| [10] | Boumal N, Bendory T, Lederman R R and Singer A 2018 Heterogeneous multi reference alignment: a single pass approach 52nd Annual Conf. on Information Sciences and Systems (CISS) pp 1-6 · doi:10.1109/CISS.2018.8362313 |
| [11] | Levin E, Bendory T, Boumal N, Kileel J and Singer A 2018 3D ab initio modeling in cryo-EM by autocorrelation analysis IEEE 15th Int. Symp. on Biomedical Imaging (ISBI 2018) pp 1569-73 · doi:10.1109/ISBI.2018.8363873 |
| [12] | Chung J, Haber E and Nagy J 2006 Numerical methods for coupled super-resolution Inverse Problems22 1261 · Zbl 1147.93302 · doi:10.1088/0266-5611/22/4/009 |
| [13] | Slagel J T, Chung J, Chung M, Kozak D and Tenorio L 2019 Sampled Tikhonov regularization for large linear inverse problems Inverse Problems35 114008 · Zbl 1434.65083 · doi:10.1088/1361-6420/ab2787 |
| [14] | Censor Y, Herman G T and Jiang M 2009 A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin J. Fourier Anal. Appl.15 431-6 · Zbl 1177.68252 · doi:10.1007/s00041-009-9077-x |
| [15] | Eldar Y C and Needell D 2011 Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma Numer. Algorithms58 163-77 · Zbl 1230.65051 · doi:10.1007/s11075-011-9451-z |
| [16] | Gower R M and Richtárik P 2015 Randomized iterative methods for linear systems SIAM J. Matrix Anal. Appl.36 1660-90 · Zbl 1342.65110 · doi:10.1137/15m1025487 |
| [17] | Needell D 2010 Randomized Kaczmarz solver for noisy linear systems BIT Numer. Math.50 395-403 · Zbl 1195.65038 · doi:10.1007/s10543-010-0265-5 |
| [18] | Needell D, Srebro N and Ward R 2016 Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm Math. Program.155 549-73 · Zbl 1333.65070 · doi:10.1007/s10107-015-0864-7 |
| [19] | Needell D and Tropp J A 2014 Paved with good intentions: analysis of a randomized block Kaczmarz method Linear Algebr. Appl.441 199-221 · Zbl 1282.65042 · doi:10.1016/j.laa.2012.12.022 |
| [20] | Strohmer T and Vershynin R 2009 Comments on the randomized Kaczmarz method J. Fourier Anal. Appl.15 437-40 · Zbl 1177.68253 · doi:10.1007/s00041-009-9082-0 |
| [21] | Strohmer T and Vershynin R 2009 A randomized Kaczmarz algorithm with exponential convergence J. Fourier Anal. Appl.15 262-78 · Zbl 1169.68052 · doi:10.1007/s00041-008-9030-4 |
| [22] | Andersen M S and Hansen P C 2014 Generalized row-action methods for tomographic imaging Numer. Algorithms67 121-44 · Zbl 1302.65285 · doi:10.1007/s11075-013-9778-8 |
| [23] | Elfving T, Hansen P C and Nikazad T 2014 Semi-convergence properties of Kaczmarz’s method Inverse Problems30 055007 · Zbl 1296.65054 · doi:10.1088/0266-5611/30/5/055007 |
| [24] | Gordon R, Bender R and Herman G T 1970 Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography J. Theor. Biol.29 471-81 · doi:10.1016/0022-5193(70)90109-8 |
| [25] | Natterer F 2001 The Mathematics of Computerized Tomography (Philadelphia, PA: SIAM) · Zbl 0973.92020 · doi:10.1137/1.9780898719284 |
| [26] | Censor Y, Eggermont P B and Gordon D 1983 Strong underrelaxation in Kaczmarz’s method for inconsistent systems Numer. Math.41 83-92 · Zbl 0489.65023 · doi:10.1007/bf01396307 |
| [27] | Hanke M and Niethammer W 1990 On the acceleration of Kaczmarz’s method for inconsistent linear systems Linear Algebr. Appl.130 83-98 · Zbl 0708.65033 · doi:10.1016/0024-3795(90)90207-s |
| [28] | Herman G T 2009 Fundamentals of Computerized Tomography: Image Reconstruction from Projections (Berlin: Springer) · Zbl 1280.92002 · doi:10.1007/978-1-84628-723-7 |
| [29] | Elfving T 1980 Block-iterative methods for consistent and inconsistent linear equations Numer. Math.35 1-12 · Zbl 0416.65031 · doi:10.1007/bf01396365 |
| [30] | Jiao Y, Jin B and Lu X 2017 Preasymptotic convergence of randomized Kaczmarz method Inverse Problems33 125012 · Zbl 1382.65087 · doi:10.1088/1361-6420/aa8e82 |
| [31] | Censor Y and Zenios S A 1997 Parallel Optimization: Theory, Algorithms, and Applications (Oxford: Oxford University Press) · Zbl 0945.90064 |
| [32] | Escalante R and Raydan M 2011 Alternating Projection Methods (Philadelphia, PA: SIAM) · Zbl 1275.65031 · doi:10.1137/9781611971941 |
| [33] | Chung J, Chung M, Slagel J T and Tenorio L 2017 Stochastic Newton and quasi-Newton methods for large linear least-squares problems (arXiv:1702.07367) |
| [34] | Shapiro A, Dentcheva D and Ruszczyński A 2009 Lectures on Stochastic Programming: Modeling and Theory (Philadelphia, PA: SIAM) · Zbl 1183.90005 · doi:10.1137/1.9780898718751 |
| [35] | Bottou L 1998 Online learning and stochastic approximations Online Learning in Neural Networks (Cambridge: Cambridge University Press) pp 9-42 ch 2 · Zbl 0968.68127 |
| [36] | Schaul T, Zhang S and Cun Y L 2013 No more pesky learning rates Int. Conf. on Machine Learning pp 343-51 |
| [37] | Zeiler M D 2012 ADADELTA: an adaptive learning rate method (arXiv:1212.5701) |
| [38] | Gower R M and Richtárik P 2017 Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms SIAM J. Matrix Anal. Appl.38 1380-409 · Zbl 1379.65016 · doi:10.1137/16m1062053 |
| [39] | Byrd R H, Hansen S L, Nocedal J and Singer Y 2016 A stochastic quasi-Newton method for large-scale optimization SIAM J. Optim.26 1008-31 · Zbl 1382.65166 · doi:10.1137/140954362 |
| [40] | Needell D, Zhao R and Zouzias A 2015 Randomized block Kaczmarz method with projection for solving least squares Linear Algebr. Appl.484 322-43 · Zbl 1330.65056 · doi:10.1016/j.laa.2015.06.027 |
| [41] | Feichtinger H G, Cenker C, Mayer M, Steier H and Strohmer T 1992 New variants of the POCS method using affine subspaces of finite co-dimension with applications to irregular sampling Visual Communications and Image Processing’92 vol 1818 pp 299-311 · doi:10.1117/12.131447 |
| [42] | Herman G T and Meyer L B 1993 Algebraic reconstruction techniques can be made computationally efficient (positron emission tomography application) IEEE Trans. Med. Imaging12 600-9 · doi:10.1109/42.241889 |
| [43] | Whitney T M and Meany R K 1967 Two algorithms related to the method of steepest descent SIAM J. Numer. Anal.4 109-18 · Zbl 0173.17806 · doi:10.1137/0704010 |
| [44] | Tanabe K 1971 Projection method for solving a singular system of linear equations and its applications Numer. Math.17 203-14 · Zbl 0228.65032 · doi:10.1007/bf01436376 |
| [45] | Zouzias A and Freris N M 2013 Randomized extended Kaczmarz for solving least squares SIAM J. Matrix Anal. Appl.34 773-93 · Zbl 1273.65053 · doi:10.1137/120889897 |
| [46] | Kaczmarz S 1937 Angenäherte Auflösung von Systemen linearer Gleichungen Bulletin International de l’Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques35 335-57 · JFM 63.0524.02 |
| [47] | Herman G T, Lent A and Lutz P H 1978 Relaxation methods for image reconstruction Commun. ACM21 152-8 · Zbl 0367.68065 · doi:10.1145/359340.359351 |
| [48] | Popa C 1998 Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems BIT Numer. Math.38 151-76 · Zbl 1005.65038 · doi:10.1007/bf02510922 |
| [49] | Popa C and Zdunek R 2004 Kaczmarz extended algorithm for tomographic image reconstruction from limited-data Math. Comput. Simul.65 579-98 · doi:10.1016/j.matcom.2004.01.021 |
| [50] | Lorenz D A, Rose S and Schöpfer F 2018 The randomized Kaczmarz method with mismatched adjoint BIT Numer. Math.58 1079-98 · Zbl 1404.65017 · doi:10.1007/s10543-018-0717-x |
| [51] | Gower R M, Goldfarb D and Richtarik P 2016 Stochastic block BFGS: squeezing more curvature out of data Int. Conf. on Machine Learning pp 1869-78 |
| [52] | Mokhtari A and Ribeiro A 2015 Global convergence of online limited memory BFGS J. Mach. Learn. Res.16 3151-81 · Zbl 1351.90124 |
| [53] | Chen Y, Dong G, Han J, Pei J, Wah B W and Wang J 2006 Regression cubes with lossless compression and aggregation IEEE Trans. Knowl. Data Eng.18 1585-99 · doi:10.1109/tkde.2006.196 |
| [54] | Kushner H and Yin G G 2003 Stochastic Approximation and Recursive Algorithms and Applications vol 35 (Berlin: Springer) · Zbl 1026.62084 |
| [55] | Egidi N and Maponi P 2006 A Sherman-Morrison approach to the solution of linear systems J. Comput. Appl. Math.189 703-18 · Zbl 1090.65037 · doi:10.1016/j.cam.2005.02.013 |
| [56] | Meng X, Saunders M A and LSRN M W M 2014 A parallel iterative solver for strongly over- or underdetermined systems SIAM J. Sci. Comput.36 C95-118 · Zbl 1298.65053 · doi:10.1137/120866580 |
| [57] | Hansen P C 2010 Discrete Inverse Problems: Insight and Algorithms (Philadelphia, PA: SIAM) · Zbl 1197.65054 · doi:10.1137/1.9780898718836 |
| [58] | Björck A 1996 Numerical Methods for Least Squares Problems (Philadelphia, PA: SIAM) · Zbl 0847.65023 · doi:10.1137/1.9781611971484 |
| [59] | Benveniste A, Wilson S S, Métivier M and Priouret P 2012 Adaptive Algorithms and Stochastic Approximations (New York: Springer) |
| [60] | Bottou L and Cun Y L 2005 On-line learning for very large data sets Appl. Stoch Model Bus. Ind.21 137-51 · Zbl 1091.68063 · doi:10.1002/asmb.538 |
| [61] | Nemirovski A, Juditsky A, Lan G and Shapiro A 2009 Robust stochastic approximation approach to stochastic programming SIAM J. Optim.19 1574-609 · Zbl 1189.90109 · doi:10.1137/070704277 |
| [62] | Bottou L, Curtis F E and Nocedal J 2018 Optimization methods for large-scale machine learning SIAM Rev.60 223-311 · Zbl 1397.65085 · doi:10.1137/16m1080173 |
| [63] | Paige C C and Saunders M A 1982 Algorithm 583, LSQR: sparse linear equations and least-squares problems ACM Trans. Math. Softw.8 195-209 · doi:10.1145/355993.356000 |
| [64] | Golub G H and Van Loan C F 2012 Matrix Computations vol 3 (Baltimore, MA: JHU Press) |
| [65] | Hämäläinen K, Harhanen L, Kallonen A, Kujanpää A, Niemi E and Siltanen S 2015 Tomographic x-ray data of a walnut (arXiv:1502.04064) |
| [66] | Jorgensen J Tomobox (accessed September 2019) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
