An index-free way to take the gradient of a neural network

Taking the derivative of the loss function of a neural network can be quite cumbersome. Even taking the derivative of a single layer in a neural network often results in expressions cluttered with indices. In this post I’d like to show an index-free way to do it.

Consider the map where is the weight matrix, is the bias, is the input, and is the activation function. Usually represents both a scalar function (i.e. mapping ) and the function mapping which applies in each coordinate. In training neural networks, we would try to optimize for best parameters and . So we need to take the derivative with respect to and . So we consider the map

This map is a concatenation of the map and and since the former map is linear in the joint variable , the derivative of should be pretty simple. What makes the computation a little less straightforward is the fact the we are usually not used to view matrix-vector products as linear maps in but in . So let’s rewrite the thing:

There are two particular notions which come in handy here: The Kronecker product of matrices and the vectorization of matrices. Vectorization takes some given columnwise and maps it by

The Kronecker product of matrices and is a matrix in

We will build on the following marvelous identity: For matrices , , of compatible size we have that

Why is this helpful? It allows us to rewrite

So we can also rewrite

So our map mapping can be rewritten as

mapping . Since is just a concatenation of applied coordinate wise and a linear map, now given as a matrix, the derivative of (i.e. the Jacobian, a matrix in ) is calculated simply as

While this representation of the derivative of a single layer of a neural network with respect to its parameters is not particularly simple, it is still index free and moreover, straightforward to implement in languages which provide functions for the Kronecker product and vectorization. If you do this, make sure to take advantage of sparse matrices for the identity matrix and the diagonal matrix as otherwise the memory of your computer will be flooded with zeros.

Now let’s add a scalar function (e.g. to produce a scalar loss that we can minimize), i.e. we consider the map

The derivative is obtained by just another application of the chain rule:

If we want to take gradients, we just transpose the expression and get

Note that the right hand side is indeed vector in and hence, can be reshaped to a tupel of an matrix and an vector.

A final remark: the Kronecker product is related to tensor products. If and represent linear maps and , respectively, then represents the tensor product of the maps, . This relation to tensor products and tensors explains where the tensor in TensorFlow comes from.

 

The fundamental theorem of optimal transport

 

The problem of optimal transport of mass from one distribution to another can be stated in many forms. Here is the formulation going back to Kantorovich: We have two measurable sets and , coming with two measures and . We also have a function which assigns a transport cost, i.e. is the cost that it takes to carry one unit of mass from point to . What we want is a plan that says where the mass in should be placed in (or vice versa). There are different ways to formulate this mathematically.

A simple way is to look for a map which says that thet mass in should be moved to . While natural, there is a serious problem with this: What if not all mass at should go to the same point in ? This happens in simple situations where all mass in sits in just one point, but there are at least two different points in where mass should end up. This is not going to work with a map as above. So, the map is not flexible enough to model all kinds of transport we may need.

What we want is a way to distribute mass from one point in to the whole set . This looks like we want maps which map points in to functions on , i.e. something like where stands for some set of functions on . We can de-curry this function to some by . That’s good in principle, be we still run into problems when the target mass distribution is singular in the sense that is a “continuous” set and there are single points in that carry some mass according to . Since we are in the world of measure theory already, the way out suggests itself: Instead of a function on we look for a measure on as a transport plan.

The demand that we should carry all of the mass in to reach all of is formulated by marginals. For simplicity we just write these constraints as

(with the understanding that the first equation really means that for all continuous function it holds that ).

This leads us to the full transport problem

There is the following theorem which characterizes optimality of a plan and which is the topic of this post:

Theorem 1 (Fundamental theorem of optimal transport) Under some technicalities we can say that a plan which fulfills the marginal constraints is optimal if and only if one of the following equivalent conditions is satisfied:

1. The support of is -cyclically monotone.
2. There exists a -concave function such that its -superdifferential contains the support of , i.e. .

 

A few clarifications: The technicalities involve continuity, integrability, and boundedness conditions of and integrability conditions on the marginals. The full theorem can be found as Theorem 1.13 in A user’s guide to optimal transport by Ambrosio and Gigli. Also the notions -cyclically monotone, -concave and -superdifferential probably need explanation. We start with a simpler notion: -monotonicity:

Definition 2 A set is -monotone, if for all it holds that

 

If you find it unclear what this has to do with monotonicity, look at this example:

