×

zbMATH — the first resource for mathematics

Paved with good intentions: analysis of a randomized block Kaczmarz method. (English) Zbl 1282.65042
Summary: The block Kaczmarz method is an iterative scheme for solving overdetermined least-squares problems. At each step, the algorithm projects the current iterate onto the solution space of a subset of the constraints. This paper describes a block Kaczmarz algorithm that uses a randomized control scheme to choose the subset at each step. This algorithm is the first block Kaczmarz method with an (expected) linear rate of convergence that can be expressed in terms of the geometric properties of the matrix and its submatrices. The analysis reveals that the algorithm is most effective when it is given a good row paving of the matrix, a partition of the rows into well-conditioned blocks. The operator theory literature provides detailed information about the existence and construction of good row pavings. Together, these results yield an efficient block Kaczmarz scheme that applies to many overdetermined least-squares problem.

MSC:
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
68W20 Randomized algorithms
41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
Software:
Blendenpik
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] R. Aharoni, Y. Censor, Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, in: Proceedings of the Fourth Haifa Matrix Theory Conference (Haifa, 1988), vol. 120, 1989, pp. 165-175. · Zbl 0679.65046
[2] Ailon, N.; Chazelle, B., The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 1, 302-322, (2009) · Zbl 1185.68327
[3] Avron, H.; Maymounkov, P.; Toledo, S., Blendenpik: supercharging lapack’s least-squares solver, SIAM J. Sci. Comput., 32, 3, 1217-1236, (2010) · Zbl 1213.65069
[4] Anderson, J., Extensions, restrictions, and representations of states on \(C^\ast\)-algebras, Trans. Amer. Math. Soc., 249, 2, 303-329, (1979) · Zbl 0408.46049
[5] M. Benzi, Key moments in the history of numerical analysis, Presented at 2009 SIAM Applied Linear Algebra Conference, October 2009.
[6] C. Boutsidis, A. Gittens, Improved matrix algorithms via the Subsampled Randomized Hadamard Transform. arXiv:1204.0062, April 2012. · Zbl 1286.65054
[7] Berman, K.; Halpern, H.; Kaftal, V.; Weiss, G., Matrix norm inequalities and the relative Dixmier property, Integral Equations Operator Theory, 11, 1, 28-48, (1988)
[8] Björck, Å., Numerical methods for least squares problems, (1996), Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 0847.65023
[9] Bourgain, J.; Tzafriri, L., Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J. Math., 57, 2, 137-224, (1987) · Zbl 0631.46017
[10] Bourgain, J.; Tzafriri, L., On a problem of kadison and Singer, J. Reine Angew. Math., 420, 1-43, (1991) · Zbl 0729.47028
[11] Bai, Z. D.; Yin, Y. Q., Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab., 21, 3, 1275-1294, (1993) · Zbl 0779.60026
[12] Byrne, C. L., Applied iterative methods, (2008), A K Peters Ltd. Wellesley, MA · Zbl 1140.65001
[13] Chrétien, S.; Darses, S., Invertibility of random submatrices via tail decoupling and a matrix Chernoff inequality, Statist. Probab. Lett., 82, 7, 1479-1487, (2012) · Zbl 1246.15034
[14] C. Cenker, H.G. Feichtinger, M. Mayer, H. Steier, T. Strohmer, New variants of the POCS method using affine subspaces of finite codimension, with applications to irregular sampling, in: Proceedings of the SPIE: Visual Communications and Image Processing, 1992, pp. 299-310.
[15] Censor, Y.; Herman, G. T.; Jiang, M., A note on the behavior of the randomized Kaczmarz algorithm of strohmer and vershynin [mr2500924], J. Fourier Anal. Appl., 15, 4, 431-436, (2009) · Zbl 1177.68252
[16] Chen, X.; Powell, A., Almost sure convergence of the Kaczmarz algorithm with random measurements, J. Fourier Anal. Appl., 1-20, (2012)
[17] Casazza, P. G.; Tremain, J. C., The kadison-Singer problem in mathematics and engineering, Proc. Natl. Acad. Sci. USA, 103, 7, 2032-2039, (2006), (electronic) · Zbl 1160.46333
[18] Donoho, D. L.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inform. Theory, 47, 7, 2845-2862, (2001) · Zbl 1019.94503
[19] Eggermont, P. P.B.; Herman, G. T.; Lent, A., Iterative algorithms for large partitioned linear systems, with applications to image reconstruction, Linear Algebra Appl., 40, 37-67, (1981) · Zbl 0466.65021
[20] Elfving, T., Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35, 1, 1-12, (1980) · Zbl 0416.65031
[21] Eldar, Y. C.; Needell, D., Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma, Numer. Algorithms, 58, 2, 163-177, (2011) · Zbl 1230.65051
[22] S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkha, Applied and Numerical Harmonic Analysis, in press. · Zbl 1315.94002
[23] H.G. Feichtinger, T. Strohmer, A Kaczmarz-based approach to nonperiodic sampling on unions of rectangular lattices, in: SampTA ’95: 1995 Workshop on Sampling Theory and Applications, Jurmala, Latvia, September 1995, pp. 32-37.
[24] C.F. Gauss, Theoria Combinationis Observationum Erroribus Minimis Obnoxiae, Supplementum, Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), 1995 (Transl. G.W. Stewart).
[25] Gordon, R.; Bender, R.; Herman, G. T., Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography, J. Theoret. Biol., 29, 471-481, (1970)
[26] G.H. Golub, C.F. Van Loan, Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, third ed., Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[27] Herman, G.; Meyer, L., Algebraic reconstruction techniques can be made computationally efficient, IEEE Trans. Medical Imaging, 12, 3, 600-609, (1993)
[28] Halko, N.; Martinsson, P. G.; Tropp, J. A., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53, 2, 217-288, (2011) · Zbl 1269.65043
[29] Hamaker, C.; Solmon, D. C., The angles between the null spaces of X-rays, J. Math. Anal. Appl., 62, 1, 1-23, (1978) · Zbl 0437.45025
[30] Hanson, D. L.; Wright, F. T., A bound on tail probabilities for quadratic forms in independent random variables, Ann. Math. Statist., 42, 1079-1083, (1971) · Zbl 0216.22203
[31] Kaczmarz, S., Angenäherte auflösung von systemen linearer gleichungen, Bull. Int. Acad. Polon. Sci. Lett. Ser. A, 29, 335-357, (1937) · Zbl 0017.31703
[32] Kadison, R. V.; Singer, I. M., Extensions of pure states, Amer. J. Math., 81, 383-400, (1959) · Zbl 0086.09704
[33] B. Kashin, L. Tzafriri, Some remarks on coordinate restriction of operators to coordinate subspaces, Institute of Mathematics Preprint 12, Hebrew University, Jerusalem, 1993-1994.
[34] E. Liberty, Accelerated dense random projections, Ph.D. dissertation, Yale University, New Haven, CT, 2009.
[35] Leventhal, D.; Lewis, A. S., Randomized methods for linear constraints: convergence rates and conditioning, Math. Oper. Res., 35, 3, 641-654, (2010) · Zbl 1216.15006
[36] A. Naor, Sparse quadratic forms and their geometric applications, Technical Report No. 1033, Séminaire Bourbaki, January 2011.
[37] Natterer, F., The mathematics of computerized tomography, (Classics in Applied Mathematics, vol. 32, (2001), Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA), Reprint of the 1986 original · Zbl 0617.92001
[38] Needell, D., Randomized Kaczmarz solver for noisy linear systems, BIT, 50, 2, 395-403, (2010) · Zbl 1195.65038
[39] D. Needell, R. Ward, Two-subspace projection method for coherent overdetermined linear systems. arXiv:1204.0277, April 2012. · Zbl 1306.65190
[40] Popa, C., Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems, BIT, 38, 1, 151-176, (1998) · Zbl 1005.65038
[41] Popa, C., Block-projections algorithms with blocks containing mutually orthogonal rows and columns, BIT, 39, 2, 323-338, (1999) · Zbl 1126.65307
[42] Popa, C., A fast Kaczmarz-kovarik algorithm for consistent least-squares problems, Korean J. Comput. Appl. Math., 8, 1, 9-26, (2001) · Zbl 0970.65036
[43] Popa, C., A Kaczmarz-kovarik algorithm for symmetric ill-conditioned matrices, An. Ştiinţ. Univ. Ovidius Constanţa Ser. Mat., 12, 2, 135-146, (2004) · Zbl 1120.65318
[44] B. Recht, C. Ré, Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case studies, and consequences, in: Proceedings of the 25th Annual Conference on Learning Theory, Edinburgh, June 2012.
[45] P. Richtárik, M. Takáč, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. arXiv:1107.2848, April 2011.
[46] N. Srivastava, Spectral sparsification and restricted invertibility, Ph.D. dissertation, Yale University, New Haven, CT, 2010.
[47] Sezan, M. I.; Stark, H., Incorporation of a priori moment information into signal recovery and synthesis problems, J. Math. Anal. Appl., 122, 1, 172-186, (1987) · Zbl 0627.65133
[48] Spielman, D. A.; Srivastava, N., An elementary proof of the restricted invertibility theorem, Israel J. Math., 190, 83-91, (2012) · Zbl 1261.46007
[49] Strohmer, T.; Vershynin, R., Comments on the randomized Kaczmarz method, J. Fourier Anal. Appl., 15, 4, 437-440, (2009) · Zbl 1177.68253
[50] Strohmer, T.; Vershynin, R., A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15, 2, 262-278, (2009) · Zbl 1169.68052
[51] Tropp, J. A., Norms of random submatrices and sparse approximation, C. R. Math. Acad. Sci. Paris, 346, 23-24, 1271-1274, (2008) · Zbl 1170.46012
[52] Tropp, J. A., The random paving property for uniformly bounded matrices, Studia Math., 185, 1, 67-82, (2008) · Zbl 1152.46007
[53] J.A. Tropp, Column subset selection, matrix factorization, and eigenvalue optimization, in: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 978-986.
[54] Tropp, J. A., Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3, 1-2, 115-126, (2011) · Zbl 1232.15029
[55] Tropp, J. A., User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 4, 389-434, (2012) · Zbl 1259.60008
[56] Tseng, P., Dual coordinate ascent methods for non-strictly convex minimization, Math. Programming, 59, 2, Ser. A, 231-247, (1993) · Zbl 0782.90073
[57] Vershynin, R., John’s decompositions: selecting a large part, Israel J. Math., 122, 253-277, (2001) · Zbl 0998.46006
[58] Vershynin, R., Random sets of isomorphism of linear operators on Hilbert space, (High Dimensional Probability, IMS Lecture Notes Monograph Series, vol. 51, (2006), Institute of Mathematical Statistics Beachwood, OH), 148-154 · Zbl 1129.46006
[59] Woolfe, F.; Liberty, E.; Rokhlin, V.; Tygert, M., A fast randomized algorithm for the approximation of matrices, Appl. Comput. Harmon. Anal., 25, 3, 335-366, (2008) · Zbl 1155.65035
[60] Xu, J.; Zikatanov, L., The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc., 15, 3, 573-597, (2002) · Zbl 0999.47015
[61] P. Youssef, A note on column subset selection. arXiv:1212.0976, December 2012. · Zbl 1318.46004
[62] P. Youssef, Restricted invertibility and the Banach-Mazur distance to the cube. arXiv:1206.0654, June 2012. · Zbl 1304.15019
[63] A. Zouzias, N.M. Freris, Randomized extended Kaczmarz for solving least-squares. arXiv:1205.5770, May 2012. · Zbl 1273.65053
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.