Deterministic and randomized Kaczmarz methods for A X B = C AXB=C with applications to color image restoration Wenli Wang, Duo Liu, Gangrong Qu, Michiel E. Hochstenbach Abstract We study Kaczmarz type methods to solve consistent linear matrix equations. We first present a block Kaczmarz (BK) method that employs a deterministic cyclic row selection strategy. Assuming that the associated coefficient matrix has full column or row rank, we derive matrix formulas for a cycle of this BK method. Moreover, we propose a greedy randomized block Kaczmarz (GRBK) method and further extend it to a relaxed variant (RGRBK) and a deterministic counterpart (MWRBK). We establish the convergence properties of the proposed methods. Numerical tests verify the theoretical findings, and we apply the proposed methods to color image restoration problems. MSC Classification]15A06, 15A24, 65F10 keywords Deterministic and randomized Kaczmarz methods, consistent linear matrix equation, convergence, minimum norm solution, Kaczmarz for multiple right-hand sides, color image restoration pacs [ Dedicated with love to Prof. ?ke Björck, for his beautiful character, friendship, and work on many topics, including some appearing in this paper. 1 Introduction Given the matrices A\in\mathbb{R}^{m\times p} , B\in\mathbb{R}^{q\times n} , and C\in\mathbb{R}^{m\times n} , we are interested in solving X\in\mathbb{R}^{p\times q} from the consistent matrix equation \displaystyle AXB=C. (1.1) This equation has close connections to numerous important applications in engineering, such as image processing, stability analysis, control theory, regression analysis, computer vision, image processing, network analysis, and computer-aided geometric design; see, e.g., ref2 ; ref3 ; ref5 ; ref6 ; ref11 . One particular example that we will study is a forward model for noise-free color image restoration, which can be written as \displaystyle AXA_{\rm c}^{T}=C\,; (1.2) see, e.g., ref5 . In ( 1.1 ), A may be square, overdetermined ( m>p ) or underdetermined ( m
n or if A is not of full column rank; this results in a component in ( 2.1 ) by which the solution differs from A^{+}CB^{+} . However, it is the restriction of this operator to the space \text{range}(B)\otimes\text{range}(A^{T}) that has spectral radius less than 1, and this is what is relevant for the convergence of the Kaczmarz method, considering that the updates are in \text{range}(A^{T}) with transpose in \text{range}(B) . 3.3 The BK method with B of full row rank If B has full row rank, matrix equation ( 1.1 ) can be reformulated as \displaystyle AX=\widetilde{C}, (3.12) where \widetilde{C}=CB^{T}\,(BB^{T})^{-1} . This transformation may again be considered under the same circumstances as in Section 3.2 . Note that this is a linear system with multiple right-hand sides, and we perform a Kaczmarz type method involving rank-one updates to this problem. Then the corresponding update formula for the BK method (cf. line 5 of Algorithm 2 ) is \displaystyle X^{k+1}=X^{k}+\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,A_{i_{k},:}^{T}\,\big(\widetilde{C}_{i_{k},:}-A_{i_{k},:}X^{k}\big). (3.13) When the matrix B has relatively small dimensions, that is, both q and n are relatively small, the computational cost per iteration is slightly lower than that of Algorithm 2 , which has a per-iteration complexity of \mathcal{O}(q(p+n)) . In addition, computing \widetilde{C} must be performed in advance, introducing an initial computational cost. In Experiment 6.2 , we discuss some numerical results using update formula ( 3.13 ) in the context of model ( 1.2 ). Similar to Algorithm 3 , a cycle of iterative formula ( 3.13 ) is presented in Algorithm 4 . This method also includes rank-one update in line 5 with a per-iteration computational cost of \mathcal{O}(pq) . Algorithm 4 The BK method with B of full row rank 1: Input : initial guess X^{0} 2: Output: approximate solution to matrix equation ( 3.12 ) 3: for s=0 , 1 , 2 , \dots until convergence do 4: Set X^{s,\,0}=X^{s} 5: Compute X^{s,\,i}=X^{s,\,i-1}+\tfrac{\alpha}{\|A_{i,:}\|^{2}}\,A_{i,:}^{T}\,(\widetilde{C}_{i,:}-A_{i,:}\,X^{s,\,i-1}),\hskip 9.24994pti=1,\,\ldots,\,m 6: Update X^{s+1}=X^{s,\,m} 7: end for Algorithm 4 may be viewed as a natural extension of standard Kaczmarz method ( 1.4 ) for multiple right-hand sides. To the best of our knowledge, this method has not been proposed or studied before in the literature. Unlike treating AX=Y as a collection of q independent linear systems AX_{:,j}=Y_{:,j} and solving each separately, Algorithm 4 updates all columns of X simultaneously at each iteration. Based on the convergence results presented in Section 3.2 , we derive the following corollary. Equation ( 3.14 ) is a direct generalization for multiple right-hand sides of that of the classical Kaczmarz algorithm ( ref34 , Prop. 4) . Item (a) is an extension of ( ref34 , Thm. 5) , while part (b) is unique to the context of multiple right-hand sides. Theorem 3.6 . One cycle of Algorithm 4 can be written as \displaystyle X^{s+1}=X^{s}+A^{T}L_{\alpha}^{-1}\,(\widetilde{C}-AX^{s}). (3.14) If \alpha\in(0,2) , then Algorithm 4 is convergent and \rho\,(I_{p}-A^{T}\,L_{\alpha}^{-1}\,A)<1 . In addition: (a) If ( 1.1 ) is consistent, the process converges to a solution of this matrix equation. (b) If \text{range}(X^{0})\subseteq\text{range}(A^{T}) and \text{range}((X^{0})^{T})\subseteq\text{range}(B) , then the method converges to the minimum norm solution A^{+}\widetilde{C} ( =A^{+}CB^{+} ). Proof. By replacing Q with the identity matrix I in Proposition 3.3 , ( 3.14 ) for a cycle of Algorithm 4 can be directly obtained. Based on ( 3.14 ), by replacing Q with I in Theorem 3.5 , we get \displaystyle\text{vec}(X^{s+1})=[I_{pq}-(I_{q}\otimes A^{T}\,L_{\alpha}^{-1}\,A)]\,\text{vec}(X^{s})+\text{vec}(A^{T}\,L_{\alpha}^{-1}\,\widehat{C}\,Q^{T}), where I_{pq}-(I_{q}\otimes A^{T}\,L_{\alpha}^{-1}\,A) is a partitioned diagonal matrix of dimension pq\times pq , with each diagonal block equal to I_{q}-A^{T}\,L_{\alpha}^{-1}\,A . Thus, we have \displaystyle\rho\,[I_{pq}-(I_{q}\otimes A^{T}\,L_{\alpha}^{-1}\,A)]=\max\limits_{i=1,\dots,p}\ |1-\lambda_{i}(A^{T}\,L_{\alpha}^{-1}\,A)|=\rho\,(I_{p}-A^{T}\,L_{\alpha}^{-1}\,A). By Theorem 3.2 , Algorithm 4 converges if 0<\alpha<2 . Thus, it follows from Lemma 3.4 that \rho\,(I_{p}-A^{T}\,L_{\alpha}^{-1}\,A)<1 . Algorithm 3 is developed under the assumption that B has full column rank, while Algorithm 4 assumes that B has full row rank. When B is square and nonsingular, both conditions hold. We explore the connections between them in this special case, leading to the following proposition. Proposition 3.7 . Algorithms 3 and 4 are equivalent when coefficient matrix B is nonsingular. Proof. This equivalence arises from the fact that, if B is square, the matrix Q obtained from the QR decomposition of B is square and hence orthogonal. We have in this case \widehat{C}=CR^{-1} and \widetilde{C}=CR^{-1}Q^{T} . This implies \displaystyle X^{s,\,i} \displaystyle=X^{s,\,i-1}+\tfrac{\alpha}{\|A_{i,:}\|^{2}}\,A_{i,:}^{T}\,(\widehat{C}_{i,:}-A_{i,:}\,X^{s,\,i-1}\,Q)\,Q^{T} \displaystyle=X^{s,\,i-1}+\tfrac{\alpha}{\|A_{i,:}\|^{2}}\,A_{i,:}^{T}\,(C_{i,:}R^{-1}\,Q^{T}-A_{i,:}\,X^{s,\,i-1}) \displaystyle=X^{s,\,i-1}+\tfrac{\alpha}{\|A_{i,:}\|^{2}}\,A_{i,:}^{T}\,(\widetilde{C}_{i,:}-A_{i,:}\,X^{s,\,i-1}).~~~~~~\framebox{} In experiments in Section 6 , we find that indeed the number of iterations is exactly the same, also in finite precision arithmetic. We note that matrix equations ( 3.9 ) and ( 3.12 ) are special cases of the more general form ( 1.1 ). Consequently, the theoretical results derived for matrix equation ( 1.1 ) remain applicable to equations ( 3.9 ) and ( 3.12 ); however, the converse does not necessarily hold. We now provide a schematic table summarizing key properties of the cyclic and randomized Kaczmarz method. Just as for linear systems Ax=b , we have the following upper bounds for cyclic and randomized Kaczmarz for ( 1.1 ), per step and sweep; and invariance under scaling and permutation of rows. Method Upper bound step Upper bound sweep Scaling Permutation Cyclic — \rho(I-A^{T}L^{-1}A) \checkmark — Randomized \delta^{1/2} \delta^{m/2} — \checkmark Cyclic Kaczmarz does not have a nontrivial upper bound (i.e., smaller than 1) per step, since at some steps there may not be any progress. An important note is that the spectral radius gives an asymptotic factor (so may not hold initially), and that the randomized upper bound holds in expectation (so may also not hold, especially in the beginning; note that \sqrt{\mathbb{E}_{k}[\|X^{k}-X_{*}\|_{F}^{2}]}\geq\mathbb{E}_{k}[\|X^{k}-X_{*}\|_{F}] so \delta^{1/2} is an upper bound in expectation for the progress in \|X_{k}-X_{*}\|_{F} in one row-action step in the randomized method). Which one of the sweep bounds for cyclic and randomized is smaller is problem dependent. The convergence of cyclic Kaczmarz may be (much) faster than randomized, but also the other way around, mainly depending on the row ordering. If we start by randomly permuting the rows of A (and C as a result), which usually gives a row ordering that is not particularly favorable or unfavorable, then cyclic Kaczmarz typically behaves very similar to its randomized counterpart. 4 GRBK method and its relaxed and deterministic variants In this section, we extend the greedy strategy proposed in ref19 to solve matrix equation ( 1.1 ), resulting in the GRBK method, which is introduced in Section 4.1 . In addition, motivated by the relaxed strategy in ref20 and the maximal weighted residual strategy in ref25 ; Mc , we further improve the GRBK method and obtain its relaxed and deterministic variants, i.e., the RGRBK and MWRBK methods, which are presented in Sections 4.2 and 4.3 , respectively. 4.1 The GRBK method Let us for the moment shift focus to linear system ( 1.3 ) with associated residual r^{k}:=b-Ax^{k} . Bai and Wu ref19 observe that rows with larger residual norms exert a greater influence on the overall error, and therefore, they propose a GRK method that prioritizes these rows when solving linear system ( 1.3 ). The greedy selection strategy in GRK method involves the maximum and average row norms of r^{k} relative to A (i.e., \max\limits_{i}\tfrac{(r_{i,:}^{k})^{2}}{\|A_{i,:}\|^{2}} and \tfrac{\|r^{k}\|^{2}}{\|A\|_{F}^{2}} ), where their proportions sum to 1 and are balanced using a fixed factor of \tfrac{1}{2} . Extending the greedy strategy in ref19 , we propose Algorithm 5 to solve matrix equation ( 1.1 ). Algorithm 5 The GRBK method 1: Input : initial guess X^{0} 2: Output: approximate solution to matrix equation ( 1.1 ) 3: for k=0 , 1 , 2 , \dots until convergence do 4: Compute R^{0}=C-AX^{0}B 5: Compute \gamma_{k}=\tfrac{1}{2}\,\Big[\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}}\Big] 6: Determine the index set \mathcal{J}_{k}=\big\{i~|~\|R_{i,:}^{k}\|^{2}\geq\gamma_{k}\,\|A_{i,:}\|^{2}\big\} 7: Let \widetilde{R}^{k} contain the corresponding rows: \widetilde{R}_{i,:}^{k}=\left\{\begin{array}[]{ll}R_{i,:}^{k},&\text{if}~i\in\mathcal{J}_{k}\\ \mathbf{0},&\text{otherwise}\end{array}\right. 8: Choose i_{k}\in\mathcal{J}_{k} with probability \mathbb{P}({\rm row=}\ i_{k})=\|\widetilde{R}_{i_{k},:}^{k}\|^{2}\,/\,\|\widetilde{R}^{k}\|_{F}^{2} 9: Update X^{k+1}=X^{k}+\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,A_{i_{k},:}^{T}\,(R^{k}_{i_{k},:}\,B^{T}) 10: Compute R^{k+1}=R^{k}-\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,(AA_{i_{k},:}^{T})\,((R^{k}_{i_{k},:}\,B^{T})\,B) 11: end for The row selection strategy of the GRBK method is based on the residual. The two terms in line 5 represent the maximum and average row norms of R^{k} relative to A . These terms also play an important role in Algorithms 6 and 7 and in the analysis. With the second term, we can select the rows that have above average residual norm (relative to the norm of the rows of A ). Using the first term only, as we will do in Algorithm 7 , we can pick the row with maximal residual norm. In Algorithm 5 , we use the average of the two terms. We consider other weights in Algorithm 6 . The update operation in line 9 of Algorithm 5 involves a rank-one update, with complexity of \mathcal{O}(q(p+n)) . The computation in line 10 has a similar update with \mathcal{O}(qn+mp+mn) work. Therefore, the overall computational cost of Algorithm 5 per iteration is \mathcal{O}(pq+qn+mp+mn) : quadratic in the matrix sizes. Remark 4.1 . From line 6 of Algorithm 5 , the index set \mathcal{J}_{k} can be expressed as \displaystyle\mathcal{J}_{k}=\big\{i~\big|~\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\geq\tfrac{1}{2}\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\tfrac{1}{2}\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}}\big\}, (4.1) which filters out the rows with small residual norms. The index set \mathcal{J}_{k} is updated each iteration and is nonempty because of the following. First, we observe that \displaystyle\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\geq\sum_{i=1}^{m}\tfrac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}\,\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}=\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}}. Then, letting \tfrac{\|R_{j,:}^{k}\|^{2}}{\|A_{j,:}\|^{2}}=\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}} , we obtain \displaystyle\tfrac{\|R_{j,:}^{k}\|^{2}}{\|A_{j,:}\|^{2}}\geq\tfrac{1}{2}\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\tfrac{1}{2}\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}}=\gamma_{k}. This result shows that j\in\mathcal{J}_{k} and therefore \mathcal{J}_{k}\neq\emptyset . We now analyze the convergence of Algorithm 5 . To do so, we extend ( ref19 , Thm. 3.1) (which is for linear systems ( 1.3 )) to problem ( 1.1 ). We first introduce some relevant quantities that will play a central role in several results to follow. Let us define \displaystyle\Omega_{k}:=\Big\{i~\big|~\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}<\tfrac{1}{m}\sum_{i\in[m]}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\Big\}. (4.2) This means that \Omega_{k} is exactly the set of row indices for which the residual norm (relative to A ) is below average. It is obvious that \frac{1}{m}\sum_{i\in[m]}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\leq\max\limits_{1\leq i\leq m}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}} . In what is to follow, we make the very mild assumption that not all ratios \|R_{i,:}^{k}\|^{2}\,/\,\|A_{i,:}\|^{2} are exactly the same (which holds with probability one). Therefore, we can write \frac{1}{m}\sum_{i\in[m]}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}=\varepsilon\cdot\max\limits_{1\leq i\leq m}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}} , with 0<\varepsilon<1 . Then, let \theta\in[0,1] , and define \displaystyle\varphi_{k,\,\theta}:=\theta\cdot\tfrac{1}{\sum_{i\in[m]\backslash\Omega_{k}}{\|A_{i,:}\|^{2}}+\varepsilon\,\sum_{i\in\Omega_{k}}{\|A_{i,:}\|^{2}}}+(1-\theta)\cdot\tfrac{1}{\|A\|_{F}^{2}}. (4.3) It is easy to see that \varphi_{k,\,\theta}\geq\tfrac{1}{\|A\|_{F}^{2}} for all \theta\in[0,1] . Moreover, under our mild assumption we know that \varphi_{k,\,\theta}>\tfrac{1}{\|A\|_{F}^{2}} for all \theta\in(0,1] . Using this \varphi_{k,\,\theta} , we next define a quantity that plays a key role as an upper bound on the convergence factor: \displaystyle\delta_{k,\,\theta}:=1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\varphi_{k,\,\theta}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B). (4.4) From the lower bound on \varphi_{k,\,\theta} , it follows that \displaystyle\delta_{k,\,\theta}<1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\|A\|_{F}^{-2}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B)=\delta, (4.5) where \delta is the upper bound on the convergence factor of Algorithm 1 as in ( 2.3 ). We note that \delta coincides with \delta_{k,0} . In the next theorem, \varphi_{k,\,1/2} and \delta_{k,\,1/2} are relevant; we will need \varphi_{k,\,\theta} and \delta_{k,\,\theta} for other values of \theta later on. Theorem 4.2 . (Extension of ( ref19 , Thm. 3.1) ) Let matrix equation ( 1.1 ) with A\in\mathbb{R}^{m\times p} , B\in\mathbb{R}^{q\times n} and C\in\mathbb{R}^{m\times n} be consistent. If 0<\alpha<\tfrac{2}{\|B\|^{2}} , then the sequence \{X^{k}\}_{k=0}^{\infty} , obtained by Algorithm 5 converges in expectation to a solution of ( 1.1 ). If \text{range}(X^{0})\subseteq\text{range}(A^{T}) and \text{range}((X^{0})^{T})\subseteq\text{range}(B) , then Algorithm 5 converges in expectation to the unique minimum norm solution X_{\ast} . Moreover, the solution error satisfies \displaystyle\mathbb{E}_{k}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\delta_{k,\,1/2}\cdot\|X^{k}-X_{\ast}\|_{F}^{2}\leq\delta\cdot\|X^{k}-X_{\ast}\|_{F}^{2}. (4.6) Consequently, we have \displaystyle\mathbb{E}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\displaystyle\prod_{\ell=0}^{k}\delta_{\ell,\,1/2}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}\leq\delta^{k+1}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}. (4.7) Proof. Let \zeta_{k}=\tfrac{1}{2}\,\Big[\frac{1}{\|R^{k}\|_{F}^{2}}\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\tfrac{1}{\|A\|_{F}^{2}}\Big] . Then, according to line 5 of Algorithm 5 , for all i\in\mathcal{J}_{k} we have \frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\geq\gamma_{k}=\|R^{k}\|_{F}^{2}\ \zeta_{k} . For 0<\alpha<\tfrac{2}{\|B\|^{2}} , we take the expectation of ( 3.6 ), conditional on the first k iterations, which gives: \displaystyle\mathbb{E}_{k}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big] \displaystyle\phantom{MM}\leq\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\,\sum_{i=1}^{m}\tfrac{\|\widetilde{R}_{i,:}^{k}\|^{2}}{\|\widetilde{R}^{k}\|_{F}^{2}}\,\tfrac{\|C_{i,:}-A_{i,:}\,X^{k}B\|^{2}}{\|A_{i,:}\|^{2}} \displaystyle\phantom{MM}\leq\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\sum_{i\in\mathcal{J}_{k}}\tfrac{\|\widetilde{R}_{i,:}^{k}\|^{2}}{\|\widetilde{R}^{k}\|_{F}^{2}}\,\zeta_{k}\,\|R^{k}\|_{F}^{2} \displaystyle\phantom{MM}=\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\ \zeta_{k}\ \|A\,(X^{k}-X_{\ast})\,B\|_{F}^{2} \displaystyle\phantom{MM}=\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\ \zeta_{k}\ \|(B^{T}\otimes A)\,\text{vec}(X^{k}-X_{\ast})\|^{2}, (4.8) where \mathcal{J}_{k} is as in ( 4.1 ). Furthermore, we note that \text{vec}(X^{0}-X_{*})\in\text{range}(B\otimes A^{T}) and \displaystyle\text{vec}(\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,A_{i_{k},:}^{T}\,((C_{i_{k},:}-A_{i_{k},:}\,X^{k}B)\,B^{T}))\in\text{range}(B\otimes A^{T}). Thus, we have \text{vec}(X^{k}-X_{*})\in\text{range}(B\otimes A^{T}) by induction. Since \|A^{T}x\|^{2}\geq\sigma^{2}_{\text{min}}(A)\,\|x\|^{2} holds for any x\in\text{range}(A) (cf., e.g., ( ref11 , Lemma 2.1) ), it follows that \displaystyle\|(B^{T}\otimes A)\,\text{vec}(X_{k}-X_{*})\| \displaystyle\geq\sigma_{\min}(B\otimes A^{T})\,\|\text{vec}(X_{k}-X_{*})\| \displaystyle=\sigma_{\min}(A)\,\sigma_{\min}(B)\,\|X_{k}-X_{*}\|_{F}. (4.9) Thus, inequality ( 4.1 ) becomes \displaystyle\mathbb{E}_{k}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\big(1-(2\alpha-\alpha^{2}\,\|B\|^{2})\,\zeta_{k}\,\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B)\big)\cdot\|X^{k}-X_{\ast}\|_{F}^{2}. (4.10) In addition, we have \displaystyle\zeta_{k}\ \|A\|_{F}^{2} \displaystyle=\tfrac{1}{2}\,\frac{\max\limits_{i}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}}{\frac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}}}+\tfrac{1}{2} \displaystyle=\tfrac{1}{2}\,\frac{\max\limits_{i}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}}{\sum_{i\in[m]\backslash\Omega_{k}}\frac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}\,\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\sum_{i\in\Omega_{k}}\frac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}\,\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}}+\tfrac{1}{2} \displaystyle\geq\tfrac{1}{2}\,\frac{1}{\sum_{i\in[m]\backslash\Omega_{k}}\tfrac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}+\varepsilon\,\sum_{i\in\Omega_{k}}\frac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}}+\tfrac{1}{2}. (4.11) This means that \zeta_{k}\geq\varphi_{k,\,1/2} , which is larger than \|A\|_{F}^{-2} under the mild assumption that not all residual rows have equal weight. Applying the law of total expectation \mathbb{E}[\cdot]=\mathbb{E}[\mathbb{E}_{k}[\cdot]] (cf., e.g., ref19 ; ref20 ; ref11 ), inequality ( 4.10 ) becomes \displaystyle\mathbb{E}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\delta_{k,\,1/2}\cdot\mathbb{E}\big[\|X^{k}-X_{\ast}\|_{F}^{2}\big]. (4.12) An induction on the iteration number and ( 4.5 ) gives the estimate ( 4.7 ). We note that if \text{range}(X^{0})\subseteq\text{range}(A^{T}) and \text{range}((X^{0})^{T})\subseteq\text{range}(B) , the rank-one updates in Algorithm 5 are such that for all k we keep the property \text{range}(X^{k})\subseteq\text{range}(A^{T}) and \text{range}((X^{k})^{T})\subseteq\text{range}(B) . Thus, the sequence \{X^{k}\}_{k=0}^{\infty} , converges in expectation to the unique minimum norm solution X_{\ast} . As a side note, in ref19 , Bai and Wu find that r^{k}_{i_{k-1}}=0 , where r^{k}_{i_{k-1}} is the i_{k-1} th component of the associated residual r^{k} . By utilizing this relation, they obtain \displaystyle\frac{\max\limits_{i}\frac{\|r_{i}^{k}\|^{2}}{\|A_{i,:}\|^{2}}}{\sum_{i\in[m]}\frac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}\,\tfrac{\|r_{i}^{k}\|^{2}}{\|A_{i,:}\|^{2}}} \displaystyle=\frac{\max\limits_{i}\frac{\|r_{i}^{k}\|^{2}}{\|A_{i,:}\|^{2}}}{\sum_{i\neq i_{k-1}}\frac{\|A_{i,:}\|^{2}}{\|A\|_{F}^{2}}\,\tfrac{\|r_{i}^{k}\|^{2}}{\|A_{i,:}\|^{2}}} \displaystyle\geq\frac{\|A\|_{F}^{2}}{\sum_{i\neq i_{k-1}}\|A_{i,:}\|^{2}}\geq\frac{\|A\|_{F}^{2}}{\max\limits_{1\leq j\leq m}\sum_{i\neq j}\|A_{i,:}\|^{2}}. However, for our matrix equation ( 1.1 ), there will generally be no zero residual row (no index i with R^{k}_{i,:}={\bf 0} ). Therefore, we need a different type of set \Omega_{k} (compared to ref19 ) in the derivation of ( 4.11 ). It would also be possible to exploit our set \Omega_{k} for the context of linear systems ( 1.3 ) as treated in ref19 . From inequality ( 4.12 ), the sequence \big\{\mathbb{E}[\|X^{k}-X_{\ast}\|_{F}^{2}]\big\} is decreasing if 0<\alpha<2\,\|B\|^{-2} . Moreover, similar to ( 3.6 ), inequality ( 4.12 ) also includes the function g(\alpha)=2\alpha-\alpha^{2}\,\|B\|^{2} , which attains its maximum at \alpha=\|B\|^{-2} . This indicates that the upper bound of the convergence factor is minimized when the parameter \alpha is set to \|B\|^{-2} . 4.2 The RGRBK method In the previous subsection, the GRK method employed fixed weights equal to \tfrac{1}{2} for the maximum and average row norms of r^{k} relative to A . A natural question arises: what happens if different proportions are used? To explore this, Bai and Wu ref20 , in the context of ( 1.3 ), introduce a variable parameter \theta\in[0,1] and propose an RGRK method. Two cases of the parameter \theta in the RGRK method are of particular interest: \bullet \theta=\tfrac{1}{2} : The RGRK method coincides with the GRK method in ref19 . \bullet \theta=1 : The RGRK method is equivalent to the MWRK method in ref25 ; Mc , a deterministic approach that selects the row with the maximum residual; see also Section 4.3 . Extending RGRK ref20 (which is for linear systems ( 1.3 )), we now propose and study an RGRBK method to solve matrix equation ( 1.1 ) in Algorithm 6 (cf. also Table 1.2 ). Algorithm 6 The RGRBK method 1: Input : initial guess X^{0} , parameter \theta\in[0,1] 2: Output: approximate solution to matrix equation ( 1.1 ) 3: for k=0 , 1 , 2 , \dots until convergence do 4: Compute R^{0}=C-AX^{0}B 5: Compute \xi_{k}=\theta\cdot\max\limits_{1\leq i\leq m}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+(1-\theta)\cdot\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}} 6: Determine the index set \mathcal{H}_{k}=\big\{i~|~\|R_{i,:}^{k}\|^{2}\,\geq\,\xi_{k}\,\|A_{i,:}\|^{2}\big\} 7: Let \widetilde{R}^{k} be the correspondingly selected rows: \widetilde{R}_{i,:}^{k}=\left\{\begin{array}[]{ll}R_{i,:}^{k},&\text{if}~i\in\mathcal{H}_{k}\\ \mathbf{0},&\text{otherwise}\\ \end{array}\right. 8: Choose i_{k}\in\mathcal{H}_{k} with probability \mathbb{P}({\rm row=}\ i_{k})=\|\widetilde{R}_{i_{k},:}^{k}\|^{2}\,/\,\|\widetilde{R}^{k}\|_{F}^{2} 9: Update X^{k+1}=X^{k}+\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,A_{i_{k},:}^{T}\,(R^{k}_{i_{k},:}\,B^{T}) 10: Compute R^{k+1}=R^{k}-\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,(AA_{i_{k},:}^{T})\,((R^{k}_{i_{k},:}\,B^{T})\,B) 11: end for Note that Algorithm 6 retains the same per-iteration computational complexity as Algorithm 5 . The reason for the non-emptiness of the index set \mathcal{H}_{k} is analogous to Remark 4.1 . In a manner analogous to Theorem 4.2 , we derive Theorem 4.3 ; its proof is omitted. Theorem 4.3 . Let matrix equation ( 1.1 ) with A\in\mathbb{R}^{m\times p} , B\in\mathbb{R}^{q\times n} and C\in\mathbb{R}^{m\times n} be consistent. If 0<\alpha<\tfrac{2}{\|B\|^{2}} , then the sequence \{X^{k}\}_{k=0}^{\infty} , obtained by Algorithm 6 converges in expectation to a solution of ( 1.1 ). If \text{range}(X^{0})\subseteq\text{range}(A^{T}) and \text{range}((X^{0})^{T})\subseteq\text{range}(B) , then Algorithm 6 converges in expectation to the unique minimum norm solution X_{\ast} . Moreover, the solution error satisfies \displaystyle\mathbb{E}_{k}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\delta_{k,\,\theta}\cdot\|X^{k}-X_{\ast}\|_{F}^{2}\leq\delta\cdot\|X^{k}-X_{\ast}\|_{F}^{2}, As a result, we have \displaystyle\mathbb{E}\big[\|X^{k+1}-X_{\ast}\|_{F}^{2}\big]\leq\displaystyle\prod_{\ell=0}^{k}\delta_{\ell,\theta}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}\leq\delta^{k+1}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}. We will compare the upper bounds of the convergence factors for the algorithms discussed in this section and the RBK algorithm proposed in ref12 in Section 4.3 . 4.3 The MWRBK method We now generalize the maximal weighted residual strategy in ref25 ; Mc (which is for linear systems ( 1.3 )) to matrix equation ( 1.1 ) (cf. also Table 1.2 ). We directly select the row with the largest weighted residual for each iteration, which can also be obtained from the RGRBK method by taking \theta=1 . This gives the following MWRBK method (Algorithm 7 ), which is a deterministic approach. Algorithm 7 The MWRBK method 1: Input : initial guess X^{0} 2: Output: approximate solution to matrix equation ( 1.1 ) 3: for k=0 , 1 , 2 , \dots until convergence do 4: Compute R^{0}=C-AX^{0}B 5: Let i_{k} be the index maximizing \|R_{i,:}^{k}\|^{2}\,/\,\|A_{i,:}\|^{2} ; if there are more, choose the smallest 6: Update X^{k+1}=X^{k}+\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,A_{i_{k},:}^{T}\,(R^{k}_{i_{k},:}\,B^{T}) 7: Compute R^{k+1}=R^{k}-\tfrac{\alpha}{\|A_{i_{k},:}\|^{2}}\,(AA_{i_{k},:}^{T})\,((R^{k}_{i_{k},:}\,B^{T})\,B) 8: end for A theoretical estimate of the convergence rate of Algorithm 7 is given below, which is along the same lines as in ( ref25 , Thm. 3.1) . Theorem 4.4 . Let matrix equation ( 1.1 ) with A\in\mathbb{R}^{m\times p} , B\in\mathbb{R}^{q\times n} and C\in\mathbb{R}^{m\times n} be consistent. Let 0<\alpha<\tfrac{2}{\|B\|^{2}} and X^{k} denote the k th iteration obtained by Algorithm 7 with \text{range}(X^{0})\subseteq\text{range}(A^{T}) and \text{range}((X^{0})^{T})\subseteq\text{range}(B) . Then \displaystyle\|X^{k+1}-X_{\ast}\|_{F}^{2}\leq\displaystyle\prod_{\ell=0}^{k}\,\delta_{\ell,\,1}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}\leq\delta^{k+1}\cdot\|X^{0}-X_{\ast}\|_{F}^{2}, (4.13) where \delta_{\ell,\,1} is defined in ( 4.4 ). Proof. The method for \theta=1 is deterministic, and therefore the proof technique is different from Theorems 4.2 and 4.3 . For 0<\alpha<\tfrac{2}{\|B\|^{2}} , using that i_{k} maximizes the quantity in line 5 of Algorithm 7 , we have \displaystyle\|X^{k+1}-X_{\ast}\|_{F}^{2} \displaystyle\leq\|X^{k}-X_{\ast}\|_{F}^{2}-\tfrac{2\alpha-\alpha^{2}\,\|B\|^{2}}{\|A_{i_{k},:}\|^{2}}\,\|R_{i_{k},:}^{k}\|^{2} \displaystyle=\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\,\tfrac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}\tfrac{\|R^{k}\|_{F}^{2}}{\sum_{i\in[m]\backslash\Omega_{k}}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\,\|A_{i,:}\|^{2}+\sum_{i\in\Omega_{k}}\frac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}\,\|A_{i,:}\|^{2}} \displaystyle\leq\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\,\tfrac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}\tfrac{\|R^{k}\|_{F}^{2}}{\frac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}\,\big(\sum_{i\in[m]\backslash\Omega_{k}}\|A_{i,:}\|^{2}+\sum_{i\in\Omega_{k}}\varepsilon\,\|A_{i,:}\|^{2}\big)} \displaystyle=\|X^{k}-X_{\ast}\|_{F}^{2}-(2\alpha-\alpha^{2}\,\|B\|^{2})\,\tfrac{\|A\,(X^{k}-X_{\ast})\,B\|_{F}^{2}}{\sum_{i\in[m]\backslash\Omega_{k}}\|A_{i,:}\|^{2}+\varepsilon\,\sum_{i\in\Omega_{k}}\|A_{i,:}\|^{2}} \displaystyle\leq\big(1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\varphi_{k,\,1}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B)\big)\cdot\|X^{k}-X_{\ast}\|_{F}^{2}. In the last line, we have used ( 4.1 ). Induction on the iteration number gives inequality ( 4.13 ). Similar to the discussions in Sections 3.1 and 4.1 , the upper bound of the convergence factor for the RGRBK and MWRBK methods is minimized when \alpha=\|B\|^{-2} . Table 4.1 provides a summary of the upper bounds of the convergence factors of the methods involved in this section for solving matrix equation ( 1.1 ). Recall that \delta is equal to \delta_{k,0} . Table 4.1: The upper bound on the convergence factors of RBK ref12 , GRBK, RGRBK, and MWRBK methods for solving AXB=C . Method Convergence factor upper bound Result RBK ref12 \delta=\delta_{k,\,0} =1-\frac{2\alpha-\alpha^{2}\,\|B\|^{2}}{\|A\|_{F}^{2}}\,\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B) ( ref12 , Thm. 1) GRBK (Alg. 5 ) \delta_{k,\,1/2} =1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\varphi_{k,\,1/2}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B) <\delta Thm. 4.2 RGRBK (Alg. 6 ) \delta_{k,\,\theta} =1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\varphi_{k,\,\theta}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B) <\delta Thm. 4.3 MWRBK (Alg. 7 ) \delta_{k,\,1} =1-(2\alpha-\alpha^{2}\,\|B\|^{2})\cdot\varphi_{k,\,1}\cdot\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B) <\delta Thm. 4.4 With respect to these upper bounds, we have already seen that the upper bounds of the convergence factors for GRBK, RGRBK, and MWRBK are not larger than the \delta for RBK. For linear systems ( 1.3 ), the authors of ( ref20 , Sec. 2) show that the upper bound of the convergence factor of RGRK is a monotonically decreasing function with respect to the parameter \theta . We generalize this result for ( 1.1 ) by establishing that the upper bound of the convergence factor for the proposed RGRBK method also exhibits a decreasing behavior with respect to \theta (under the very mild assumption of not having equal residual rows as mentioned before): \frac{\partial\delta_{k,\,\theta}}{\partial\theta}=(2\alpha-\alpha^{2}\,\|B\|^{2})\,\sigma_{\min}^{2}(A)\,\sigma_{\min}^{2}(B)\cdot\big(\tfrac{1}{\|A\|_{F}^{2}}-\tfrac{1}{\sum_{i\in[m]\backslash\Omega_{k}}{\|A_{i,:}\|^{2}}+\varepsilon\,\sum_{i\in\Omega_{k}}{\|A_{i,:}\|^{2}}}\big)<0. This means that the upper bound \delta_{k,\,\theta} on the convergence factor is decreasing as a function of \theta . Therefore, we expect that the (deterministic) MWRBK method (corresponding to \theta=1 ) may converge fastest; this is indeed confirmed by experiments in the following sections. Table 4.2 provides an overview of the index selection criteria of the methods involved in this section for solving equations ( 1.1 ) and ( 1.3 ). The RGRBK method has a parameter \theta\in[0,1] ; it becomes the GRBK method for \theta=\tfrac{1}{2} and the MWRBK method for \theta=1 . Fig. 4.3 gives a schematic graph of \delta_{k,\,\theta} as a function of the parameter \theta , together with the relations between the RGRBK, GRBK, and MWRBK methods. Table 4.2: Index selection criteria of the methods involved in this section for solving Ax=b and AXB=C . Ax=b GRK ref19 \tfrac{(r_{i_{k},:}^{k})^{2}}{\|A_{i_{k},:}\|^{2}}\geq\tfrac{1}{2}\max\limits_{i}\tfrac{(r_{i,:}^{k})^{2}}{\|A_{i,:}\|^{2}}+\tfrac{1}{2}\tfrac{\|r^{k}\|_{F}^{2}}{\|A\|_{F}^{2}} RGRK ref20 \tfrac{(r_{i_{k},:}^{k})^{2}}{\|A_{i_{k},:}\|^{2}}\geq\theta\,\max\limits_{i}\tfrac{(r_{i,:}^{k})^{2}}{\|A_{i,:}\|^{2}}+(1-\theta)\tfrac{\|r^{k}\|_{F}^{2}}{\|A\|_{F}^{2}} MWRK ref25 ; Mc \tfrac{(r_{i_{k},:}^{k})^{2}}{\|A_{i_{k},:}\|^{2}}=\max\limits_{i}\tfrac{(r_{i,:}^{k})^{2}}{\|A_{i,:}\|^{2}} AXB=C GRBK (Alg. 5 ) \tfrac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}\geq\tfrac{1}{2}\max\limits_{i}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+\tfrac{1}{2}\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}} RGRBK (Alg. 6 ) \tfrac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}\geq\theta\,\max\limits_{i}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}}+(1-\theta)\tfrac{\|R^{k}\|_{F}^{2}}{\|A\|_{F}^{2}} MWRBK (Alg. 7 ) \tfrac{\|R_{i_{k},:}^{k}\|^{2}}{\|A_{i_{k},:}\|^{2}}=\max\limits_{i}\tfrac{\|R_{i,:}^{k}\|^{2}}{\|A_{i,:}\|^{2}} Fig. 4.3: Schematic graph of \delta_{k,\,\theta} with respect to \theta , and relations between RGRBK, GRBK, and MWRBK methods. In Table 4.4 , we summarize the per-iteration computational complexity of various methods for solving matrix equation ( 1.1 ). All algorithms, except for the GI ref8 , are row-action methods that involve rank-one updates; cf. also Table 1.1 . Table 4.4: The per-iteration computational complexity of various methods for solving AXB=C . Method Complexity BK (Alg. 2 ), RBK (Alg. 1 ref12 ) \mathcal{O}(q(p+n)) BK (Alg. 3 ) \mathcal{O}(q(p+n)) BK (Alg. 4 ) \mathcal{O}(pq) GRBK, RGRBK, MWRBK (Algs. 5 , 6 , 7 ) \mathcal{O}(pq+qn+mp+mn) RGRK ref11 , MWRK ref11 \mathcal{O}(pq+qn+mp+mn) GI ref8 \min(\mathcal{O}(mq(p+n)),\,\mathcal{O}(pn(m+q))) 5 Numerical examples This section provides some numerical examples to validate the main theoretical findings. All experiments are tested using MATLAB R2021b on a laptop with Intel(R) Core(TM) i5-12500H CPU @ 2.50GHz. We examine the methods from the aspects of the number of iterations (denoted by ‘IT’), elapsed CPU time in seconds (denoted by ‘CPU’), and relative solution error (denoted by ‘RSE’). In each experiment, the randomized methods (GRBK, RGRBK, and MWRBK) are executed for 20 independent trials. For randomized methods, the values of the IT and CPU are the averages of 20 trials. We also show the standard deviation (denoted by ‘SD’) and the range (denoted by ‘Range’) of the CPUs derived from 20 independent experiments. Based on the discussions in Sections 3 and 4 , we take the parameter \alpha=\|B\|^{-2} . In addition, as discussed in Section 4.3 , the upper bound on the convergence factor of the RGRBK method is smaller than that of the GRBK method for \theta\in(\tfrac{1}{2},1) ; therefore, we focus on this case. The initial guess X^{0} is the zero matrix for all experiments. This is a common choice in Kaczmarz type methods, as it tends to give good approximation results. Also, this satisfies the requirements of the various theorems (namely \text{range}(X_{0})\subseteq\text{range}(A^{T}) and \text{range}(X_{0}^{T})\subseteq\text{range}(B) ), so that all methods converge to the minimum norm solution X_{*}=A^{+}CB^{+} . The coefficient matrices A and B selected as test matrices include sparse matrices from the University of Florida sparse matrix collection ref33 and dense matrices randomly generated by the function \sf randn . These matrices have also been used in ref19 ; ref20 ; ref25 ; ref12 ; Du . The matrix X is produced by \sf randn(p,q) . To create a consistent system, the matrix C is generated by C=AXB . We present the size, rank, and density of the coefficient matrices, where the density is defined as \displaystyle\text{density}:=\text{number of nonzeros of an}\ m\times n\ \text{matrix}\,/\,(m\,n). We now briefly discuss possible stopping criteria. A practical rule for all methods may be based on the norm of the rank-one update (cf. Table 4.4 ): \|X^{k+1}-X^{k}\|=\alpha\ \|R_{i_{k},:}^{k}\,B^{T}\|\,/\,\|A_{i_{k},:}\|. Another natural stopping criterion is to use \|R^{k}\| , especially in Algorithms 5 – 7 , where the residual R^{k} is already available. However, rather than comparing these rules in details, we focus on the behavior of the methods considering the solution error: \displaystyle\text{RSE}:=\|X^{k}-X_{\ast}\|_{F}\,/\,\|X_{\ast}\|_{F}. Example 5.1 . In this example, we analyze the convergence behavior of the three BK methods, i.e., Algorithms 2 , 3 , and 4 . We first investigate the convergence of Algorithm 2 . For a consistent matrix equation ( 1.1 ), the coefficient matrices can be categorized into nine different configurations. Specifically, when A is row-full-rank, column-full-rank, or rank-deficient, B may also be row-full-rank, column-full-rank, or rank-deficient. Table 5.1 lists nine corresponding sets of test matrices used to evaluate the performance of Algorithm 2 . The convergence curves of Algorithm 2 are given in Fig. 5.2 . Table 5.3 summarizes the dimensions of the test matrices and reports the results of the IT and CPU. These results illustrate that Algorithm 2 seems feasible for various problem sizes, including overdetermined and underdetermined systems, typically with a linear asymptotic convergence. The time per iteration seems to have a natural relation with the sparsity of the coefficient matrices. For instance, the matrices in Sets 1 and 3 are relatively dense and have the longest per-iteration computation times. Table 5.1: The test matrices used in Example 5.1 , where various scenarios are tested: m>p and m
q
and
pn
and
q