Example 1 Let and let be the usual scalar product. Then -monotonicity is the condition that for all it holds that

which may look more familiar. Indeed, when and are subset of the real line, the above conditions means that the set somehow “moves up in ” if we “move right in ”. So -monotonicity for is something like “monotonically increasing”. Similarly, for , -monotonicity means “monotonically decreasing”.

You may say that both and are strange cost functions and I can’t argue with that. But here comes: ( being the euclidean norm) seems more natural, right? But if we have a transport plan for this for some marginals and we also have

i.e., the transport cost for differs from the one for only by a constant independent of , so may well use the latter.

The fundamental theorem of optimal transport uses the notion of -cyclical monotonicity which is stronger that just -monotonicity:

Definition 3 A set is -cyclically monotone, if for all , and all permutations of it holds that

 

For we get back the notion of -monotonicity.

Definition 4 A function is -concave if there exists some function such that

 

This definition of -concavity resembles the notion of convex conjugate:

Example 2 Again using we get that a function is -concave if

and, as an infimum over linear functions, is clearly concave in the usual way.

Definition 5 The -superdifferential of a -concave function is

where is the -conjugate of defined by

 

Again one may look at and observe that the -superdifferential is the usual superdifferential related to the supergradient of concave functions (there is a Wikipedia page for subgradient only, but the concept is the same with reversed signs in some sense).

Now let us sketch the proof of the fundamental theorem of optimal transport: \medskip

Proof (of the fundamental theorem of optimal transport). Let be an optimal transport plan. We aim to show that is -cyclically monotone and assume the contrary. That is, we assume that there are points and a permutation such that

We aim to construct a such that is still feasible but has a smaller transport cost. To do so, we note that continuity of implies that there are neighborhoods of and of such that for all and it holds that

We use this to construct a better plan : Take the mass of in the sets and shift it around. The full construction is a little messy to write down: Define a probability measure on the product as the product of the measures . Now let and be the projections of onto and , respectively, and set

where denotes the pushforward of measures. Note that the new measure is signed and that fulfills

1. is a non-negative measure
2. is feasible, i.e. has the correct marginals
3. 

which, all together, gives a contradiction to optimality of . The implication of item 1 to item 2 of the theorem is not really related to optimal transport but a general fact about -concavity and -cyclical monotonicity (c.f.~this previous blog post of mine where I wrote a similar statement for convexity). So let us just prove the implication from item 2 to optimality of : Let fulfill item 2, i.e. is feasible and is contained in the -superdifferential of some -concave function . Moreover let be any feasible transport plan. We aim to show that . By definition of the -superdifferential and the -conjugate we have

Since by assumption, this gives

which shows the claim.

Corollary 6 If is a measure on which is supported on a -superdifferential of a -concave function, then is an optimal transport plan for its marginals with respect to the transport cost .

 

 

Best stepsizes for Douglas-Rachford for Lipschitz + strongly montone

This is a short follow up on my last post where I wrote about the sweet spot of the stepsize of the Douglas-Rachford iteration. For the case -Lipschitz + -strongly monotone, the iteration with stepsize converges linear with rate

Here is animated plot of this contraction factor depending on and and acts as time variable:

What is interesting is, that this factor has increasing or decreasing in depending on the values of and .

For each pair there is a best and also a smallest contraction factor . Here are plots of these quantities:

Comparing the plot of te optimal contraction factor to the animated plot above, you see that the right choice of the stepsize matters a lot.

 

The sweet spot of the Douglas-Rachford iteration

I blogged about the Douglas-Rachford method before here and here. It’s a method to solve monotone inclusions in the form

with monotone multivalued operators from a Hilbert space into itself. Using the resolvent and the reflector , the Douglas-Rachford iteration is concisely written as

The convergence of the method has been clarified is a number of papers, see, e.g.

Lions, Pierre-Louis, and Bertrand Mercier. “Splitting algorithms for the sum of two nonlinear operators.” SIAM Journal on Numerical Analysis 16.6 (1979): 964-979.

for the first treatment in the context of monotone operators and

Svaiter, Benar Fux. “On weak convergence of the Douglas–Rachford method.” SIAM Journal on Control and Optimization 49.1 (2011): 280-287.

for a recent very general convergence result.

Since is monotone if is monotone and , we can introduce a stepsize for the Douglas-Rachford iteration

