Block Kaczmarz Method with Inequalities

Jonathan Briskman, Deanna Needell

Introduction

The Kaczmarz method is an iterative algorithm for solving linear systems of equations. It is usually applied to large-scale overdetermined systems because of its simplicity and speed (but also converges in the underdetermined case to the least-norm solution under appropriate initial conditions). Each iteration projects onto the solution space corresponding to one row in the system, in a sequential fashion. Strohmer and Vershynin prove that when the rows are selected from a certain random distribution rather than sequentially, that the randomized method converges to the solution at a linear rate . The method has been applied to fields including image reconstruction, digital signal processing, and computer tomography . Leventhal and Lewis modify the randomized Kaczmarz method to apply to systems of linear equalities and inequalities , thereby extending results on the standard method in this setting (see e.g. and references therein). Unlike the traditional randomized algorithm which enforces a single constraint at each iteration, the block Kaczmarz approach recently analyzed by Needell and Tropp enforces multiple constraints simultaneously and thus offers computational advantages. Here we demonstrate convergence for a system of linear equalities and inequalities by combining a randomized block Kaczmarz method for the equalities with a randomized Kaczmarz algorithm for the inequalities. These results indicate that the block Kaczmarz method can be used for a system of equalities and inequalities, and in some cases may quicken convergence. We also consider the case of utilizing blocking in both the equalities and inequalities, although this can be detrimental unless the geometry of the system meets certain conditions.

where $\bm{A}$ is a real (or complex) $n\times d$ matrix, typically with $n\gg d$ .

We define the eigenvalues $\lambda_{\min}(\bm{A}),\ldots,\lambda_{\max}(\bm{A})$ of a matrix analogously. For convenience we will assume that each row $\bm{a_{i}}$ of $\bm{A}$ has unit norm, $\lVert{\bm{a_{i}}}\rVert_{2}=1$ , and we call such matrices standardized.

Now we consider a system of linear equalities and inequalities and denote by $S$ its non-empty set of feasible solutions. We thus consider the matrix $\bm{A}$ whose rows can be arranged such that

and we will write $I_{=}$ and $I_{\leq}$ to denote the row indices of $\bm{A}_{=}$ and $\bm{A}_{\leq}$ , respectively. Therefore, we ask that

We will assume that the set of rows $\{1,2,...,n\}$ is partitioned such that the first $n_{e}$ rows correspond to equalities, and the remaining $n_{i}=n-n_{e}$ rows to inequalities. Thus $\bm{A}_{=}$ is an $n_{e}\times d$ matrix and $\bm{A}_{\leq}$ is $n_{i}\times d$ .

The error bound for this system of linear inequalities uses the function $e:\textbf{R}^{n}\rightarrow\textbf{R}^{n}$ defined as in by

2. Details of Kaczmarz

The simple Kaczmarz method is an iterative algorithm that approximates a least-squares minimizer $\bm{x}_{\star}$ to the problem in (1.1). It takes an arbitrary initial approximation $\bm{x}_{0}$ , and at each iteration $j$ the current iterate is projected orthogonally onto the solution hyperplane $\{\left\langle\bm{a}_{i},\bm{x}\right\rangle=\bm{b}_{i}\}$ , using the update rule

where $i=j$ mod $n+1$ . With an unfortunate ordering of the rows, this method as-is can produce very slow convergence. However, it has been well known that using randomized selection often eliminates this effect . The randomized Kaczmarz method put forth by Strohmer and Vershynin uses a random selection method for the selection of row $i$ such that each row $i$ is selected with probability proportional to $\lVert{\bm{a}_{i}}\rVert_{2}^{2}$ . This randomization provides an algorithm that is both simple to analyze and enforce in many cases. In this paper we assume each row has unit norm, so each row is selected uniformly at random from $\{$ 1,…,n $\}$ in the simple randomized Kaczmarz approach. This assumption is both for notational convenience, and because the use of matrix pavings discussed below only hold for standardized matrices. In practice, one can employ pre-conditioning on non-standardized systems, or extend the construction of matrix pavings to non-standardized systems . Strohmer and Vershynin prove a linear rate of convergence for consistent systems that depends on the scaled condition number of $\bm{A}$ , and not on the number of equations $n$ ,

