Efficient Kaczmarz

Unlike many of the other solvers provided by RegularizedLeastSquares.jl, the Kaczmarz method does not utilize a matrix-vector product with the operator $\mathbf{A}$ nor the normal operator $\mathbf{A*A}$. Instead, it uses the rows of $\mathbf{A}$ to update the solution iteratively. Efficient Kaczmarz implementation therefore require very efficient dot products with the rows of $\mathbf{A}$. In RegularizedLeastSquares.jl, this is achieved with the dot_with_matrix_row function.

using RegularizedLeastSquares
A = randn(256, 256)
x = randn(256)
b = A*x;

The dot_with_matrix_row function calculates the dot product between a row of A and the current approximate solution of x:

row = 1
isapprox(RegularizedLeastSquares.dot_with_matrix_row(A, x, row), sum(A[row, :] .* x))
true

Since in Julia, dense arrays are stored in column-major order, such a row-based operation is quite inefficient. A workaround is to transpose the matrix then pass it to a Kaczmarz solver.

At = collect(transpose(A))
A_eff = transpose(At)
256×256 transpose(::Matrix{Float64}) with eltype Float64:
 -1.80557    0.313329   -0.667699   …  -0.618023   -1.24444    -2.04875
  1.08727   -2.22076    -1.20682       -0.708024    0.360774    0.250382
 -1.33112    0.0414042   1.86394        0.0792032   0.12826     0.526062
 -0.553248   2.16309    -0.777423      -1.35159    -1.51858     0.327812
  0.24652   -0.0155911  -0.239541       0.350716    1.07311    -0.0804484
  0.727163   1.62074    -0.673152   …  -0.847237   -0.626463    0.491774
  1.38745   -0.562742   -1.46977       -0.440028   -1.07327     0.230239
  1.85069   -0.459385    0.118673       0.86236     1.23117    -1.08668
 -0.770242  -0.392056   -0.234461      -0.12238    -1.37828    -0.0346693
  1.21956    1.59021     0.243209      -1.6744      0.307374    0.694154
  ⋮                                 ⋱                           ⋮
  0.825603   0.988754   -0.506474       0.128337   -0.525212    0.190284
  0.701102  -0.636687    1.35002       -0.307082   -1.20817    -2.1507
 -1.42285    0.417204    1.25446        1.09562    -0.335862   -1.72348
 -0.647665   0.935455    0.596153   …  -1.17693     0.713277   -0.135372
  1.48149   -0.461158   -1.02821       -1.06419     0.544962    0.316491
  0.852773  -0.105748   -0.0078154     -0.0923463   0.800994    0.334433
  1.571     -1.14967     0.343052      -1.02449    -1.4077     -0.361919
 -1.68988    1.90363     0.182456      -0.754418    0.38491     1.00596
  0.349849  -0.83696    -1.85303    …   1.25512     0.0537507   1.18797

Note that the transpose function can return a lazy transpose object, so we first collect the transpose into a dense matrix. Then we transpose it again to get the efficient representation of the matrix.

We can compare the performance using the BenchmarkTools.jl package. First for the original matrix:

using BenchmarkTools
solver = createLinearSolver(Kaczmarz, A; reg = L2Regularization(0.0001), iterations=100)
@benchmark solve!(solver, b) samples = 100
BenchmarkTools.Trial: 100 samples with 1 evaluation per sample.
 Range (min … max):  28.065 ms … 28.293 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     28.166 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   28.166 ms ± 45.442 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                    ▂█    ▅▂▅ ▂ ▂▅██▂  ▂     ▅ █        ▂   ▂  
  ▅▁▁▅▅▁█▅█▅▁▁▅▅██▁▅██▁▅█▅███████████▅███▅█▁▁███▅▅▁▁▁▁█▅█▁▁▁█ ▅
  28.1 ms         Histogram: frequency by time        28.3 ms <

 Memory estimate: 17.30 KiB, allocs estimate: 504.

And then for the efficient matrix:

solver_eff = createLinearSolver(Kaczmarz, A_eff; reg = L2Regularization(0.0001), iterations=100)
@benchmark solve!(solver_eff, b) samples = 100
BenchmarkTools.Trial: 100 samples with 1 evaluation per sample.
 Range (min … max):  1.823 ms …  1.944 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     1.859 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   1.863 ms ± 22.959 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

        ▁█  █▆▃▃▃▆ ▁█▃▁▃ ▃▁ ▁ ▆   ▁▁                          
  ▄▁▄▁▁▁██▇▇██████▇█████▄██▁█▄█▄▁▇██▄▁▄▁▁▇▁▁▁▁▁▁▁▁▁▁▄▄▁▁▁▁▁▇ ▄
  1.82 ms        Histogram: frequency by time        1.93 ms <

 Memory estimate: 17.31 KiB, allocs estimate: 505.

We can also combine the efficient matrix with a weighting matrix, as is shown in the Weighting example.

Custom operators need to implement the dot_with_matrix_row function to be used with the Kaczmarz solver. Ideally, such an implementation is allocation free.


This page was generated using Literate.jl.