It turns out, that this stepsize matters a lot in practice; too small and too large stepsizes lead to slow convergence. It is a kind of folk wisdom, that there is “sweet spot” for the stepsize. In a recent preprint Quoc Tran-Dinh and I investigated this sweet spot in the simple case of linear operators and and this tweet has a visualization.

A few days ago Walaa Moursi and Lieven Vandenberghe published the preprint “Douglas-Rachford splitting for a Lipschitz continuous and a strongly monotone operator” and derived some linear convergence rates in the special case they mention in the title. One result (Theorem 4.3) goes as follows: If is monotone and Lipschitz continuous with constant and is maximally monotone and -strongly monotone, than the Douglas-Rachford iterates converge strongly to a solution with a linear rate

This is a surprisingly complicated expression, but there is a nice thing about it: It allows to optimize for the stepsize! The rate depends on the stepsize as

and the two plots of this function below show the sweet spot clearly.

 

If one knows the Lipschitz constant of and the constant of strong monotonicity of , one can minimize to get on optimal stepsize (in the sense that the guaranteed contraction factor is as small as possible). As Moursi and Vandenberghe explain in their Remark 5.4, this optimization involves finding the root of a polynomial of degree 5, so it is possible but cumbersome.

Now I wonder if there is any hope to show that the adaptive stepsize Quoc and I proposed here (which basically amounts to in the case of single valued – note that the role of and is swapped in our paper) is able to find the sweet spot (experimentally it does).
<p

 

The Douglas-Rachford method for convex-concave saddle point problem without ever solving a linear system

Consider the saddle point problem

(where I omit all the standard assumptions, like convexity, continuity ans such…). Fenchel-Rockafellar duality says that solutions are characterized by the inclusion

Noting that the operators

are both monotone, we may apply any of the splitting methods available, for example the Douglas-Rachford method. In terms of resolvents

this method reads as

For the saddle point problem, this iteration is (with )

The first two lines involve proximal steps and we assume that they are simple to implement. The last line, however, involves the solution of a large linear system. This can be broken down to a slightly smaller linear system involving the matrix as follows: The linear system equals

Plugging from the second equation into the first gives

Denoting this can be written as

and the second equation is just

This gives the overall iteration

This is nothing else than using the Schur complement or factoring as

and has been applied to imaging problems by O’Connor and Vandenberghe in “Primal-Dual Decomposition by Operator Splitting and Applications to Image Deblurring” (doi). For many problems in imaging, the involved inversion may be fairly easy to perform (if is the image gradient, for example, we only need to solve an equation with an operator like and appropriate boundary conditions). However, there are problems where this inversion is a problem.

I’d like to show the following trick to circumvent the matrix inversion, which I learned from Bredies and Sun’s “Accelerated Douglas-Rachford methods for the solution of convex-concave saddle-point problems”: Here is a slightly different saddle point problem

We added a new dual variable , which is forced to be zero by the additional indicator functional . Hence, the additional bilinear term is also zero, and we see that is a solution of (1) if and only if is a solution of (2). In other words: The problem just looks differently, but is, in essence, the same as before.

Now let us write down the Douglas-Rachford iteration for (2). We write this problem as

with

Writing down the Douglas-Rachford iteration gives

Switching back to variables without a tilde, we get, using ,

First not that throughout the iteration and from the last line of the linear system we get that

which implies that

Thus, both variables and disappear in the iteration. Now we rewrite the remaining first two lines of the linear system as

Again denoting , solving the second equation for and plugging the result in the first gives

To eliminate we add on both sides and get

In total we obtain the following iteration:

and note that only the third line changed.

Since the above works for any matrix , we have a lot of freedom. Let us see, that it is even possible to avoid any inversion whatsoever: We would like to choose in a way that for some positive . This is equivalent to

As soon as the right hand side is positive definite, Cholesky decomposition shows that such an exists, and this happens if . Further note, that we do need in any way, but only , and we can perform the iteration without ever solving any linear system since the third row reads as

 

The origin of the Douglas-Rachford iteration

I blogged about the Douglas-Rachford method before and in this post I’d like to dig a bit into the history of the method.

As the name suggests, the method has its roots in a paper by Douglas and Rachford and the paper is

Douglas, Jim, Jr., and Henry H. Rachford Jr., “On the numerical solution of heat conduction problems in two and three space variables.” Transactions of the American mathematical Society 82.2 (1956): 421-439.