where $\bm{x}_{\star}$ is the solution to the consistent system (1.1) and $K=\|\bm{A}\|_{F}^{2}/\sigma^{2}_{\min}(\bm{A})$ denotes the scaled condition number. Needell extended this work to the inconsistent case and proves linear convergence to the least-squares solution within some fixed radius ,

where $\bm{e}=\bm{Ax_{\star}}-\bm{b}$ denotes the residual vector. Because the Kaczmarz method projects directly onto each solution hyperplane, such a convergence radius is unavoidable without adding a relaxation parameter.

The randomized Kaczmarz method can be adapted to the case of a linear system of equalities and inequalities described in (1.3). Leventhal and Lewis apply the Kaczmarz method to a consistent system of linear equalities and inequalities (here consistent simply means the feasible set $S$ is non-empty). At each iteration $j$ , the previous iterate only projects onto the solution hyperplane if the inequality is not already satisfied. If the inequality is satisfied for row $i$ selected at iteration $j$ $(\bm{a}_{i}^{T}\bm{x}\leq\bm{b}_{i})$ , the approximation $\bm{x}_{j}$ is set as $\bm{x}_{j-1}$ . The update rule for this algorithm is thus

This algorithm converges linearly in expectation , with

In order to bound the right hand side of this expression, the authors rely on a lemma due to Hoffman . This result states that for any system (1.3) with non-empty solution set $S$ , there exists a constant $L$ independent of $\bm{b}$ such that for all $\bm{x}$ ,

When $\bm{A}_{=}=\bm{A}$ is full column rank, the Hoffman constant is the inverse of the smallest singular value, $L=\sigma_{\min}^{-1}(\bm{A})$ .

which coincides with (1.5) for consistent systems of equalities.

3. Block Kaczmarz

A block variant of the randomized Kaczmarz method due to Elfving has been recently analyzed by Needell and Tropp and can improve the convergence rate in certain cases. The block Kaczmarz method first partitions the rows $\{1,...,n\}$ into $m$ blocks, denoted $\tau_{1},\ldots\tau_{m}$ . Instead of selecting one row per iteration as done with the simple Kaczmarz method, the block Kaczmarz algorithm chooses a block uniformly at random at each iteration. Thus the block Kaczmarz method enforces multiple constraints simultaneously. At each iteration, the previous iterate $\bm{x}_{j-1}$ is projected onto the solution space to $\bm{A}_{\tau}\bm{x}=\bm{b}_{\tau}$ , which enforces the set of equations in block $\tau$ . $\bm{A}_{\tau}$ and $\bm{b}_{\tau}$ are written as the row submatrix of $\bm{A}$ and the subvector of $\bm{b}$ indexed by $\tau$ respectively, yielding an iterative rule of

The pseudoinverse used in (1.9) returns the solution to the underdetermined least squares problem for a wide or square row submatrix $\bm{A}_{\tau}$ .

Depending on the characteristics of the submatrix $\bm{A}_{\tau}$ , the block method can provide better convergence than the simple method. If we assume that the submatrices $\bm{A}_{\tau}$ are well conditioned, the additional cost of computing their pseudo-inverse can be overcome by the gain in utilizing block multiplications (see our experiments in Section 4). In fact, if the blocks admit a fast multiply (for example if the matrix is built of DFT or circulant blocks), then the computational cost of the block iteration (1.9) is similar to the cost of the simple update rule in (1.4). Since the convergence depends heavily on the conditioning of each submatrix, one seeks partitions of the rows into blocks for which each block is well-conditioned. The notion of a row-paving allows one to do precisely that.

We define an ( $m$ , $\beta$ ) row paving The standard definition of a row paving also includes a constant $\alpha$ which serves as a lower bound to the smallest singular value. We ignore that parameter here since it will not be utilized. of matrix $\bm{A}$ as a partition $T=\{\tau_{1},...\tau_{m}\}$ of the row indices such that

The size of the paving, or number of blocks, is $m$ . The value of $\beta$ is the upper paving bound, which controls the spectral norms of the submatrices. Needell and Tropp show that these parameters determine the performance of the algorithm, with convergence for a consistent system admitting an $(m,\beta)$ paving given by

