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(A_{\rm c})_{i,j} for i\neq j . To ensure the preservation of total intensity, each row of A_{\rm c} is constrained to sum to 1, i.e., \sum_{j}(A_{\rm c})_{i,j}=1 . In our examples, we choose the (rather typical) cross-channel blurring matrix as \displaystyle\small A_{\rm c}=\left[\begin{array}[]{cccc}0.90&0.05&0.05\\ 0.00&0.90&0.10\\ 0.05&0.10&0.85\end{array}\right]. The bottom row of Fig. 6.1 shows the blurred images, with their corresponding peak signal-to-noise ratio (PSNR) values 19.31, 17.52, and 18.86, respectively. Fig. 6.1: Test images (top row) and blurred images (bottom row). Table 6.2 provides an overview of the size of the experiments in this section. Notice that for this application, m=p (i.e., A is square), and q=n ( B is square), with p\gg q ( X is tall and skinny). We remark that in this specific experiment the matrix B=A_{c}^{T} is a small 3\times 3 nonsingular matrix, for which direct inversion is natural and offers a natural solution, as in Algorithm 4 . We test this approach in Experiment 6.2 , but also stress that we have developed methods to solve ( 1.1 ) for A and B of arbitrary size. Table 6.2: Overview of the sizes of the experiments in Section 6 , and of the degrees of freedom (dofs) in the solution X (equal to pq ). Experiment m=p q=n dofs face 1 8464 3 25392 bird 1 9216 3 27648 mandril 15000 3 45000 Experiment 6.1 . In this experiment, we compare the restored results of the GI ref8 , BK (Alg. 2 ), RBK ref12 (Alg. 1 ), GRBK (Alg. 5 ), RGRBK (Alg. 6 ), and MWRBK (Alg. 7 ) methods. All methods, except for GI, process one row per iteration. The GI method uses all rows in each iteration, which may be computationally more expensive, as also confirmed by this experiment. In Fig. 6.3 , we plot the PSNR versus the time spent using these methods. In this experiment, we run the randomized methods only once. To achieve comparable PSNR values, the GI, BK, and RBK methods require more computation time than the GRBK, RGRBK, and MWRBK methods, with the GI method being the most time-consuming among all. As expected from the discussion in Section 4 , increasing \theta from 0.5 (GRBK), via an intermediate value in the interval (0.5,1) (RGRBK), to 1 (MWRBK) has a favorable effect on the performance. Furthermore, the randomized RBK is still faster than the deterministic BK, which means that taking rows with larger norm pays off. When we would scale ( 1.1 ) apriori such that all rows have equal norm, it is expected that BK and RBK behave similarly. Fig. 6.3: Relation between PSNR and CPU for the restored face (left), bird (middle), and mandril (right) images using different methods. Experiment 6.2 . In this experiment, we compare the recovery results obtained by the GI ref8 , BK (Alg. 2 ), RBK ref12 , GRBK, RGRBK, and MWRBK methods. For a fair comparison and a good impression of the typical behavior of the various methods, we use the exact solution in the stopping criterion and terminate the iterations once \text{RSE}\leq 8\cdot 10^{-2} . The PSNR values of the restored images obtained by different algorithms are identical: 30.23 ( face ), 31.08 ( bird ), and 28.85 ( mandril ), respectively. Table 6.4 presents the numerical results, and Fig. 6.5 shows the restored images obtained by the MWRBK method. We observe that the GI method requires the longest per-iteration and total computation time, which is consistent with its cubic computational complexity compared to the quadratic complexity of the other algorithms. Although the number of iterations required by GI varies across cases, it seems a less competitive method overall. Although GRBK, RGRBK, and MWRBK incur higher CPU time per iteration (CPU/IT) than BK and RBK, they require significantly fewer iterations, resulting in a shorter overall computation time than BK and RBK. These results show that their overall convergence is faster than that of BK and RBK. As the problem size increases, the SD of the randomized algorithms (RBK, GRBK, and RGRBK) increases slightly. For example, in experiment \sf face , the SD values of the randomized methods are less than 2 , while in experiment \sf mandrill , the SD values increase modestly but remain below 7 . In addition, in unreported experiments we have compared the behavior of three BK methods (Algorithms 2 , 3 , and 4 ). For the case of this 3\times 3 matrix A_{\text{c}} , these BK methods generally have very similar number of iterations and runtimes, irrespective of how close A_{\text{c}} is to the identity. Proposition 3.7 shows that Algorithms 3 and 4 are equivalent given the fact that A_{\text{c}} is nonsingular, and our results indeed confirm that the numbers of iterations are identical. Table 6.4: The PSNR, IT, CPU, SD, Range, and CPU/IT of the restored images by the various methods, where all methods, except for GI, use a rank-one update at each iteration. Method face PSNR IT CPU SD Range CPU/IT GI 30.23 1 37689 113.8 – – 3.0\cdot 10^{-3} BK 30.23 281401 105.2 – – 3.7\cdot 10^{-4} RBK 30.23 139442 1 67.0 1.73 [64.1, 71.3] 4.8\cdot 10^{-4} GRBK 30.23 1 11534 1 19.0 0.58 [18.1, 20.0] 1.7\cdot 10^{-3} RGRBK 30.23 1 11191 1 17.8 0.70 [16.7, 18.9] 1.6\cdot 10^{-3} MWRBK 30.23 1 12045 1 17.4 – – 1.5\cdot 10^{-3} bird GI 31.08 602495 1919.3 – – 3.2\cdot 10^{-3} BK 31.08 821648 1 330.0 – – 4.0\cdot 10^{-4} RBK 31.08 390479 1 207.8 4.11 [200.5, 217.2] 5.3\cdot 10^{-4} GRBK 31.08 1 97871 1 167.8 3.09 [163.1, 173.2] 1.7\cdot 10^{-3} RGRBK 31.08 1 96407 1 158.4 2.10 [154.6, 162.1] 1.6\cdot 10^{-3} MWRBK 31.08 1 97475 1 147.2 – – 1.5\cdot 10^{-3} mandril GI 28.85 254358 1224.6 – – 4.8\cdot 10^{-3} BK 28.85 595118 1 474.2 – – 8.0\cdot 10^{-4} RBK 28.85 375388 1 314.1 6.41 [299.1, 328.7] 8.4\cdot 10^{-4} GRBK 28.85 1 59750 1 153.8 2.29 [150.6, 158.3] 2.6\cdot 10^{-3} RGRBK 28.85 1 58563 1 145.1 2.52 [141.0, 149.4] 2.5\cdot 10^{-3} MWRBK 28.85 1 58522 1 123.8 – – 2.1\cdot 10^{-3} Fig. 6.5: Restored images obtained by the MWRBK method for Experiment 6.2 . Based on the results provided in Tables 6.2 and 6.4 , we observe a proportional relation between the dofs and the computational cost per iteration (CPU/IT) for the three test images. For instance, in the RBK method, the CPU/IT increases from 8.4\cdot 10^{-4} for face to 4.8\cdot 10^{-4} for m andril, a ratio of approximately 1.75 . The dofs of m andril are approximately 1.77 times those of face . This consistent trend shows the influence of the problem size on per-iteration computational cost. The example bird requires the largest number of iterations, which might be due to the many edges in the figure. There is no clear relation of the number of iterations with the condition number of the within-channel blurring matrices A , as bird corresponds to the matrix having the smallest condition number of the three examples. Finally, some words about the scaling of the methods for larger images. We take larger 140\times 140 and 280\times 280 versions of face ; with 140^{2}\cdot 3=58800 and 280^{2}\cdot 3=235200 dofs, these have ca 2.3 and 9.3 more unknowns than the original 92\times 92 image. The CPU/IT scales exactly linear with the dofs. The number of iterations increases for larger images, probably because of having more details. For the 140\times 140 face , IT is ca 19000 instead of 12000. In conclusion, the CPU/IT is proportional to the dofs, and the number of iterations seems to depend on the complexity of the image. 7 Conclusions We have explored deterministic and randomized Kaczmarz methods to solve the consistent matrix equation ( 1.1 ), which arises commonly in many applications. Our methods can be used for A and B of any size (i.e., overdetermined and underdetermined cases), with the exception of Algorithms 3 and 4 , which require B to have full column or row rank. The gradient type GI method in ref8 uses a full-rank update in each iteration. The methods in ref11 use a rank-one addition with a single element of C and one column of B in each step. All of our proposed methods also perform a rank-one update at each iteration using one row of C and the entire matrix B . As summarized in Table 4.4 , the methods in ref11 and this paper require quadratic costs in terms of the matrix dimensions m,n,p,q , while the GI method in ref8 incurs a cubic complexity; see also Section 6 . We have first studied a (deterministic, cyclic) BK method in Section 3.1 (Algorithm 2 ). This is a straightforward extension of the standard Kaczmarz method to matrix equation ( 1.1 ) and also a deterministic (cyclic) version of the RBK method of ref12 . We have shown that this method converges to the solution X^{0}_{\ast} (=A^{+}CB^{+}+X^{0}-A^{+}AX^{0}BB^{+}) if 0<\alpha<2\,\|B\|^{-2} . We have also considered variants of this BK method under the assumption that B is of full column rank (Section 3.2 , Algorithm 3 ) or full row rank (Section 3.3 , Algorithm 4 ). These additional constraints enable us to derive a matrix expression for a sweep (cycle) of the BK method. Note that Algorithm 2 imposes no requirements on B , but the last two methods require B to be of full row or column rank (with nonsingularity as a special case) and of modest size. In addition, as shown in Proposition 3.7 , the last two methods are equivalent when the coefficient matrix B is nonsingular. In Experiment 6.2 , we have confirmed that these three BK methods exhibit a similar convergence behavior when B is 3\times 3 . Next, we have proposed and studied the GRBK method (Algorithm 5 ) and its relaxed and deterministic variants: RGRBK (Algorithm 6 ) and MWRBK (Algorithm 7 ) in Section 4 , which select rows based on the residual norm. Based on the experiments in Section 6 , the extra cost of computing this residual norm is worthwhile; in addition, the residual can also serve as a suitable stopping criterion. We have proven that they converge to the unique minimum norm solution A^{+}CB^{+} if 0<\alpha<2\,\|B\|^{-2} . According to the convergence analysis in Sections 3 and 4 , the upper bounds of the convergence factors for the proposed methods are minimized when \alpha=\|B\|^{-2} . As shown in Section 4.3 , the upper bound of the convergence factor for the GRBK, RGRBK, and MWRBK methods is not larger than that of RBK. Thus, it is reasonable to expect that they may require fewer iterations to achieve convergence. The experiments in Sections 5 and 6 show that this is indeed the case. The RGRBK method reduces to the GRBK method when \theta=\tfrac{1}{2} and to the MWRBK method when \theta=1 , as illustrated in Fig. 4.3 and Table 4.2 . Its convergence factor upper bound is decreasing with \theta . Therefore, the upper bound for the convergence factor is minimal at \theta=1 , where RGRBK coincides with MWRBK. Finally, based on the theoretical analysis and experimental results, the overall performance of the proposed methods can be summarized as follows. The BK method converges asymptotically (see Theorem 3.2 ); its convergence rate may be sensitive to the ordering of the rows in A . It may be (much) faster than its randomized counterpart (RBK), but it may also be slower. With a randomized initial ordering of the rows, the BK method typically behaves similarly to the randomized method RBK, without the drawback of the variance of RBK. We note although its convergence is often slower than other methods (see Section 6 ), BK is valuable for understanding the influence of row selection through comparisons with the randomized (RBK) and greedy (GRBK, RGRBK, MWRBK) counterparts. The greedy extensions (GRBK, RGRBK, and MWRBK) consistently achieve faster convergence than RBK, also observed in the numerical tests in Sections 5 and 6 . Although the greedy approaches are slower than the BK and RBK methods per iteration, they use fewer iterations with a lower runtime. The randomized algorithms (RBK, GRBK, and RGRBK) have modest standard deviations in the experiments. Overall, both theory and experiments suggest that the (deterministic) MWRBK method (Algorithm 7 ) seems to be the most attractive among the considered methods in terms of the number of iterations and computational time. Finally, we remark that in this paper we have considered matrix equations without noise. Kaczmarz type methods may also be particularly suitable for noisy right-hand sides C ; this is left for follow-up work. Conflict of interest Not applicable.