At first glance, the title does not suggest that the paper may be related to monotone inclusions and if you read the paper you’ll not find any monotone operator mentioned. So let’s start and look at Douglas and Rachford’s paper.

1. Solving the heat equation numerically

So let us see, what they were after and how this is related to what is known as Douglas-Rachford splitting method today.

Indeed, Douglas and Rachford wanted to solve the instationary heat equation

with Dirichlet boundary conditions (they also considered three dimensions, but let us skip that here). They considered a rectangular grid and a very simple finite difference approximation of the second derivatives, i.e.

(with modifications at the boundary to accomodate the boundary conditions). To ease notation, we abbreviate the difference quotients as operators (actually, also matrices) that act for a fixed time step

With this notation, our problem is to solve

in time.

Then they give the following iteration:

 

 

(plus boundary conditions which I’d like to swipe under the rug here). If we eliminate from the first equation using the second we get

 

This is a kind of implicit Euler method with an additional small term . From a numerical point of it has one advantage over the implicit Euler method: As equations (1) and (2) show, one does not need to invert in every iteration, but only and . Remember, this was in 1950s, and solving large linear equations was a much bigger problem than it is today. In this specific case of the heat equation, the operators and are in fact tridiagonal, and hence, solving with and can be done by Gaussian elimination without any fill-in in linear time (read Thomas algorithm). This is a huge time saver when compared to solving with which has a fairly large bandwidth (no matter how you reorder).

How do they prove convergence of the method? They don’t since they wanted to solve a parabolic PDE. They were after stability of the scheme, and this can be done by analyzing the eigenvalues of the iteration. Since the matrices and are well understood, they were able to write down the eigenfunctions of the operator associated to iteration (3) explicitly and since the finite difference approximation is well understood, they were able to prove approximation properties. Note that the method can also be seen, as a means to calculate the steady state of the heat equation.

We reformulate the iteration (3) further to see how is actually derived from : We obtain

 

2. What about monotone inclusions?

What has the previous section to do with solving monotone inclusions? A monotone inclusion is

with a monotone operator, that is, a multivalued mapping from a Hilbert space to (subsets of) itself such that for all and and it holds that

We are going to restrict ourselves to real Hilbert spaces here. Note that linear operators are monotone if they are positive semi-definite and further note that monotone linear operators need not to be symmetric. A general approach to the solution of monotone inclusions are so-called splitting methods. There one splits additively as a sum of two other monotone operators. Then one tries to use the so-called resolvents of and , namely

to obtain a numerical method. By the way, the resolvent of a monotone operator always exists and is single valued (to be honest, one needs a regularity assumption here, namely one need maximal monotone operators, but we will not deal with this issue here).

The two operators and from the previous section are not monotone, but and are, so the equation is a special case of a montone inclusion. To work with monotone operators we rename

and write the iteration~(4) in terms of monotone operators as

i.e.

Using and we rewrite this in terms of resolvents as

This is not really applicable to a general monotone inclusion since there and may be multi-valued, i.e. the term is not well defined (the iteration may be used as is for splittings where is monotone and single valued, though).

But what to do, when both and and are multivaled? The trick is, to introduce a new variable . Plugging this in throughout leads to

We cancel the outer and use to get

and here we go: This is exactly what is known as Douglas-Rachford method (see the last version of the iteration in my previous post). Note that it is not that converges to a solution, but , so it is convenient to write the iteration in the two variables

The observation, that these splitting method that Douglas and Rachford devised for linear problems has a kind of much wider applicability is due to Lions and Mercier and the paper is

Lions, Pierre-Louis, and Bertrand Mercier. “Splitting algorithms for the sum of two nonlinear operators.” SIAM Journal on Numerical Analysis 16.6 (1979): 964-979.

Other, much older, splitting methods for linear systems, such as the Jacobi method, the Gauss-Seidel method used different properties of the matrices such as the diagonal of the matrix or the upper and lower triangluar parts and as such, do not generalize easily to the case of operators on a Hilbert space.

 

How to obtain a finite primal dual gap

Consider a convex optimization problem of the form

with convex and and matrix . (We formulate everything quite loosely, skipping over details like continuity and such, as they are irrelevant for the subject matter). Optimization problems of this type have a specific type of dual problem, namely the Fenchel-Rockafellar dual, which is