Therefore the convergence rate depends on the size $m$ and upper bound $\beta$ ; the algorithm’s performance improves with low values of $m$ and $\beta$ , and large $\sigma_{\min}^{2}(\bm{A})$ . The authors also prove convergence for inconsistent systems, with the same convergence rate and convergence radius which depends also on the minimum of all $\lambda_{\min}(\bm{A}_{\tau}\bm{A}_{\tau}^{*})$ , see for details.

Surprisingly, every standardized matrix admits a good row paving. The following result is due to which builds off the foundational work of .

For any $\delta\in(0,1)$ and standardized $n\times d$ matrix $\bm{A}$ , there is a row paving satisfying

Although this is an existential result, there are constructive methods to obtain such pavings, and for certain classes of matrices, they can even be obtained by a random partitioning of the rows .

With such a paving in tow, the convergence of (1.10) becomes

Although often comparable to the convergence rate for the simple method (1.5), numerical results confirm that the block method offers significant reduction in computation time due to the speed of matrix–vector multiplication (see e.g. ).

4. Contribution

This paper analyzes the system with matrix described in (1.2) using an algorithm with the block Kaczmarz approach for the equalities given by $\bm{A}_{=}$ and the simple method for the inequalities given by $\bm{A}_{\leq}$ . A paving is created for $\bm{A}_{=}$ , with the inequalities excluded. At each iteration, we select from $\bm{A}_{=}$ with a fixed probability $p$ and from $\bm{A}_{\leq}$ with probability $1-p$ . In the former case, we select a block $\tau$ from paving $T$ uniformly at random, and in the latter case we select a row $i$ of $\bm{A}_{\leq}$ uniformly at random. In the case of a block of equalities being selected, the algorithm proceeds by updating $\bm{x}_{j}$ using (1.9). When an inequality row is selected, $\bm{x}_{j}$ is updated using the rule (1.6). We prove that this method yields linear convergence to the solution set $S$ . We also include a discussion about paving both $\bm{A}_{=}$ and $\bm{A}_{\leq}$ , which identifies a geometric property of the system which allows for improved convergence by utilizing two pavings. We show that when this property is not satisfied, utilizing both pavings can be detrimental to convergence.

5. Organization

Section 2 lays out our main result, Theorem 2.1, and provides a proof. We discuss blocking the full matrix in Section 3 and Section 4 explains numerical experiments and results. We conclude with discussion and related work in Section 5.

Analysis of the Block Kaczmarz Algorithm for a System of Inequalities

In this section we analyze the convergence of the described method, which is detailed in Algorithm 2.1.

Notice that the probability of selecting a block of $\bm{A}_{=}$ is $\frac{\beta m}{n_{i}+\beta m}$ . This quantity corresponds to the relative size of $A_{=}$ in the system, where the size is measured in terms of the paving quantities $\beta m$ . This value may be difficult to compute precisely, and the simpler threshold of $n_{e}/n$ appears to also work well in practice. We provide no evidence that our selection of this threshold is most efficient, nor any more efficient than using one proportional to the number of equality rows $n_{e}$ . We find that this algorithm yields linear convergence in expectation with a rate that only depends on the number of inequalities $n_{i}$ , paving size $m$ , and upper bound $\beta$ .

Our main result is described in Theorem 2.1.

Remarks. 1. Note that when there are no block projections, no inequalities, or neither, Theorem 2.1 recovers the results of the standard randomized Kaczmarz for inequalities , the standard randomized block Kaczmarz method or the standard randomized Kaczmarz method , respectively. We thus view this result as a completely generalized convergence bound.

2. If we let $\rho_{s}$ and $\rho_{b}$ be the convergence rates of the simple and block methods for mixed systems, respectively, then by (1.8) and Theorem 2.1,

It is evident that our expected convergence rate will be faster per iteration than the simple method when $n_{i}+\beta m<n$ . Since $\beta$ can be chosen close to $1$ and $m<n_{e}$ is then number of rows in $\bm{A}_{=}$ , this holds quite easily.

3. Since a single iteration using a block $\bm{A}_{\tau}$ in general may cost more than an iteration utilizing a single row, it is more fair to compare per epoch, rather than per iteration. An epoch is typically the minimum number of iterations needed to visit each row of the matrix. When there are inequalities present that are already satisfied in a given iteration, that iteration may make no contribution and cost very little computationally. Thus the notion of epoch may be slightly skewed here, but if we ignore this subtlety the simple method will have approximately $n$ iterations per epoch, compared to $n_{i}+m$ iterations per epoch with the block method. The approximate per epoch convergence rates can thus be compared as

