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))trueSince 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.18797Note 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 = 100BenchmarkTools.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 = 100BenchmarkTools.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.