and under certain regularity conditions it holds that the optimal value of the dual equals the the objective value of the primal and, moreover, that a pair is both primal and dual optimal if and only if the primal dual gap is zero, i.e. if and only if

Hence, it is quite handy to use the primal dual gap as a stopping criteria for iterative methods to solve these problems. So, if one runs an algorithm which produces primal iterates and dual iterates one can monitor

and stop if the value falls below a desired tolerance.

There is some problem with this approach which appears if the method produces infeasible iterates in the sense that one of the four terms in is actually . This may be the case if or are not everywhere finite or, loosely speaking, have linear growth in some directions (since then the respective conjugate will not be finite everywhere). In the rest of the post, I’ll sketch a general method that can often solve this particular problem.

For the sake of simplicity, consider the following primal dual algorithm

(also know as primal dual hybrid gradient method or Chambolle-Pock’s algorithm). It converges as soon as .

While the structure of the algorithm ensures that and are always finite (since always ), is may be that or are indeed infinite, rendering the primal dual gap useless.

Let us assume that the problematic term is . Here is a way out in the case where one can deduce some a-priori bounds on , i.e. a bounded and convex set with . In fact, this is often the case (e.g. one may know a-priori that there exist lower bounds and upper bounds , i.e. it holds that ). Then, adding these constraints to the problem will not change the solution.

Let us see, how this changes the primal dual gap: We set where is the set which models the bound constraints. Since is a bounded convex set and is finite on , it is clear that

is finite for every . This leads to a finite duality gap. However, one should also adapt the prox operator. But this is also simple in the case where the constraint and the function are separable, i.e. encodes bound constraints as above (in other words ) and

Here it holds that

and it is simple to see that

i.e., only uses the proximal operator of and project onto the constraints. For general , this step may be more complicated.

One example, where this makes sense is denoising which can be written as

Here we have

The guy that causes problems here is which is an indicator functional and indeed will usually be dual infeasible. But since is an image with a know range of gray values one can simple add the constraints to the problem and obtains a finite dual while still keeping a simple proximal operator. It is quite instructive to compute in this case.

 

Workshop on the Interface of Statistics and Optimization

Here is a small signal boost for the

to  be held at Duke University, Durham, North Carolina from Feb 8 to Feb 10 2017. The workshop is part of the long-year program on optimization currently taking place at the Statistical and Applied Mathematical Sciences Institute (SAMSI).

There will be a lineup of invited speakers from the forefront of Statistics and Optimization each of which has made influential contributions to the other field as well. The planning is still ongoing, and hence, the list of speakers will grow some.

If you can’t make it to North Carolina next February, still mark the date since the talks will be broadcasted via the net and (if tech works out) you may even participate in the Q&A sessions after the talks via your computer.

 

Sparse reconstruction with ℓ∞ constraints

Last week Christoph Brauer, Andreas Tillmann and myself uploaded the paper A Primal-Dual Homotopy Algorithm for -Minimization with -Constraints to the arXiv (and we missed being the first ever arXiv-paper with a non-trivial five-digit identifier by twenty-something papers…). This paper specifically deals with the optimization problem

where and are a real matrix and vector, respecively, of compatible size. While the related problem with constraint has been addressed quite often (and the penalized problem is even more popular) there is not much code around to solve this specific problem. Obvious candidates are

• Linear optimization: The problem can be recast as a linear program: The constraint is basically linear already (rewriting it with help of the ones vector as , ) and for the objective one can, for example, perform a variable split , and then write .
• Splitting methods: The problem is convex problem of the form with

  

  and hence, several methods for these kind of problem are available, such as the alternating direction method of multipliers or the Chambolle-Pock algorithm.

The formulation as linear program has the advantage that one can choose among a lot of highly sophisticated software tools and the second has the advantage that the methods are very easy to code, usually in just a few lines. Drawbacks are, that both methods do exploit too much specific structure of the problem.

Application of the problem with constraint are, for example:

• The Dantzig selector, a statistical estimation technique, were the problem is

  

• Sparse dequantization as elaborated here by Jacques, Hammond and Fadili and applied here to de-quantizaton of speech signals by Christoph, Timo Gerkmann and myself.