This result is similar to that found by Needell and Tropp , with the block convergence rate at best equal to that of the simple convergence rate when $\beta=1$ . However, as already noted, the block method is quite advantageous computationally.

Combining the paving result of Prop. 1.2 with Theorem 2.1 yields the following corollary.

Instate the assumptions and notation of Theorem 2.1 and let $\bm{A}_{=}$ be equipped with an $(m,\beta)$ row-paving as in Proposition 1.2. Then the iterates of Algorithm 2.1 satisfy

where $\gamma=\left(1-\frac{1}{L^{2}(n_{i}+C\|\bm{A}_{=}\|^{2}\log(1+n))}\right)$ and $C$ is some absolute constant.

Fix an iteration $j$ of Algorithm 2.1. We proceed as in and . First, we suppose that $q\leq\frac{\beta m}{n_{i}+\beta m}$ , so that a block $\tau$ of equalities is selected this iteration. Then writing $P_{S}$ as the orthogonal projection onto $S$ , we have $\bm{b}_{\tau}=\bm{A}_{\tau}P_{S}\bm{x}_{j-1}$ since $P_{S}\bm{x}_{j-1}\in S$ . We then have

Taking expectation (over the choice of the block $\tau$ , conditioned on previous choices), and using the fact that $\bm{A}_{\tau}^{\dagger}\bm{A}_{\tau}$ is an orthogonal projector, along with the properties of the paving yields

Since $d(\bm{x}_{j-1},S)=\lVert{\bm{x}_{j-1}-P_{S}\bm{x}_{j-1}}\rVert_{2}$ and $d(\bm{x}_{j},S)\leq\lVert{\bm{x}_{j}-P_{S}\bm{x}_{j-1}}\rVert_{2}$ , this means that

Next suppose that instead $i\in I_{\leq}$ is selected. Then since each row $\bm{a_{i}}$ has unit norm,

where the last line follows from the fact that $\langle\bm{a_{i}},P_{S}\bm{x}_{j-1}\rangle\leq b_{i}$ and $e(\bm{A}\bm{x}_{j-1}-\bm{b})_{i}\geq 0$ . Now taking expectation again we have

Combining these results and letting $E_{=}$ and $E_{\leq}$ denote the events that a block from $T$ and a row from $I_{\leq}$ is selected, respectively, we have

Since $p=\frac{\beta m}{\ n_{i}+\beta m}$ , we have $\frac{1-p}{n_{i}}=\frac{1}{n_{i}+\beta m}$ and we can simplify

where we have utilized the Hoffman bound (1.7) in the second inequality.

Utilizing independence of the random selections and recursing on this relation yields the desired result. ∎

A Discussion about Blocking Inequalities

It is natural to ask whether one can benefit by blocking both the equalities as above and also the inequalities, as described by Algorithm 3.2. Indeed, Section 4 will show dramatic improvements in computational time when the rows of $\bm{A}_{=}$ are paved and block projections as in Algorithm 2.1 are used. So can one benefit even more by paving also the rows of $\bm{A}_{\leq}$ ? The answer to this question heavily depends on the structure of the matrix $\bm{A}$ .

If we only consider $\bm{A}_{=}$ , a block projection as in (1.9) enforces all the equations indexed by $\tau$ to be satisfied. This is of course desirable when the rows indexed by $\tau$ correspond to equalities. Also, if a single inequality corresponding to row $i$ in $\bm{A}_{\leq}$ is not satisfied and we perform a single projection as in (1.4), we are again enforcing that inequality to hold with equality. However, this improves the estimation since in this case we know the solution set $S$ lies on the opposite side of the hyperplane $\{\bm{x}:\langle\bm{x},\bm{a_{i}}\rangle=b_{i}\}$ as the current estimation (see Figure 1 (a)).

On the other hand, if we employ a block projection as in (1.9) to a set of inequalities indexed by $\tau$ which are not satisfied by the current estimation $\bm{x}_{j-1}$ then we enforce all of them to hold with equality simultaneously. Depending on the geometry of the involved rows, this may result in an improved estimation or actually one much farther from the solution set. Of course, one might alternatively want to solve the convex program to project onto the intersection of the corresponding half-spaces, but we would like to maintain the efficiency and simplicity of the block Kaczmarz method.

As an illustrative example, Figure 1 (b) and (c) demonstrate two possible scenarios in two dimensions. Here, the solution space is a single point marked $S$ , and we draw two hyperplanes $H_{i_{1}}$ and $H_{i_{2}}$ where $H_{i}=\{\bm{x}:\langle\bm{a_{i}},\bm{x}\rangle=b_{i}\}$ . The yellow shaded regions denote areas where both inequalities hold true: $\{\bm{x}:\langle\bm{a}_{i_{1}},\bm{x}\rangle\leq b_{i_{1}}\text{ and }\langle\bm{a}_{i_{2}},\bm{x}\rangle\leq b_{i_{2}}\}$ . Notice that in (b), when the angle between $\bm{x}_{j-1}-\bm{x}_{j}$ and $\bm{s}-\bm{x}_{j}$ is obtuse, the orthogonal projection of estimation $\bm{x}_{j-1}$ onto their intersection is guaranteed to be closer to the solution set S. On the other hand, when that angle is acute we see exactly the opposite, as in (c). We can quantify this notion by the following definition.

In other words, the angle between $\bm{w}-\bm{z}$ and $\bm{s}$ (and thus $\bm{s}-\bm{z}$ ) is obtuse.

We will see that performing block projections on the inequalities in the system only makes sense when one can obtain an obtuse row paving. We will use $\bm{w}=\bm{x}_{j-1}$ , $\bm{z}=\bm{x}_{j}$ , and $\bm{s}\in S$ . Notice that if $i_{1},i_{2}\in\tau\in T$ , then the partition used in the system depicted in Figure 1 (c) does not constitute an obtuse row paving.

We conduct two simple experiments to demonstrate the different behavior of the algorithm. In all cases the matrix $\bm{A}$ is a $300\times 100$ matrix with standard normal entries, $100$ rows correspond to inequalities, and $\bm{b}$ is generated so that the solution set $S$ is non-empty. We measure the residual error which we define as $\lVert{e(\bm{A}\bm{x}_{j}-\bm{b})}\rVert_{2}$ . Figure 2 (a) shows the behavior of the block method with this matrix and a row paving obtained via a random row partition of $30$ blocks ( $10$ rows per block). This generation will create a matrix with paving that with very high probability is not an obtuse row paving. As Figure 2 demonstrates, the block method does not converge to a solution in this case. However, as Figure 2 (c) shows, the simple Kaczmarz method succeeds in identifying a point in the solution space. Next, we create a matrix in the exact same way, and create the same random row paving. Then, however, we iterate through every block in the paving corresponding to inequalities and if two rows $i$ and $k$ in a block satisfy $\langle\bm{a_{i}},\bm{a}_{k}\rangle>0$ , we replace row $\bm{a_{i}}$ with $-\bm{a_{i}}$ and entry $b_{i}$ with $-b_{i}$ . This guarantees every block in the paving yields a geometry like that shown in Figure 1 (b), and gives an obtuse row paving. Note that of course this changes the solution space as well so one cannot employ this strategy in general. We then add positive values to the entries in $\bm{b}$ corresponding to inequalities to ensure the solution set $S$ is non-empty. With this new system and paving, we again run the block method and see that the method now converges to a point in the solution set, as seen in Figure 2 (b).

With this definition we obtain the following result, whose proof can be found in the appendix.

Let $\bm{A}$ satisfy the assumptions of Theorem 2.1 and in addition have an obtuse $(m^{\prime},\beta^{\prime})$ row paving of $\bm{A}_{\leq}$ . Let $x_{1},\ldots$ denote the iterates of Algorithm 3.2. Then using the notation of Theorem 2.1,

Note that row pavings of standardized matrices can be obtained readily, often by random partitions , whereas obtuse row pavings may be much more challenging to obtain in general. Of course, by default the trivial paving which assigns each set $\tau$ to a single row always admits an obtuse row paving. We focus on Algorithm 2.1 which paves only $\bm{A}_{=}$ , and leave further analysis of Algorithm 3.2 and constructions of obtuse row pavings for future work.