We wanted to see if one of the most efficient methods known for sparse reconstruction with penalty, namely the homotopy method, can be adapted to this case. The homotopy method for builds on the observation that the solution for is zero and that the set of solutions , parameterized by the parameter , is piecewise linear. Hence, on can start from , calculate which direction to go, how far the breakpoint is away, go there and start over. I’ve blogged on the homotopy method here already and there you’ll find some links to great software packages, but also the fact that there can be up to exponentially many breakpoints. However, in practice the homotopy method is usually blazingly fast and with some care, can be made numerically stable and accurate, see, e.g. our extensive study here (and here is the optimization online preprint).

The problem with constraint seems similar, especially it is clear that for , is a solution. It is also not so difficult to see that there is a piecewise linear path of solutions . What is not so clear is, how it can be computed. It turned out, that in this case the whole truth can be seen when the problem is viewed from a primal-dual viewpoint. The associated dual problem is

and a pair is primal and dual optimal if and only if

(where denotes the sign function, multivalued at zero, giving there). One can note some things from the primal-dual optimality system:

• You may find a direction such that stays primal-dual optimal for the constraint for small ,
• for a fixed primal optimal there may be several dual optimal .

On the other hand, it is not that clear which of the probably many dual optimal allows to find a new direction such that with stay primal optimal when reducing . In fact, it turned out that, at a breakpoint, a new dual variable needs to be found to allow for the next jump in the primal variable. So, the solution path is piecewise linear in the primal variable, but piecewise constant in the dual variable (a situation similar to the adaptive inverse scale space method).

What we found is, that some adapted theorem of the alternative (a.k.a. Farkas’ Lemma) allows to calculate the next dual optimal such that a jump in will be possible.

What is more, is that the calculation of a new primal or dual optimal point amounts to solving a linear program (in contrast to a linear system for homotopy). Hence, the trick of up- and downdating a suitable factorization of a suitable matrix to speed up computation does not work. However, one can somehow leverage the special structure of the problem and use a tailored active set method to progress through the path. Our numerical tests indicated is that the resulting method, which we termed -Houdini, is able to solve moderately large problems faster than a commercial LP-solver (while also not only solving the given problem, but calculating the whole solution path on the fly) as can be seen from this table from the paper:

The code of -Houdini is on Christoph’s homepage, you may also reproduce the data in the above table with your own hardware.

 

The randomized sparse Kaczmarz method also converges linearly

Yesterday I uploaded the paper “Linear convergence of the Randomized Sparse Kaczmarz Method” by Frank Schöpfer and myself to the arXiv.

Recall that the Kaczmarz method for linear systems

iterates

where is the -th row of , is the th entry of and the index is chosen according to some rule. We could, e.g. choose the rows in a cyclic manner, i.e. starting with the first row, proceeding to the next row and once we came to the last row we would start over from the first again. It is known (and probably proved by Kaczmarz himself) that the method converges to a solution of whenever the system has a solution. Moreover, it easy to see that we converge to the minimum norm solution in case of underdetermined systems when the method is initialized with zero. This is due to the fact that the whole iteration takes place in the range space of .

In this and this paper we proposed a simple modification of the Kaczmarz method, that makes it converge to sparse solutions. The modification is simply

where is the soft thresholding function. In this paper we proved that this variant converges, when initialized with zero and for a consistent system, to the solution of

For not too small values of this is indeed a sparse solution of and Frank also proved that there is a threshold such that for larger than this threshold the solution is also the minimum solution.

In general, convergence rates for the Kaczmarz method (and its sparse variant) are hard to prove. To convince oneself of this fact note that the convergence speed can drastically change if the rows of the system are reordered. The situation changes if one uses a randomization of the sparse Kaczmarz method where, in each iteration, a row is chose at random. Strohmer and Vershynin proved that this randomization leads to linear convergence rate. In the above mentioned paper we were able to prove the same result for the randomized sparse Kaczmarz method. While this sounds like an obvious generalization, the methods we use are totally different. While the linear convergence of the randomized Kaczmarz method can be proven in a few lines(well, probably one page) using only very basic tools, we need, among other things, quite intricate error bounds for Bregman projections w.r.t. piecewise linear-quadratic convex functions.

In fact, the linear convergence can be observed in practice and we illustrate the usefulness of the randomization and also the “sparsification” on some examples in the paper. For example the following figure shows the decay of the residual for the the randomized Kaczmarz method (black), the randomized sparse Kaczmarz method (red) and the randomized sparse Kaczmarz method with exact steps (green) which I did not explain here.

More details are in the paper…