Experiments

We use Matlab to run some experiments using random matrices to test the convergence of the block Kaczmarz method applied to a system of equalities and inequalities. In each experiment, we create a random $500$ by $100$ matrix $\bm{A}$ where each element is an independent standard normal random variable. Each entry is then divided by the norm of its row so that the matrix is standardized. The first 400 rows of matrix $\bm{A}$ compose $\bm{A}_{=}$ , and the remaining 100 rows are set as inequalities of $\bm{A}_{\leq}$ in the method described by (1.3). The experiments are run using the following procedure. For each of 100 trials,

Create matrix $\bm{A}$ in the manner described above.

Create $\bm{x}_{\star}$ where each entry is selected independently from a standard normal distribution. Set $\bm{b}=\bm{A}\bm{x}_{\star}$ .

Pave submatrix $\bm{A}_{=}$ into 16 blocks with 25 equalities per block by a random partitioning of the rows.

Set initial approximations $\bm{x}_{0}^{\text{block}}=\bm{x}_{0}^{\text{simp}}=\bm{A}^{*}\bm{b}$ .

If $q\leq\frac{n_{e}}{\ n}$ , choose block $\{1,...,m\}$ uniformly at random and update iterate $\bm{x}_{j}^{\text{block}}$ using (1.9). (Note that the threshold $\frac{n_{e}}{\ n}$ is different than that given in the main algorithm and theorem, but it is easier to calculate and seems to work fine in practice.)

Else, choose a row uniformly at random from $\{401,...,500\}$ and update iterate $\bm{x}_{j}^{\text{block}}$ using (1.6).

Update iterate $\bm{x}_{j}^{\text{simp}}$ using (1.6).

For both the simple and block algorithms, the median, minimum, and maximum values of the residual $\lVert{e(\bm{A}\bm{x}_{j}-\bm{b})}\rVert_{2}^{2}$ of the 100 trials are recorded for each iteration $j$ .

Figure 3 compares the performance of the block Kaczmarz method used in this paper and the standard Kaczmarz method described by Leventhal and Lewis . The plot in Figure 3 (a) compares convergence per iteration. As the block Kaczmarz method enforces multiple equalities per iteration, it is unsurprising that it performs better in this experiment. Figure 3 (b) displays the convergence of the two methods per epoch. The block Kaczmarz algorithm has an epoch of $m+n_{i}$ iterations, and the standard Kaczmarz method has an epoch of size $n$ . Here, to be fair we only count an iteration towards an epoch if the estimated solution $\bm{x}_{j}\neq\bm{x}_{j-1}$ . Thus in the case where a chosen inequality is already satisfied for iteration $j$ , this iteration does not count towards an epoch since no computation is being performed. We noticed, however, that whether or not we modified the count in this way, the behavior still produces results very similar to Figure 3. Once again the experiments yielded faster convergence with the block Kaczmarz approach. It is interesting to compare the results of Figure 3 (b) and those of Figure 2 (b) and (c). The per-epoch convergence of the methods and whether the block or standard appears faster varies slightly and depends on both the number of rows and columns. In general, the per-epoch convergence rates are reasonably comparable, as the analysis suggests. However, Figure 3 (c) compares the rate of convergence of the two algorithms by plotting the residual against the CPU time expended in the simulation. We believe that the ability to utilize efficient matrix–vector multiplication gives the method significantly improved convergence per second relative to the standard Kaczmarz algorithm, although other mechanisms may certainly be at work as well.

Conclusion and Related Work

The Kaczmarz algorithm was first proposed in . Kaczmarz demonstrated that the method converged to the solution of linear system $\bm{A}\bm{x}=\bm{b}$ for square, non-singular matrix $\bm{A}$ . Since then, the method has been utilized in the context of computer tomography as the Algebraic Reconstruction Technique (ART) . Empirical results suggested that randomized selection offered improved convergence over the cyclic scheme . Strohmer and Vershynin were the first to prove an expected linear convergence rate using a randomized Kaczmarz algorithm with specific random control. This result was extended by Needell to apply to inconsistent systems, which shows a linear convergence rate to within a fixed radius around the least-squares solution. Almost-sure convergence guarantees were recently proved by Chen and Powell . Zouzias and Freris analyze a modified version of the method in the inconsistent case, using a variant motivated by Popa to reduce the residual and thereby converge to the least squares solution. Relaxation parameters can also be introduced to obtain convergence to the least squares solution, see e.g. , and partially weighted sampling can lead to a tradeoff between convergence rate and radius . Liu, Wright, and Sridhar discuss applying a parallelized variant of the randomized Kaczmarz method, demonstrating that the convergence rate can be increased almost linearly by bounding the number of processors by a multiple of the number of rows of $\bm{A}$ .

The block Kaczmarz updating method was introduced by Elfving as a special case of the more general framework by Eggermont et.al. . The notion of using blocking in projection methods is certainly not new, and there is a large amount of literature on these types of methods, see e.g. and references therein. Needell and Tropp provide the first analysis showing an expected linear convergence rate which depends on the properties of the matrix $\bm{A}$ and of the submatrices $\bm{A_{\tau}}$ resulting from the paving, connecting pavings and the block Kaczmarz scheme. The use of specialized blocks appears elsewhere, in particular, the works of Popa use blocks with orthogonal rows that are beneficial for the block Kaczmarz method . Needell, Zhao, and Zouzias expand on the results from and to demonstrate convergence to the least-squares solution for an inconsistent system using the block Kaczmarz method. Again the block approach can yield faster convergence than the simple method.

The Kaczmarz method was first applied to a system of equalities and inequalities by Leventhal and Lewis , who also consider polynomial constraints with the method. They give a linear convergence rate to the feasible solution space $S$ , using $\lVert{\bm{A}}\rVert_{\rm F}^{2}$ and the Hoffman constant . We apply the block Kaczmarz scheme to the system described in , combining their result with that of Needell and Tropp to acquire a completely generalized result. We highlight several important complications which arise when attempting to apply the block scheme to inequalities. Nonetheless, whether a paving is used only partially or for the complete system, significant reduction in computational time can be achieved.

There are many interesting open problems related to the block Kazcmarz method and linear systems with inequalities. It has been well observed in the literature that selecting rows (or blocks) without replacement rather than with replacement as in the theoretical results leads to faster a convergence rate empirically . When selecting without replacement, independence between iterations vanishes, making a theoretical analysis more challenging. Secondly, it would be interesting to further investigate the use of obtuse row pavings. In systems with a large number of inequalities, the ability to pave the submatrix $\bm{A}_{\leq}$ with an obtuse row paving would lead to significantly faster convergence. In that case, one may like to identify a more general geometric property about the system that permits such pavings or an alternative formulation that offers convergence of the full block method.

Appendix A Proof of Theorem 3.2

Then since $\sigma$ is part of an obtuse paving, the angle between $\bm{x}_{j}-\bm{x}_{j-1}$ and $\bm{s}-\bm{x}_{j-1}$ must be obtuse. There thus exists a point $\bm{t}$ on the line segment $L=\{\gamma\bm{x}_{j-1}+(1-\gamma)\bm{s}:0\leq\gamma\leq 1\}$ such that $\bm{x}_{j-1}-\bm{x}_{j}$ and $\bm{t}-\bm{x}_{j}$ are orthogonal (see Figure 4).

Now since $\bm{t}\in L$ , we have $\lVert{\bm{t}-\bm{x}_{j-1}}\rVert_{2}\leq\lVert{\bm{x}_{j-1}-\bm{s}}\rVert_{2}$ , and thus letting $\theta$ denote the angle between $\bm{x}_{j}-\bm{x}_{j-1}$ and $\bm{t}-\bm{x}_{j-1}$ (see Figure 4), we have

By the definition of $\bm{x}_{j}$ , this means that

Using this along with the paving properties we see that

Thus, taking expectation (over the choice of $\tau^{\prime}$ , conditioned on previous choices), yields

Combining this with (2) and letting $E_{=}$ and $E_{\leq}$ denote the events that a block from $T$ and a block from $T^{\prime}$ is selected, respectively, we have

Since $p=\frac{\beta m}{\beta^{\prime}m^{\prime}+\beta m}$ , we have $\frac{1-p}{\beta^{\prime}m^{\prime}}=\frac{1}{\beta^{\prime}m^{\prime}+\beta m}$ and we can simplify