# Incluisive Electron Scattering in the Quasielastic Region with KIDS Density
Functional

Hana Gil  Center for Extreme Nuclear Matter, Korea University, Seoul 02841,
Korea  Chang Ho Hyun  Department of Physics Education, Daegu University,
Gyeongsan 38453, Korea  Kyungsik Kim<EMAIL_ADDRESS>School of Liberal
Arts and Science, Korea Aerospace University, Goyang 10540, Korea

###### Abstract

With the framework of KIDS (Korea-IBS-Daegu-SKKU) density functional model,
the isoscalar and isovector effective masses of nucleon and the effect of
symmetry energy in nuclear medium are investigated in inclusive
$(e,e^{\prime})$ reaction in quasielastic region. The effective masses are
varied in the range $(0.7\sim 1.0)M$ with free nucleon mass $M$, and the
symmetry energy is varied within the uncertainty allowed by nuclear data and
neutron star observation. The wave functions of nucleons inside target nucleus
are generated by solving Hartree-Fock equation with adjusting equation of
state, binding energy and radius of various stable nuclei, and effective mass
of nucleon in the KIDS model. With the obtained wave functions, we calculate
the differential cross section for the inclusive $(e,e^{\prime})$ reaction and
compare the theoretical results with Bates, Saclay, and SLAC experimental
data. Our model describes experimental data better at SLAC-type high incident
electron energy than those measured from Bates and Saclay. The influence of
the effective mass and symmetry energy appears to be precise on the
longitudinal cross section.

##  I Introduction

The electron scattering has long been acknowledged as one of a useful tools in
exploring the structure of nucleus and the dynamics of nucleons in nuclear
medium. In a recent work on the exclusive quasielastic scattering of electrons
off nuclei from light to heavy nuclei, we observed that the cross sections and
response functions have systematic dependence on the effective mass of the
nucleon in nuclear medium exeA2021 . In particular, the dependence appears
evident in 208Pb, in which effective mass close to free mass reproduces well
the experimental data of the single particle levels of the knocked out
protons, and their cross sections.

While exclusive $(e,e^{\prime}p)$ reaction is concerned with the distribution
of energy levels close to the Fermi surface, inclusive $(e,e^{\prime})$
reaction subsumes the participation of all the nucleons in a nucleus. The
shape and width of the peak in the inclusive cross section depends on the
average momentum and the distribution of energies of nucleons bound in nuclei.
Therefore inclusive $(e,e^{\prime})$ reaction provides a unique chance to
probe microscopic properties of nuclei not limited to a few specific and
individual states, but contributed from the whole nucleons inside a nucleus.

In the viewpoint of theory, inclusive $(e,e^{\prime})$ reaction provides
opportunities to test the performance and validity of models employed in the
description of nuclear structure and modification of hadronic properties in
nuclear medium. Without an exception, nuclear structure models are good at
reproducing the static bulk properties nuclei such as binding energy and
charge radius. Distribution of the single particle levels are, even though
they are summed up to produce correct binding energies, strongly dependent on
the nuclear structure models. For example, it has been shown that the
distribution of single particle levels depends on the effective mass of
nucleons in nuclear medium. Survey over the 240 Skyrme force models dutra2012
shows that the effective mass of the nucleon varies in the range
$(0.58-1.12)M$ where $M$ is the free mass of the nucleon. Since it receives
contributions from all the single particle levels in a nucleus, inclusive
$(e,e^{\prime})$ reaction can shed light on reducing uncertainties of the
effective mass.

Another topic under hot debate is the density dependence on the symmetry
energy. It is quite certain that the excessive spatial occupation of the
neutron in neutron-rich nuclei is strongly correlated to the slope of symmetry
energy. Since electron scattering is a qualified method to examine the spatial
structure of nuclei, inclusive $(e,e^{\prime})$ reaction provides a non-
nucleonic probe to explore the uncertainty of the density dependence of nucear
symmetry energy. Two dominant uncertainties in the nuclear many-body physics,
in-medium effective mass of the nucleon and correct form of the symmetry
energy as a function of density have not been studied systematically in the
inclusive electron scattering.

Main interest of the work is twofold: First, we test a recently developed
model for nuclear structure and nuclear matter by calculating the cross
section in the inclusive electron quasielastic scattering from nuclei and by
comparing the model results with experimental data. We focus on the kinematics
available from Bates, Saclay, and SLAC experiments, in which target nuclei are
12C, 40Ca, 56Fe, 197Au, and 208Pb and cross sections can be extracted for
incident electron energies up to 2.02 GeV and compared with experimental data.
Second, the issue of uncertainties pertinent to the effective mass and
symmetry energy is investigated by calculating the scattering observables with
different values of the effective mass and the symmetry energy. We observed a
manifest dependence on the effective mass that is critical to determination of
observables from the consideration of exclusive $(e,e^{\prime}p)$ reaction.
For the sake of consistency, and to understand the role of effective mass
clearly, we use the effective mass values used in exeA2021 , i.e. $0.7M$ and
$0.9M$ for both isoscalar and isovector effective masses. Density dependence
of the symmetry energy has been explored extenstively by using both nuclear
and neutron star data nse ; k0 . In Ref. k0 , compression modulus of the
symmetric nuclear matter and symmetry energy parameters are constrained, and
the final results are summarized in 4 sets, in which the slope parameter
varies in the range 45 $\sim$ 65 MeV. In order to highlight the dependence on
the value of slope parameter, we employ model KIDS-A and KIDS-C in this work.

The paper is organized in the following order. Section II introduces the
model, and Section III presents the basic formalism for the scattering cross
section. Section IV shows the results and discussion, and we summarize the
work in Section V.

##  II Model

A great advantage of the KIDS formalism is that the equation of state (EoS) of
infinite nuclear matter, bulk properties of nuclei, and dynamical properties
such as in-medium effective mass of the nucleon can be treated independently
to each other. For example, it’s been shown that the effective mass of the
nucleon can take different values even if the binding energy and charge radius
of nuclei are reproduced at a similar accuracy kids-nuclei1 . In Ref. exeA2021
, the role of the effective mass is investigated in the exclusive
$(e,e^{\prime})$ reaction in the quasielastic region. Considered models
predict the cross section agreeing well with experiment on the average.
However, detailed comparison shows that the cross section depends on the
effective mass in a well defined manner: models with similar effective masses
predict very similar cross sections, and the results with different effective
masses can be clearly distinguished from one another. Large effective mass
models predict results agreeing to data better than the small effective mass
models.

In the exclusive $(e,e^{\prime}p)$ reaction nucleons participating in the
process are concentrated to the energy levels and orbital states close to the
Fermi surface. In the inclusive $(e,e^{\prime})$ process, on the other hand,
the contribution of all the nucleons in a nucleus is accounted, so it provides
a more thorough examination of the nuclear structure and nuclear models. In
this work we probe the uncertainty due to the effective mass of nucleons, and
density dependence of the nuclear symmetry energy. Isoscalar and isovector
effective mass ratios are defined as

$\displaystyle\mu_{S}=\frac{m^{*}_{S}}{M},\,\,\,\mu_{V}=\frac{m^{*}_{V}}{M},$
(1)

where $m^{*}_{S}$ and $m^{*}_{V}$ are the isoscalar and isovector effective
masses, respectively. With respect to the effective mass, we use three models
KIDS0, KIDS0-m*77 and KIDS0-m*99 in Ref. exeA2021 . As one can see in Table I,
models labeled KIDS0 share the same nuclear EoS specified by $K_{0}$, $J$,
$L$, $K_{\rm sym}$, and they differ only in the effective mass. The other sets
of models named KIDS-A and KIDS-C which are rooted in Ref. k0  explore the
effect of nuclear matter properties. KIDS0, KIDS-A and KIDS-C models have
different values of the compression modulus, and symmetry energy parameters
$J$, $L$ and $K_{\rm sym}$ which are defined in the conventional expansion of
the symmetry energy $S(\rho)$ around the saturation density $\rho_{0}$

$S(\rho)=J+Lx+\frac{1}{2}K_{\rm sym}x^{2}+\cdots$

with $x=(\rho-\rho_{0})/3\rho_{0}$. Since there is no adjustment of the
effective mass in the KIDS0, KIDS-A and KIDS-C models, the models have similar
values for the effective mass.

Model | $\mu_{S}$ | $\mu_{V}$ | $K_{0}$ | $J$ | $L$ | $K_{\rm sym}$
---|---|---|---|---|---|---
KIDS0 | 0.99 | 0.81 | 240 | 33 | 49 | $-156.2$
KIDS0-m*77 | 0.70 | 0.70 | 240 | 33 | 49 | $-156.2$
KIDS0-m*99 | 0.90 | 0.90 | 240 | 33 | 49 | $-156.2$
KIDS-A | 1.01 | 0.81 | 230 | 33 | 66 | $-139.5$
KIDS-C | 0.98 | 0.80 | 250 | 31 | 58 | $-91.5$
SLy4 | 0.70 | 0.80 | 230 | 32 | 48 | $-119.7$
Table 1: Effective mass, compression modulus $K_{0}$ values and the symmetry
energy coefficients of the considered models. Dimension of $K_{0}$, $J$, $L$
and $K_{\rm sym}$ is MeV.

Nuclear contribution to the cross section is evaluated with the initial bound
and final scattering states. In order to preserve the gauge invarinace (i.e.
orthonormality of the initial and final state wave functions), the same scalar
and vector nuclear potential for the initial bound and final nucleon wave
functions should be used. For the nucleon wave functions, we start from the
Dirac equation

$\displaystyle\left[\gamma_{\mu}p^{\mu}-M-S(r)-\gamma^{0}V(r)\right]{\bf\Psi}({\bf
r})=0,$ (2)

where $S(r)$ is the scalar potential, and $V(r)$ is the time component of the
vector potential. We assume spherical symmetry. Redefining the wave function
as

${\bf\Psi}^{\prime}({\bf r})={\rm exp}\left[-\frac{1}{2}\gamma^{0}\ln
D(r)\right]{\bf\Psi}({\bf r})$ (3)

where $D(r)$ is the Darwin non-locality factor, Dirac equation is rewritten as

$\left[\gamma_{\mu}p^{\mu}-M-\frac{1}{2}{\cal U}(r)-\frac{1}{2}\gamma^{0}{\cal
U}(r)+i{\bf\alpha}\cdot\hat{\bf r}\,T(r)\right]{\bf\Psi}^{\prime}({\bf r})=0,$
(4)

where

$\displaystyle{\cal U}$ $\displaystyle=$ $\displaystyle
S+V+\frac{M-E+S+V}{M+E}(S-V),$ (5) $\displaystyle T$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\frac{d}{dr}\ln D(r).$ (6)

Since the KIDS formalism is based on non-relativistic phenomenology, the
potentials we obtain as a result of the solution of Hartree-Fock equation are
non-relativistic potentials. We have to obtain relativistic potentials $S(r)$
and $V(r)$ from the obtained non-relativistic ones. Given the non-relativistic
central potential $V_{\rm cen}(r)$, Coulomb $V_{\rm Coul}(r)$, and spin-orbit
one $V_{\rm so}(r)$, we calculate the relativistic potentials from relations
given in sv2021

$\displaystyle S(r)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left\\{\frac{1}{D}\left[U-(M-E)(D-1)\right]+(M+E)(D-1)\right\\},$
(7) $\displaystyle V(r)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left\\{\frac{1}{D}\left[U-(M-E)(D-1)\right]-(M+E)(D-1)\right\\},$
(8)

where

$\displaystyle D(r)$ $\displaystyle=$ $\displaystyle{\rm
exp}\left[-2\int^{\infty}_{r}MrV_{\rm so}(r)dr\right],$ (9) $\displaystyle
U(r)$ $\displaystyle=$ $\displaystyle U_{\rm nc}(r)+U_{\rm c}(r),$
$\displaystyle U_{\rm nc}(r)$ $\displaystyle=$
$\displaystyle\frac{2M}{E+M}\left[V_{\rm
cen}+\frac{1}{2M}T^{2}+\frac{2T}{r}+\frac{dT}{dr}\right],$ (10) $\displaystyle
U_{\rm c}(r)$ $\displaystyle=$ $\displaystyle\frac{2M}{E+M}V_{\rm Coul},$ (11)
$\displaystyle T(r)$ $\displaystyle=$ $\displaystyle MrV_{\rm so}.$ (12)

Figure 1 shows the resulting $S+V$ for light (12C), medium (56Fe), and heavy
(197Au) nuclei with models considered in this work. In all the cases,
KIDS0-m*77 and SLy4 are very similar, and their potentials are always deeper
than the other 4 models KIDS0, KIDS0-m*99, KIDS-A and KIDS-C. Interestingly,
isoscalar effective mass of KIDS-m*77 and SLy4 are the same, and it is similar
in the other 4 models.

Figure 1: $S+V$ as a function of density for the denoted nuclei.

##  III Formalism

In the plane wave Born approximation in which the electrons are described as
Dirac plane wave, the inclusive $(e,e^{\prime})$ cross section in the rest
frame of target nucleus can be written as

${\frac{d^{2}\sigma}{d\omega
d\Omega_{e}}}=\sigma_{M}\left[{\frac{Q^{4}}{q^{4}}}S_{L}(q,\omega)+\left(\tan^{2}{\frac{\theta_{e}}{2}}+{\frac{Q^{2}}{2q^{2}}}\right)S_{T}(q,\omega)\right],$
(13)

where $Q^{2}={\bf q}^{2}-\omega^{2}$ is the four momentum transfer square,
$\sigma_{M}$ represents the Mott cross section given by
$\sigma_{M}=\left({\frac{\alpha}{2E}}\right)^{2}\cos^{2}({\frac{\theta_{e}}{2}})/\sin^{4}({\frac{\theta_{e}}{2}})$,
and $S_{L}$ and $S_{T}$ are the longitudinal and transverse structure
functions which depend only on the three momentum transfer $q$ and the energy
transfer $\omega$. By keeping the three momentum and energy transfers fixed
while varying the electron incident energy $E$ and scattering angle
$\theta_{e}$, it is experimentally possible to extract the two structure
functions with two measurements.

The longitudinal and transverse structure functions in Eq. (13) are squares of
the Fourier transform of the components of the nuclear transition current
density integrated over outgoing nucleon angles, $\Omega_{p}$. Explicitly, the
structure functions for a given bound state with total angular momentum
$j_{b}$ are given by

$\displaystyle S_{L}(q,{\omega})$ $\displaystyle=$
$\displaystyle\sum_{{\mu}_{b},\,s_{p}}{\frac{{\rho}_{p}}{2(2j_{b}+1)}}\int{\mid}N_{0}{\mid}^{2}d{\Omega}_{p},$
(14) $\displaystyle S_{T}(q,{\omega})$ $\displaystyle=$
$\displaystyle\sum_{{\mu}_{b},\,s_{p}}{\frac{{\rho}_{p}}{2(2j_{b}+1)}}\int({\mid}N_{x}{\mid}^{2}+{\mid}N_{y}{\mid}^{2})d{\Omega}_{p},$
(15)

where the density of states for the outgoing nucleon is defined as
${\rho}_{p}={\frac{pE_{p}}{(2\pi)^{3}}}$. The ${\hat{\bf z}}$-axis is taken to
be along the three momentum transfer ${\bf q}$ and the z-components of the
angular momentum of the bound and continuum state nucleons are ${\mu}_{b}$ and
$s_{p}$, respectively. The Fourier transform of the nucleon transition current
$J^{\mu}({\bf r})$ is simply given by

$N^{\mu}=\int J^{\mu}({\bf r})e^{i{\bf q}{\cdot}{\bf r}}d^{3}r.$ (16)

The continuity equation could be used to eliminate the $z$-component ($N_{z}$)
via the equation $N_{z}=-{\frac{\omega}{q}}N_{0}$ if the current is conserved
by using the relation $q_{\mu}N^{\mu}=0$.

The nucleon transition current in the relativistic single particle model is
given by

$J^{\mu}({\bf r})=e{\bar{\psi}}_{p}({\bf r}){\hat{\bf J}}^{\mu}{\psi}_{b}({\bf
r})\;,$ (17)

where ${\hat{\bf J}}^{\mu}$ is a free nucleon current operator, and $\psi_{p}$
and $\psi_{b}$ are the wave functions of the outgoing nucleon and the bound
state, respectively. For a free nucleon, the operator comprises the Dirac
contribution and the contribution of an anomalous magnetic moment $\mu_{T}$
given by ${\hat{\bf
J}}^{\mu}=F_{1}(q_{\mu}^{2}){\gamma}^{\mu}+iF_{2}(q_{\mu}^{2}){\frac{{\mu}_{T}}{2M}}{\sigma}^{\mu\nu}q_{\nu}$.
The form factors $F_{1}$ and $F_{2}$ are related to the electric and magnetic
Sachs form factors given by $G_{E}=F_{1}+{\frac{{\mu}_{T}}{4M^{2}}}Q^{2}F_{2}$
and $G_{M}=F_{1}+{\mu}_{T}F_{2}$ which are assumed to take the following
standard form:

$G_{E}={\frac{1}{(1+{\frac{Q^{2}}{\Lambda^{2}})^{2}}}}={\frac{G_{M}}{({\mu}_{T}+1)}}\;,$
(18)

where the standard value for $\Lambda^{2}$ is 0.71 (GeV/c)2 and the anomalous
magnetic moment $\mu_{T}$ is used 1.793 for proton and $-1.91$ for neutron.

##  IV Result

###  IV.1 Cross sections from SLAC data

Figure 2: Differential cross section for the incident electron energy 2.02 GeV
and at the scattering angle $\theta=15^{\circ}$. SLAC data are from slacdata .
Figure 3: Longitudinal and transverse cross sections for the incident electron
energy 2.02 GeV and at the scattering angle $\theta=15^{\circ}$. The upper and
lower panels are the results for the longitudinal and transverse cross
sections, respectively.

SLAC data provide the differential cross sections with 12C, 56Fe, and 197Au
for the incident electron energy 2.02 GeV, and at the scattering angle
$\theta=15^{\circ}$ slacdata . The value of the four momentum transfer square
is about $Q^{2}=0.25$ (GeV/c)2 around the peak. Figure 2 shows the data and
theoretical results. There are several features insensitive to the mass of
nuclei. KIDS0-m*77 and SLy4 models behave almost the same, and they are worst
in the agreement with experiment. They are always underestimated than the
other models KIDS0, KIDS0-m*99, KIDS-A and C. KIDS0 and KIDS0-m*99 models are
best at reproducing the data. KIDS-A, C models predict the cross section
larger than the KIDS0 and KIDS0-m*99 models, but the difference is not as
significant as the difference from the KIDS0-m*77 and SLy4 models.

One may have already noticed easily that the two groups, one with KIDS0-m*77
and SLy4 (GroupI), and the other with the remaining 4 models (Group II) are
distinguished in terms of the effective mass. Group I models have the
effective mass in the range $(0.7\sim 0.8)M$, while the Group II models have
isoscalar effective masses $(0.9\sim 1.0)M$ and isovector ones $(0.8\sim
0.9)M$. The results indicates tha large effective mass is favored over the
effective masses smaller than $0.8M$ in the comparison with data. A similar
result has also been obtained in the exclusive $(e,e^{\prime})$ reaction
exeA2021 . In the scattering with 208Pb, results for the 3s1/2 and 2d3/2
states show evident dependence on the effective mass and better agreement to
data with larger effective masses. Response functions in the 1p1/2 and 1p3/2
states of 16O also show clear and better agreement to data with KIDS0 and
KIDS0-m*99 models than the KIDS-m*77 and SLy4.

Effect of the symmetry energy can be extracted by comparing KIDS0, KIDS-A and
KIDS-C. Around peaks ($\omega\sim 150$ MeV), difference within the three
models is 5% at most, and the difference dcreases as the mass number
increases. Three models have distinct values of $K_{0}$, $J$, $L$, and
$K_{\tau}$, but the result of KIDS-A is very similar to that of KIDS-C. These
similarities demonstrate that the cross section is insensitive to the density
dependence of the symmetry energy at least within the range that nuclear data
and neutron star properties are reproduced accurately.

It is worthwhile to compare the result of KIDS0 and SLy4. Both models are
partially fitted to the pure neutron matter EoS of apr , so they have similar
values of $J$ and $L$, which determine the behavior of the symmetry energy
most dominantly at densities relevant to nuclei. Even though the symmetry
energy is similar in the two models, cross sections are very different. This
comparison confirms that the dependence on the symmetry energy is
insignificant compared to that of the effective mass.

In Fig. 3, we show the longitudinal and transverse cross sections in Eq. (13)

$\displaystyle\sigma_{L}$ $\displaystyle=$
$\displaystyle\sigma_{M}{\frac{Q^{4}}{q^{4}}}S_{L}(q,\omega),$
$\displaystyle\sigma_{T}$ $\displaystyle=$
$\displaystyle\sigma_{M}\left(\tan^{2}{\frac{\theta_{e}}{2}}+{\frac{Q^{2}}{2q^{2}}}\right)S_{T}(q,\omega).$
(19)

The upper and lower panels are the results for the longitudinal and transverse
cross sections, respectively. The kinematics are the same as the ones in Fig.
2. The difference between Group I and Group II is shown clearly in all the
results. While in the case of transverse part the effects of effective masses
and the symmetry energy are very small in Group II, in the longitudinal part,
the role of the symmetry energy in Group II enhances the magnitude of the
cross section. Peak positions in Fig. 2 are similar between Group I and Group
II for 12Ca and 197Au, but clearly distinguished for 56Fe. The reason could be
understood from the behavior $\sigma_{L}$ and $\sigma_{T}$. Peak position of
Group I is to the left of Group II by about 50 MeV for $\sigma_{T}$ of 12C,
$\sigma_{L}$ and $\sigma_{T}$ of 56Fe, and $\sigma_{L}$ of 197Au, but for the
case of $\sigma_{L}$ for 12C and $\sigma_{T}$ for 197Au, peaks of Group I are
located on the right side of the peaks of Group II. Portion of the
longitudinal part in the total differential cross in Eq. (13) is about 45 %
due to very forward scattering angle.

###  IV.2 Cross sections from Bates and Saclay data

Figure 4: Cross sections of the 40Ca($e$, $e^{\prime}$) reaction. Experimental
data are taken from bates .

Figure 4 shows the cross section of the 40Ca($e,e^{\prime}$) reaction for the
incident electron energies $E$ and at the scattering angle $\theta$ denoted in
each panel. The values of the four momentum transfer square around the peak
are about $Q^{2}=0.22$ (GeV/c)2 for 330 MeV and about $Q^{2}=0.19$ (GeV/c)2
for 628 and 375 MeV. Results are compared with experimental data from Bates
bates .

For $E=330$ MeV and $\theta=140^{\circ}$, overall shape of data coincides
better with Group II than Group I. Position of the peak also agrees well with
the models in Group II. For $E=375$ MeV and $\theta=90^{\circ}$, data around
the peak agree well with Group I, and the Group II models predict the cross
sections slightly above the error bars. Overall behavior before and after the
peak is reproduced better by Group II. For $E=628$ MeV and
$\theta=45.5^{\circ}$, number of data is not sufficient to pin down the
location of peak. Both Group I and Group II predict similar position of peak.
For a few data below and above the peak, Group II models show good agreement
with experiment.

Figure 5: Cross sections of the 208Pb($e$, $e^{\prime}$) reaction.
Experimental data are taken from saclay .

Figure 5 shows the cross section of the 208Pb ($e,e^{\prime}$) at the incident
energies and the scattering angles specified in each panel. Theoretical
results are compared with experimental data taken from Saclay saclay . The
values of the four momentum transfer square around the peak are about
$Q^{2}=0.19$ (GeV/c)2 for 310 MeV and about $Q^{2}=0.17$ (GeV/c)2 for 485 and
354 MeV. Agreement to data depends heavily on the energy.

For $E=310$ MeV and $\theta=143^{\circ}$, all the models reproduce data up to
the peak, and the difference is negligible between the models. Shape of the
peak is flat and wide over the energy transfer $\omega=150\sim 200$ MeV. Such
a behavior is unusual compared to the data in the reactions with 12C and 56Fe,
but the Group I models reproduce the data almost perfectly in this energy
transfer range. On the other hand, the Group II models go down quickly and
monotonically right after the peak. For $E=354$ MeV and $\theta=90^{\circ}$,
models predict similar result and agree with data up to $\omega=100$ MeV.
Group II models do not agree with the data at all above 100 MeV, but the Group
I models reproduce the flat and wide behavior in $\omega=130\sim 170$ MeV. For
$E=485$ MeV and $\theta=60^{\circ}$, Group I models give the result agreeing
with data in $\omega=170\sim 190$ MeV. At the other transfer energies, theory
fails to reproduce the data.

Figure 6: Longitudinal and transverse cross section for 40Ca. The explanations
for the curves are the same as those in Fig. 4. Figure 7: Longitudinal and
transverse cross section for 208Pb. The explanations for the curves are the
same as those in Fig. 5.

In Figs. 6 and 7, the longitudinal and transverse cross sections are shown for
the reactions of 40Ca and 208Pb, respectively. For the longitudinal cross
sections, similar to Fig. 3, dependence on the symmetry energy is transparent,
and the peak positions of Group II is shifted to the right side of Group I by
about 20 $\sim$ 30 MeV. The differences for the peak positions decrease with
larger scattering angle between Group I and II. The reason for the suppression
of $\sigma_{L}$ is because the term $\tan^{2}\theta_{e}/2$ in $\sigma_{T}$,
cross section is dominated by $\sigma_{T}$ as $\theta_{e}$ increases. In the
transverse cross section, the influence of the effective mass and symmetry
energy is seldom distinguishable within each Group. Flat and wide peaks in Pb
are originated from the behavior of $\sigma_{T}$ in the Group I models. Group
II models do not show such a behavior at all. Interestingly, flat peaks also
appear in $\sigma_{L}$ of Ca for the Group I models. Flat shape becomes
evident in $\sigma_{L}$ for Ca at $\theta_{e}=140^{\circ}$. However, because
of the suppression by $\sigma_{T}$, the effect is not observed in Fig. 4.

Summarizing the results for the electron energies below 1 GeV, it is hard to
conclude definitely what values of the effective mass are more desirable for
the consistency with experiment. However, it is evidently certain that
irrespective of the target nuclei, incident energy and scattering angle,
models in a group predict very similar results, and the results of Group I are
manifestly discriminated from those of Group II.

##  V Summary

In the present work, we calculated the cross sections for inclusive
$(e,e^{\prime})$ reaction from 12C, 40Ca, 56Fe, 197Au, and 208Pb in the
quasielastic region by using the KIDS nuclear density functional model. To
conserve the nuclear current and guarantee gauge invariance, wave functions of
the bound- and continuum-state nucleons are generated by solving the Dirac
equation with the scalar and vector potentials identical in the intital and
final states. Scalar and vector potentials in the Dirac equation are obtained
from the transformation of non-relativistic potentials that are determined
from well-defined properties of finite nuclei and infinite nuclear matter, and
there is no artificial adjustment of the potential to the scattering data.

The precise value of the effective mass has not been determined in experiment
or theory. By using the KIDS density functional formalism, effective mass
values can be fixed to assumed values independent of the input data.
Consequently, they are not coupled to static properties of nuclei and EoS of
nuclear matter. Inclusive scattering supports the isoscalar effective mass in
the range $(0.9\sim 1.0)M$. In particular, the effect of the masses in the
range $(0.7\sim 0.9)M$ moves the peak positions and suppresses the magnitude
of cross sections.

Uncertainty arising from the symmetry energy was also probed. Density
dependence of the symmetry energy was adjusted to both nuclear data and
neutron star observation. Even though the coefficients of the symmetry energy
vary over a wide range, the effect of the symmetry energy is weak and makes
only a few percent difference in the cross section. However the effect of the
symmetry energy appears clearly in the longitudinal cross section though it is
very small compared to the transverse cross section.

In conclusion, the inclusive $(e,e^{\prime})$ reaction suggests criterion to
pin down the nucleon’s effective mass in nuclear medium. Effect of the
symmetry energy is not as manifest as the effective mass, but longitudinal
cross sections, if measured precisely, could provide complementary constraints
to the density dependence of the symmetry energy.

## Acknowledgments

This work was supported by the National Research Foundation of Korea (NRF)
grant funded by the Korea government (No. 2018R1A5A1025563 and No.
2020R1F1A1052495).

## References

  * (1) H. Gil, C. H. Hyun, and K. Kim, arXiv:2105.10136 [nucl-th].
  * (2) M. Dutra, O. Lourenço, J. S. Sá Martins, A. Delfino, J. R. Stone, and P. D. Stevenson, Phys. Rev. C 85, 035201 (2012).
  * (3) H. Gil, Y.-M. Kim, P. Papakonstantinou, and C. H. Hyun Phys. Rev. C 103, 034330 (2021).
  * (4) H. Gil, and C. H. Hyun, New Physics: Sae Mulli 71, 242 (2021).
  * (5) H. Gil, P. Papakonstantinou, C. H. Hyun, and Y. Oh, Phys. Rev. C 99, 064319 (2019).
  * (6) K. S. Kim, C. Y. Ryu, W. Y. So, and S. W. Hong, J. Korean Phys. Soc. 78, 188 (2021).
  * (7) D. B. Day et al., Phys. Rev. Lett. 59, 427 (1987); Phys. Rev. C 48, 1849 (1993).
  * (8) A. Akmal, V. R. Pandharipande, and D. G. Ravenhall, Phys. Rev. C 58, 1804 (1998).
  * (9) M. Deady et al., Phys. Rev. C 28, 631 (1983); 33, 1897 (1986) C. C. Blatchley, J. J. LeRose, O. E. Pruet, P. D. Zimmerman, C. F. Williamson, and M. Deady, ibid. 34, 1243 (1986).
  * (10) A. Zghiche, et al., Nucl. Phys. A 572, 513 (1994).


claimClaim remarkRemark hypothesisHypothesis

    Greedy randomized sparse Kaczmarz method with linear convergenceZiyang Yuan, Hui Zhang, Hongxia Wang

    # Sparse Sampling Kaczmarz-Motzkin Method with Linear Convergence

    Ziyang Yuan
    Mathematical Department, National University of Defense Technology ().
<EMAIL_ADDRESS>

    Hui Zhang
    Corresponding Author, Mathematical Department, National University of Defense Technology ( )
<EMAIL_ADDRESS>

    Hongxia Wang
    Mathematical Department, National University of Defense Technology ( )
<EMAIL_ADDRESS>

    ###### Abstract

    The randomized sparse Kaczmarz method was recently proposed to recover sparse solutions of linear systems. In this work, we introduce a greedy variant of the randomized sparse Kaczmarz method by employing the sampling Kaczmarz-Motzkin method, and prove its linear convergence in expectation with respect to the Bregman distance in the noiseless and noisy cases. This greedy variant can be viewed as a unification of the sampling Kaczmarz-Motzkin method and the randomized sparse Kaczmarz method, and hence inherits the merits of these two methods. Numerically, we report a couple of experimental results to demonstrate its superiority.

    ###### keywords:

    Sampling Kaczmarz-Motzkin, Bregmann projection, Sparse.

    00A20

    ##
    1 Introduction

    The Kaczmarz method, originally appeared in [1], might be the most well-known method for finding an approximation solution to large-scale linear systems of the form

    (1)

    $\displaystyle\mathbf{A}\mathbf{x}=\mathbf{b},$

    where $\mathbf{A}\in\mathbb{R}^{m\times n}$
    and $\mathbf{b}\in\mathbb{R}^{m}$. It has been utilized in a large range of applications such as computer tomography [2], digital signal processing [3], distributed computing [4] and many other engineering and physics problems.
    The standard Kaczmarz iterative scheme reads as

    (2)

    $\displaystyle\mathbf{x}_{k+1}=\mathbf{x}_{k}-\frac{\langle\mathbf{a}_{i},\mathbf{x}_{k}\rangle-b_{i}}{\left\|\mathbf{a}_{i}\right\|_{2}^{2}}\mathbf{a}_{i},$

    where $\mathbf{a}_{i}$ is the vector transposed by the $i$-th row of $\mathbf{A}$, $b_{i}$ is the $i$-th entry of $\mathbf{b}$, and the index $i$ is chosen cyclically. Geometrically, (2) says that $\mathbf{x}_{k+1}$ is obtained by projecting $\mathbf{x}_{k}$ onto the hyperplane $\{\mathbf{x}\in\mathbb{R}^{n}:\langle\mathbf{a}_{i},\mathbf{x}\rangle=b_{i}\}$. When it is initialized with $\mathbf{x}_{0}=\bm{0}$, the iteration sequence $\{\mathbf{x}_{k}\}$ generated by the Kaczmarz method converges linearly to the minimum 2-norm solution $\hat{\mathbf{x}}$ of $\mathbf{A}\mathbf{x}=\mathbf{b}$. However, the rate of convergence is hard to estimate. In 2009, the authors of
    [5] first analyzed a randomized variant of the Kaczmarz method. Instead of choosing $i$ cyclically, it updates $\mathbf{x}_{k}$ via (2) at random by choosing the $i$-th row with probability $\frac{\|\mathbf{a}_{i}\|^{2}_{2}}{\|\mathbf{A}\|^{2}_{\mathrm{F}}}$. Theoretically, they showed that the randomized Kaczmarz method converges linearly in the sense that

    (3)

    $\mathbb{E}\left[\left\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\right\|_{2}^{2}\right]\leq\left(1-\frac{\sigma^{2}_{\min}(\mathbf{A})}{\|\mathbf{A}\|_{\text{F}}^{2}}\right)\cdot\mathbb{E}\left[\left\|\mathbf{x}_{k}-\hat{\mathbf{x}}\right\|_{2}^{2}\right],$

    where
    $\|\mathbf{A}\|_{\text{F}}$ is the Frobenius norm and $\sigma_{\min}(\mathbf{A})$ denotes the smallest singular value of $\mathbf{A}$. This elegant result triggers a great of researches into developing new variants and corresponding convergence analysis; seeing [6, 7, 8, 9, 10, 11]. Recently, finding sparse solutions of linear systems becomes a popular topic in data science and machine learning. In this paper, we focus on another variant of the Kaczmarz method namely the randomized sparse Kaczmarz method, which was developed in
    [12, 13, 14]. Specifically, the iterative procedure of randomized sparse Kaczmarz method can be formulated as

    (4)

    $\displaystyle\begin{aligned} \mathbf{x}_{k+1}^{*}&=\mathbf{x}_{k}^{*}-\frac{\left\langle\mathbf{a}_{i},\mathbf{x}_{k}\right\rangle-\mathbf{b}_{i}}{\left\|\mathbf{a}_{i}\right\|_{2}^{2}}\cdot\mathbf{a}_{i},\\
    \mathbf{x}_{k+1}&=S_{\lambda}\left(\mathbf{x}_{k+1}^{*}\right),\end{aligned}$

    where the parameter $\lambda$ is a nonnegative parameter, and the index $i$ is chosen by the same probability of the randomized Kaczmarz method. The soft thresholding operator $S_{\lambda}(x)=\textrm{max}\{|x|-\lambda,0\}\cdot\textrm{sign}(x)$ is introduced here to generate sparse solutions. In the case of $\lambda=0$, $S_{\lambda}(\cdot)$ reduces to the identity operator so that $\mathbf{x}^{*}_{k+1}=\mathbf{x}_{k+1}$ and hence the randomized sparse Kaczmarz method generalizes randomized Kaczmarz method in [5]. In the case of $\lambda\neq 0$, a larger $\lambda$ is likely to generate a sparser solution. Interestingly, it has also been shown that randomized sparse Kaczmarz method still converges linearly in a similar way to (3)[14].

    As a natural development, we wonder whether randomized sparse Kaczmarz method still works well, or even better, if it is equipped with more advanced sampling strategies that may accelerate the convergence rate. To this end, by employing the sampling Kaczmarz-Motzkin method, which essentially combines the random and greedy ideas together, we propose a new variant, called sparse sampling Kaczmarz-Motzkin method (SSKM). The proposed variant can be viewed as a blender of randomized sparse Kaczmarz method and the sampling Kaczmarz-Motzkin method. SSKM method randomly samples $\beta$ rows from $\mathbf{A}$, and then
    greedily picks out the most-violated one among the $\beta$ rows(refer to the second column of Table 1). Hence, the SSKM method inherits the merits of these two methods. Theoretically, by introducing the concept of Bregman projection, we prove that the SSKM method converges linearly in expectation in the noiseless case. Especially, as listed in the third column of Table 1, it can have a faster convergence rate comparing to the previous results. Furthermore, we also show that the same linear convergence rate can be held even with noisy observed data. Finally, we demonstrate the superiority of SSKM method by groups of numerical experiments.

    The paper is organized as follows. Section 2 shows some theories about Bregman projection. In section 3, we introduce SSKM method and prove its linearly convergence. Section 4 reports the numerical tests. Section 5 is the conclusion.

    Table 1: Convergence rate comparison between different methods. The rows of $\mathbf{A}$ are normalized, $\|\mathbf{e}_{k}\|^{2}_{2}=\|\mathbf{A}\mathbf{x}^{k}-\mathbf{b}\|^{2}_{2}$, $|\hat{\mathbf{x}}|_{\min}$ means the smallest nonzero absolute element, $\tilde{\sigma}_{\min}(\mathbf{A})$ is the non-zero smallest singular value, and $\beta_{k}/\gamma_{k}\geq 1$.

    | Selection Rule
    | Convergence Rate

    ---|---|---

    $\mathrm{RK}\cite[cite]{[\@@bibref{}{2009AVershyin}{}{}]}$
    | $\mathbb{P}\left(t_{j}=i\right)=\frac{\left\|\mathbf{a}_{i}\right\|^{2}_{2}}{\|\mathbf{A}\|_{\text{F}}^{2}}$
    | $\mathbb{E}\left\|\mathbf{e}_{k}\right\|^{2}\leq\left(1-\frac{\sigma_{\min}^{2}(\mathbf{A})}{\|\mathbf{A}\|_{\text{F}}^{2}}\right)^{k}\left\|\mathbf{e}_{0}\right\|^{2}_{2}$

    $\mathrm{SRK}$[14]

    | $\mathbb{P}\left(t_{j}=i\right)=\frac{\left\|\mathbf{a}_{i}\right\|^{2}_{2}}{\|\mathbf{A}\|_{\text{F}}^{2}}$
    | $\mathbb{E}\left\|\mathbf{e}_{k}\right\|^{2}\leq\left(1-\frac{\tilde{\sigma}_{\min}^{2}(A)}{2m}\cdot\frac{|\hat{\mathbf{x}}|_{\min}}{|\hat{\mathbf{x}}|_{\min}+2\lambda}\right)^{k}\left\|\mathbf{e}_{0}\right\|^{2}_{2}$

    $\mathrm{SSKM}$
    | $\tau_{j}\sim\binom{[m]}{\beta}$
    | $\mathbb{E}\left\|\mathbf{e}_{k}\right\|^{2}\leq\prod_{i=0}^{k}\left(1-\frac{\beta_{k}\tilde{\sigma}_{\min}^{2}(A)}{2\gamma_{k}m}\cdot\frac{|\hat{\mathbf{x}}|_{\min}}{|\hat{\mathbf{x}}|_{\min}+2\lambda}\right)\left\|\mathbf{e}_{0}\right\|^{2}_{2}$

    $t_{j}=\arg\max_{i\in\tau_{j}}(\mathbf{a}_{i}^{\top}\mathbf{x}_{j-1}-b_{i})^{2}$

    ##
    2 Preliminaries

    First, we recall some concepts and properties of convex functions.

    ###
    2.1 Basic notions

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be convex. Define the subdifferential of $f$ at $\mathbf{x}\in\mathbb{R}^{n}$ by

    $\partial f(\mathbf{x}):=\{\mathbf{x}^{*}\in\mathbb{R}^{n}:f(\mathbf{y})\geq f(\mathbf{x})+\langle\mathbf{x}^{*},\mathbf{y}-\mathbf{x}\rangle,\forall\mathbf{y}\in\mathbb{R}^{n}\}.$

    Each $\mathbf{x}^{*}$ is called a subgradient of $f$ at $\mathbf{x}$. Next, let us define the strong convexity.

    ######
    Definition 2.1.

    The function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is said to be strongly convex, if there exists $\alpha>0$, so that for any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ and $\mathbf{x}^{*}\in\partial f(\mathbf{x})$, we have

    $f(\mathbf{y})\geq f(\mathbf{x})+\langle\mathbf{x}^{*},\mathbf{y}-\mathbf{x}\rangle+\frac{\alpha}{2}\|\mathbf{x}-\mathbf{y}\|_{2}^{2}.$

    If the concrete value of $\alpha$ is involved, then $f$ is said to be $\alpha$-strongly convex. The Fenchel conjugate $f^{*}$ of $f$ is given by,

    $f^{*}(\mathbf{x}):=\sup_{\mathbf{z}\in\mathbb{R}^{n}}\{\langle\mathbf{x},\mathbf{z}\rangle-f(\mathbf{z})\big{\}}.$

    There are many interesting connections between $f$ and $f^{*}$. Especially, as illustrated by the following fact, the strong convexity of $f$ can imply the smoothness of $f^{*}$,

    ######
    Theorem 2.2 ([15]).

    If $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is $\alpha$-strongly convex, then the Fenchel conjugate function $f^{*}$ is differentiable with $1/\alpha$-Lipschitz continuous gradient, that is

    $\|\nabla f^{*}(\mathbf{x})-\nabla f^{*}(\mathbf{y})\|_{2}\leq\frac{1}{\alpha}\cdot\|\mathbf{x}-\mathbf{y}\|_{2},\forall\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}.$

    ###
    2.2 Bregman distance

    ######
    Definition 2.3 ([12]).

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be strongly convex. The Bregman distance $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})$ between $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ with respect to $f$ and a subgradient $\mathbf{x}^{*}\in\partial f(\mathbf{x})$ is defined as

    $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y}):=f(\mathbf{y})-f(\mathbf{x})-\langle\mathbf{x}^{*},\mathbf{y}-\mathbf{x}\rangle.$

    If $f$ is differentiable, then we have $\{\nabla f(\mathbf{x})\}=\partial f(\mathbf{x})$. Note that, when $f(\mathbf{x})=\|\mathbf{x}\|^{2}$, $D_{f}(\mathbf{x},\mathbf{y})=\|\mathbf{x}-\mathbf{y}\|^{2}$, which is the standard Euclidean distance.

    Subsequently, we introduce an important property of the Bregman distance to prove the convergence of SSKM method. It can be immediately derived from the assumption of strong convexity.

    ######
    Lemma 2.4 ([14]).

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be $\alpha$-strongly convex. For any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$, $\mathbf{x}^{*}\in\partial f(\mathbf{x})$, and $\mathbf{y}^{*}\in\partial f(\mathbf{y})$, we have

    $\frac{\alpha}{2}\|\mathbf{x}-\mathbf{y}\|_{2}^{2}\leq D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})\leq\langle\mathbf{x}^{*}-\mathbf{y}^{*},\mathbf{x}-\mathbf{y}\rangle\leq\|\mathbf{x}^{*}-\mathbf{y}^{*}\|_{2}\|\mathbf{x}-\mathbf{y}\|_{2}.$

    Thus,

    $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})=0\Leftrightarrow\mathbf{x}=\mathbf{y}.$

    ###
    2.3 Bregman projection

    ######
    Definition 2.5 ([12]).

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be strongly convex, and $\mathbf{C}\subset\mathbb{R}^{n}$ be a nonempty closed convex set. The Bregman projection of $\mathbf{x}$ onto $\mathbf{C}$ with respect to $f$ and $\mathbf{x}^{*}\in\partial f(\mathbf{x})$ is the unique point defined as $\Pi_{\mathbf{C}}^{\mathbf{x}^{*}}(\mathbf{x})\in\mathbf{C}$ such that

    $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\Pi_{\mathbf{C}}^{\mathbf{x}^{*}}(\mathbf{x}))=\min_{\mathbf{y}\in\mathbf{C}}D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y}).$

    Note that, the Bregman projection can be regarded as a generalization of the traditional orthogonal projection. In fact, if $f(\mathbf{x})=\frac{1}{2}\|\mathbf{x}\|^{2}_{2}$, then $\Pi_{\mathbf{C}}^{\mathbf{x}}(\mathbf{x})=\arg\min_{y\in\mathbf{C}}\frac{1}{2}\|\mathbf{x}-\mathbf{y}\|^{2}_{2}$. Lemma below characterizes the Bregman projection.

    ######
    Lemma 2.6 ([14]).

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be strongly convex and $\mathbf{C}$ be a nonempty closed convex set. The point $\mathbf{z}\in\mathbf{C}$ is the Bregman projection of $\mathbf{x}$ onto $\mathbf{C}$ with respect to $f$ and $\mathbf{x}^{*}\in\partial f(\mathbf{x})$ iff there are some $\mathbf{z}^{*}$ such that one of the following equivalent conditions is satisfied

    $\displaystyle\langle\mathbf{z}^{*}-\mathbf{x}^{*},\mathbf{y}-\mathbf{z}\rangle\geq 0$
    $\displaystyle,\forall\mathbf{y}\in\mathbf{C}$

    $\displaystyle D_{f}^{\mathbf{z}^{*}}(\mathbf{z},\mathbf{y})\leq D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})-D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{z}),$

    Then, the point $\mathbf{z}^{*}$ is called the admissible subgradient for $\mathbf{z}=\Pi_{C}^{\mathbf{x}^{*}}(\mathbf{x}).$

    ##
    3 Sparse sampling Kaczmarz-Motzkin method

    In this section, SSKM method will be introduced to solve the augmented Basis pursuit model [16, 17]
    below,

    (5)

    $\displaystyle\begin{aligned} &\min_{\mathbf{x}\in\mathbb{R}^{n}}f(\mathbf{x})=\lambda\|\mathbf{x}\|_{1}+\frac{1}{2}\|\mathbf{x}\|_{2}^{2}\\
    &\text{s.t. }\mathbf{A}\mathbf{x}=\mathbf{b},\end{aligned}$

    where $\lambda>0$ is some regularizer.
    In this study, we assume $\mathbf{b}\neq\bm{0}$, and it is in the $\text{Range}(\mathbf{A})$. Consequently, the solution of (5) is unique and nonzero.

    Let $\mathbf{x}_{k}$ and its admissible subgradient $\mathbf{x}^{*}_{k}$ be given. The procedure of SSKM method in each iteration consists of two steps.

      1.
    Step 1.

    Choose an index $i_{k}$ according to the following distribution

    $\displaystyle\tau_{k}\sim p_{\mathrm{k}}:\left(\begin{array}[]{c}{[m]}\\
    \beta_{k}\end{array}\right)\rightarrow[0,1),$

    $\displaystyle i_{k}=\arg\max_{i\in\tau_{k}}(\mathbf{a}_{i}^{\top}\mathbf{x}_{k}-b_{i})^{2}$
    ,

    where $\binom{[m]}{\beta_{k}}$ means sampling $\beta_{k}$ numbers from the index set $[m]:=\{1,2,\cdots,m\}$.

      2.
    Step 2.

    Calculate the Bregman projection of $\mathbf{x}_{k}$ onto the $i_{k}$-th hyperplane $H(\mathbf{a}_{i_{k}},b_{i_{k}})=\{\mathbf{x}:\langle\mathbf{a}_{i_{k}},\mathbf{x}\rangle=b_{i_{k}}\}$ denoted by $\Pi^{\mathbf{x}^{*}_{k}}_{H(\mathbf{a}_{i_{k}},b_{i_{k}})}(\mathbf{x}_{k})$, and calculating its admissible subgradient.

    Algorithm 1  The Sampling Sparse Kaczmarz-Motzkin method

    0:  $\{\mathbf{x}_{0}=\mathbf{x}_{0}^{*}\in\mathbb{R}^{n},\mathbf{A}\in\mathbb{R}^{m\times n},\varepsilon,T\}$   $\mathbf{x}_{0}$: the initial point.$\mathbf{x}_{0}$: the initial point of intermediate variable.$\mathbf{A}$: the measurement matrix, whose rows are normalized.$\beta_{k}$: is the random sampling number.$\varepsilon$:  the allowed error bound.$\lambda$: the parameter of the soft-thresholding operator.$T$:  the allowed maximum iteration.

    0:    $\overline{\mathbf{x}}$: an estimation of the ground truth.

    $\mathbf{Initialization:}$

    1:  $\mathbf{x}_{0},\mathbf{x}_{0}^{*}$ are $\bm{0}$.

    $\mathbf{General~{}step}$

    1:  choose an index $i_{k}$ from the selection rule.

    $\displaystyle\begin{array}[]{c}\tau_{k}\sim p_{k},~{}\text{and}~{}p_{\mathbf{x}}(\tau_{k})=\frac{1}{m},\\
    i_{k}=\arg\max_{i\in\tau_{k}}(\mathbf{a}_{i}^{\top}\mathbf{x}_{k}-b_{i})^{2}.\end{array}$

    2:  $\mathbf{x}_{k+1}^{*}=\mathbf{x}_{k}^{*}-t_{k}\cdot\mathbf{a}_{i_{k}}.$

    3:  Where $t_{k}=\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-\mathbf{b}_{i_{k}},$ which is called the inexact step or $t_{k}=\operatorname{argmin}_{t\in\mathbb{R}}f^{*}\left(\mathbf{x}_{k}^{*}-t\cdot\mathbf{a}_{i_{k}}\right)+t\cdot\mathbf{b}_{i_{k}}$ which is called the exact step.

    4:  $\mathbf{x}_{k+1}=S_{\lambda}\left(\mathbf{x}_{k+1}^{*}\right),$ where $S_{\lambda}(\cdot)$ is the soft-thresholding operator which is defined as

    $S_{\lambda}(x_{i})=\max(|x_{i}|-\lambda,0)\cdot\textrm{sign}(x_{i}),i=1,\cdots,n.$

    5:  if $\big{|}\big{|}\mathbf{A}\mathbf{x}_{k+1}-\mathbf{b}\big{|}\big{|}_{2}\leq\varepsilon$ or $k=T$ then

    6:     $\overline{\mathbf{x}}=\mathbf{x}_{k+1}$.

    7:  end if

    In the following, we will present some technical details that help us understand SSKM, along with some preliminary theoretical results, which will be used for convergence analysis.

    ###
    3.1 Sampling rule

    The strategy to choose which $H(\mathbf{a}_{i},b_{i})$ to be projected onto is based on the rule of Sampling Kaczmarz-Motzkin method, which picks up the most violated item from one of the subsets with $\beta$ rows from $\mathbf{A}$. On the contrary to the randomized Kaczmarz and Randomized sparse Kazmarz methods, which pick up rows with a fixed probability, the probability that SSKM method utilized is flexible, and it is defined as

    (8)

    $\displaystyle p_{\mathbf{x}}(\tau_{k}):=\frac{\|\mathbf{a}_{t(\tau_{k},\mathbf{x})}\|^{2}_{2}}{\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\|\mathbf{a}_{t(\tau_{k},\mathbf{x})}\|^{2}_{2}},$

    where $t(\tau_{k},\mathbf{x})=\arg\max_{i\in\tau_{k}}(\mathbf{a}_{i}^{T}\mathbf{x}-b_{i})^{2}$. From (8), we can find the probability to choose the sub-row of $\mathbf{A}$ is not uniform, it depends on the norm of $\mathbf{a}_{t(\tau_{k},\mathbf{x})}$ which has the largest error among $(\mathbf{a}_{i}^{T}\mathbf{x}-b_{i})^{2},i\in\tau_{k}$. If $\beta_{k}=1$, (8) is equivalent to the randomized Kaczmarz method. If $\beta_{k}=m$, it is equivalent to picking up the most violated item from the whole rows of $\mathbf{A}$.

    At the first glimpse, calculating (8) demands a large burden of computational cost. However, if $\mathbf{A}$ is normalized, (8) is equal to choosing the most violated item from random $\binom{[m]}{\beta_{k}}$ rows of $\mathbf{A}$. So, there is no need to find out all the subsets with $\beta_{k}$ rows of $\mathbf{A}$. As a result, the whole computational cost is low.

    ###
    3.2 Bregman projection procedure

    The core of the second part is to calculate the Bregman projection. Lemma 3.1 below demonstrates how to calculate the Bregman projection of a given point. For completeness, we give a simple theoretical proof here.

    ######
    Lemma 3.1 ([12]).

    Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be $\alpha$-strongly convex, $\mathbf{A}\in\mathbb{R}^{m\times n}$,$\mathbf{b}\in\mathbb{R}^{m}$. Then, the Bregman projection of $\mathbf{x}\in\mathbb{R}^{n}$ onto the hyperplane $H(\mathbf{a}_{i},b_{i})$ with $\mathbf{a}_{i}\neq\bm{0}$ is

    (9)

    $\displaystyle\mathbf{z}:=\Pi_{H(\mathbf{a}_{i},b_{i})}^{\mathbf{x}^{*}}(\mathbf{x})=\nabla f^{*}(\mathbf{x}^{*}-\hat{t}\mathbf{a}_{i}),$

    where $\hat{t}\in\mathbb{R}$, which is one of the solutions of

    $\min_{t\in\mathbb{R}}f^{*}(\mathbf{x}^{*}-t\mathbf{a}_{i})+tb_{i}.$

    Moreover, $\mathbf{z}^{*}:=\mathbf{x}^{*}-\hat{t}\mathbf{a}_{i}$ is an admissible subgradient for $\mathbf{z}$ and for any $\mathbf{y}\in H(\mathbf{a}_{i},b_{i})$, we have

    (10)

    $\displaystyle D_{f}^{\mathbf{z}^{*}}(\mathbf{z},\mathbf{y})\leq D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})-\frac{\alpha}{2}\frac{(\langle\mathbf{a}_{i},\mathbf{x}\rangle-b_{i})^{2}}{\|\mathbf{a}_{i}\|^{2}_{2}}.$

    ######
    Proof 3.2.

    Recall the definition of the hyperplane $H(\mathbf{a}_{i},b_{i})=\{\mathbf{x}:\mathbf{a}_{i}^{T}\mathbf{x}=b_{i}\}$. If $\mathbf{z}:=\Pi^{\mathbf{x}^{*}}_{H(\mathbf{a}_{i},b_{i})}(\mathbf{x})$, then $\mathbf{a}_{i}^{T}\mathbf{z}=b_{i}$. As a result, $H(\mathbf{a}_{i},b_{i})-\{\mathbf{z}\}=\{\mathbf{y}:\mathbf{a}_{i}^{T}\mathbf{y}=0\}$.
    Thus, the normal cone $N_{H(\mathbf{a}_{i},b_{i})}(\mathbf{z})=\{t\mathbf{a}_{i},t\in\mathbb{R}\}$.
    Because

    $\displaystyle\mathbf{z}$
    $\displaystyle=$
    $\displaystyle\min_{\mathbf{y}\in\mathbf{C}}D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})=\min_{\mathbf{y}\in\mathbf{C}}f(\mathbf{y})-\langle\mathbf{x}^{*},\mathbf{y}-\mathbf{x}\rangle$

    $\displaystyle=$
    $\displaystyle\min_{\mathbf{y}\in\mathbb{R}^{n}}f(\mathbf{y})-\langle\mathbf{x}^{*},\mathbf{y}-\mathbf{x}\rangle+\delta_{\mathbf{C}}(\mathbf{y}),$

    where $\delta_{\mathbf{C}}(\cdot)$ is the indicator function. Thus, we can infer that $(\mathbf{x}^{*}-\mathbf{z}^{*})\in N_{\mathbf{C}}(\mathbf{x})$ by the first order optimality condition. As a result, there exists
    $\hat{t}\in\mathbb{R}$, such that $\mathbf{x}^{*}-\hat{t}\mathbf{a}_{i}\in\partial f(\mathbf{z})$. Then $\nabla f^{*}(\mathbf{x}^{*}-\hat{t}\mathbf{a}_{i})=\mathbf{z}$, which is the Bregman projection of $\mathbf{x}$. Remaining is to calculate $\hat{t}$, which is called the exact step. Note that $\mathbf{a}_{i}^{T}\nabla f^{*}(\mathbf{x}^{*}-\hat{t}\mathbf{a}_{i})=b_{i}.$ By the first order optimality condition, we can formulate an optimization problem below

    $\hat{t}\in\arg\min_{t\in\mathbb{R}}f^{*}(\mathbf{x}^{*}-t\mathbf{a}_{i})+tb_{i}.$

    Last is to prove the inequality. Recalling Lemma 2.6, we have

    $D_{f}^{\mathbf{z}^{*}}(\mathbf{z},\mathbf{y})\leq D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{y})-D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{z}).$

    Then, by the strong convex property of $f$, we derive that

    $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\mathbf{z})\geq\frac{\alpha}{2}\|\mathbf{x}-\mathbf{z}\|^{2}\geq\frac{\alpha}{2}\|\mathbf{x}-\mathbb{P}_{H(\mathbf{a}_{i},b_{i})}(\mathbf{x})\|^{2}=\frac{\alpha}{2}\frac{(\langle\mathbf{a}_{i},\mathbf{x}\rangle-b_{i})^{2}}{\|\mathbf{a}_{i}\|^{2}_{2}},$

    where $\mathbb{P}_{H(\mathbf{a}_{i},b_{i})}(\mathbf{x})$ is the standard orthogonal projection of $\mathbf{x}$ onto $H(\mathbf{a}_{i},b_{i})$. Then, we complete the proof.

    ##
    4 Proof of linear convergence of the SSKM method

    First, we characterize the error bound between $D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\hat{\mathbf{x}})$ and $\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}$.

    ######
    Lemma 4.1 ( [14]).

    Let $\tilde{\sigma}_{\min}(\mathbf{A})$ and $|\hat{\mathbf{x}}|_{\min}$ be defined as before. When $\lambda>0$, then for any $\mathbf{x}\in\mathbb{R}^{n}$ with $\partial f(\mathbf{x})\cap\mathcal{R}(\mathbf{A}^{T})\neq\emptyset$ and for all $\mathbf{x}^{*}=\mathbf{A}^{T}\mathbf{y}\in\partial f(\mathbf{x})\cap\mathcal{R}(\mathbf{A}^{T})$,
    $\mathbf{y}\in\mathbb{R}^{m}$, we have

    (11)

    $\displaystyle D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\hat{\mathbf{x}})\leq\frac{1}{\tilde{\sigma}_{\min}^{2}(\mathbf{A})}\cdot\frac{|\hat{\mathbf{x}}|_{\min}+2\lambda}{|\hat{\mathbf{x}}|_{\min}}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}_{2}.$

    Remark: when $\lambda=0$, and $\mathbf{A}$ is a full column rank matrix, by the strong convexity of $f$, we can immediately obtain that

    (12)

    $\displaystyle D_{f}^{\mathbf{x}^{*}}(\mathbf{x},\hat{\mathbf{x}})\leq\frac{1}{2\sigma_{\min}^{2}(\mathbf{A})}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|_{2}^{2}.$

    In the following, we present our results for the noiseless and noisy cases respectively.

    ######
    Theorem 4.2 (Noiseless case).

    Let

    $\gamma_{k}:=\frac{\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{2}}{\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}\leq\beta_{k},$

    and

    $q_{k}:=\left\{\begin{aligned} &(1-\frac{\beta_{k}\tilde{\sigma}_{\min}^{2}(\mathbf{A})}{2\gamma_{k}m}\cdot\frac{|\hat{\mathbf{x}}|_{\min}}{|\hat{\mathbf{x}}|_{\min}+2\lambda}),\lambda>0&\\
    &(1-\frac{\beta_{k}\sigma_{\min}^{2}(\mathbf{A})}{\gamma_{k}m}),\lambda=0&\end{aligned}\right..$

    The sequence $\{\mathbf{x}_{k}\}$ generated by the SSKM method in Algorithm 1 converges linearly in expectation to the unique solution $\hat{\mathbf{x}}$ of (5) in the sense that

    (13)

    $\displaystyle\mathbb{E}[D_{f}^{\mathbf{x}^{*}_{k+1}}(\mathbf{x}_{k+1},\hat{\mathbf{x}})]\leq q_{k}\mathbb{E}[D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})].$

    Furthermore, we have

    (14)

    $\displaystyle\mathbb{E}[\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\|_{2}]\leq\prod_{i=0}^{k}q_{k}^{\frac{1}{2}}\sqrt{2\lambda\|\hat{\mathbf{x}}\|^{2}_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}}.$

    Remark: The convergence rate of SSKM method depends on the contraction factors $q_{k}$. Note that $1\leq\gamma_{k}\leq\beta_{k}$. When $(\mathbf{a}^{T}_{i}\mathbf{x}_{k}-b_{i})^{2},i=1,\cdots,m$ are equal, the upper bound of $\gamma_{k}$ by $\beta_{k}$ can be achieved. In that case, SSKM method obtains the slowest convergence rate. On the contrary, the lower bound $\gamma_{k}=1$ can be achieved when only one of the residuals $|\mathbf{a}^{T}_{i}\mathbf{x}_{k}-b_{i}|$ is nonzero. Then, SSKM method converges as fast as

    $q_{k}=\left\{\begin{aligned} &(1-\frac{\tilde{\sigma}_{\min}^{2}(\mathbf{A})}{2}\cdot\frac{|\hat{\mathbf{x}}|_{\min}}{|\hat{\mathbf{x}}|_{\min}+2\lambda}),\lambda>0&\\
    &(1-\sigma^{2}_{\min}(\mathbf{A})),\lambda=0&\end{aligned}\right..$

    The relationship between $\gamma_{k}$ and $\beta_{k}$ can be refined for different $\mathbf{A}$. In [18], it demonstrates that when $\mathbf{A}$ are drawn i.i.d from a standard Gaussian distribution, $\gamma_{k}=\mathcal{O}(n\beta_{k}/log(\beta_{k}))$.

    Now, let us finish the proof of Theorem 4.2.

    ######
    Proof 4.3.

    By using (10) with $\mathbf{x}_{k+1}=\mathbf{z}$, $\mathbf{x}_{k}=\mathbf{x}$ and $\mathbf{y}=\hat{\mathbf{x}}$ in Lemma 3.1, inequality can be reformulated as below

    $\displaystyle D_{f}^{\mathbf{x}_{k+1}^{*}}(\mathbf{x}_{k+1},\hat{\mathbf{x}})$
    $\displaystyle\leq$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\frac{1}{2}\cdot\frac{(\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\mathbf{x}_{k}-\mathbf{b}_{i_{k}})^{2}}{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}}$

    $\displaystyle=$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\frac{1}{2}\cdot\frac{\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}}.$

    At the same time, (4.3) is also held for the inexact step by Theorem 2.8 in [12]. Using the sampling rule of the Kaczmarz-Motzkin method, and treating $\tau_{k}$ as the random variable, we derive that

    $\displaystyle\mathbb{E}[D_{f}^{\hat{\mathbf{x}_{k+1}}}$
    $\displaystyle(\mathbf{x}_{k+1},\hat{\mathbf{x}})|\tau_{k-1},\cdots,\tau_{1},\tau_{0}]$

    $\displaystyle\leq$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\mathbb{E}_{\tau_{k}}(\frac{1}{2}\cdot\frac{\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}})$

    $\displaystyle=$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}p_{\mathbf{x}_{k}}(\tau_{k})\frac{1}{2}\frac{\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}}$

    $\displaystyle=$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\frac{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}}{\sum_{\pi\in\binom{[m]}{\beta_{k}}}\|\mathbf{a}_{i(\pi,\mathbf{x}_{k})}\|^{2}_{2}}\frac{1}{2}\frac{\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}{\|\mathbf{a}_{i(\tau_{k},\mathbf{x}_{k})}\|^{2}_{2}}$

    $\displaystyle=$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\frac{1}{2}\frac{\|\mathbf{A}_{\tau_{k}}\mathbf{x}_{k}-\mathbf{b}_{\tau_{k}}\|^{2}_{\infty}}{\sum_{\pi\in\binom{[m]}{\beta_{k}}}\|\mathbf{a}_{i(\pi,\mathbf{x}_{k})}\|^{2}_{2}}$

    $\displaystyle=$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}})-\frac{1}{2}\frac{\binom{m}{\beta_{k}}\beta_{k}\|\mathbf{A}\mathbf{x}_{k}-\mathbf{b}\|^{2}_{2}}{\gamma_{k}\sum_{\pi\in\binom{[m]}{\beta_{k}}}\|\mathbf{a}_{i(\pi,\mathbf{x}_{k})}\|^{2}_{2}}$

    $\displaystyle\leq$
    $\displaystyle(1-\frac{\beta_{k}\tilde{\sigma}_{\min}^{2}(\mathbf{A})}{2\gamma_{k}m}\cdot\frac{|\hat{\mathbf{x}}|_{\min}}{|\hat{\mathbf{x}}|_{\min}+2\lambda})D_{f}^{\mathbf{x}_{k}^{*}}(\mathbf{x}_{k},\hat{\mathbf{x}}),$

    where the last equality can be derived from (11). Now considering all indexes $\tau_{0},\cdots,\tau_{k}$ as random variables with values in $\{1,\cdots,m\}$,
    and taking the full expectation on both sides, we can finish the proof of (13).

    Note that

    $D_{f}^{\mathbf{x}^{*}_{k+1}}(\mathbf{x}_{k+1},\hat{\mathbf{x}})\geq\frac{1}{2}\|\mathbf{x}^{k+1}-\hat{\mathbf{x}}\|_{2}^{2},$

    and

    $D_{f}^{\mathbf{x}^{*}_{0}}(\mathbf{x}_{0},\hat{\mathbf{x}})=\frac{1}{2}\|\hat{\mathbf{x}}\|^{2}_{2}+\lambda\|\hat{\mathbf{x}}\|_{1}.$

    Inductively, we can derive (14).

    Next, we turn to the noisy case by following the idea of proof in[14].

    ######
    Theorem 4.4 (Noisy case).

    Assume that a noisy observed data $\mathbf{b}^{\delta}\in\mathbb{R}^{m}$ with $\|\mathbf{b}^{\delta}-\mathbf{b}\|_{2}\leq\delta$ is given, where $\mathbf{b}=\mathbf{A}\hat{\mathbf{x}}$. If the sequence $\{\mathbf{x}_{k}\}$ generated by SSKM method in Algorithm 1 are computed by $\mathbf{b}^{\delta}$. Then, with the same contraction factor $q_{i}$ as in the noiseless case,
    for the inexact step, we can have,

    $\mathbb{E}[\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\|_{2}]\leq\sqrt{\prod_{i=0}^{k}q_{i}\cdot\left(2\lambda\|\hat{\mathbf{x}}\|_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}\right)}+\sqrt{\frac{\sum_{i=0}^{k}q_{i}\delta^{2}}{2}},$

    and for the exact step,

    $\mathbb{E}[\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\|_{2}]\leq\sqrt{\prod_{i=0}^{k}q_{i}\cdot\left(2\lambda\|\hat{\mathbf{x}}\|_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}\right)}+\sqrt{\sum_{i=0}^{k}q_{i}\delta^{2}\cdot\frac{1+4\lambda\|\mathbf{A}\|_{1,2}}{2}}.$

    ######
    Proof 4.5.

    Define $\mathbf{x}_{k}^{\delta}:=\hat{\mathbf{x}}+\frac{b_{i_{k}}^{\delta}-b_{i_{k}}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}\cdot\mathbf{a}_{i_{k}}$, then we can find $\mathbf{x}^{\delta}_{k}\in H\left(\mathbf{a}_{i_{k}},b_{i_{k}}^{\delta}\right)$. By Lemma 3.1, we have the inequality below,

    (16)

    $\displaystyle D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k+1},\mathbf{x}_{k}^{\delta}\right)\leq D_{f}^{\mathbf{x}_{k}^{*}}\left(\mathbf{x}_{k},\mathbf{x}_{k}^{\delta}\right)-\frac{1}{2}\cdot\frac{\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}^{\delta}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}.$

    Unfolding the expression of $D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k+1},\mathbf{x}_{k}^{\delta}\right)$ and $D_{f}^{\mathbf{x}_{k}^{*}}\left(\mathbf{x}_{k},\mathbf{x}_{k}^{\delta}\right)$, and plugging $f(\hat{\mathbf{x}})$ into both sides of (16), we obtain the inequality

    (17)

    $\displaystyle D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k+1},\hat{\mathbf{x}}\right)$
    $\displaystyle\leq$
    $\displaystyle D_{f}^{\mathbf{x}_{k}^{*}}\left(\mathbf{x}_{k},\hat{\mathbf{x}}\right)-\frac{1}{2}\cdot\frac{\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}^{\delta}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}$

    $\displaystyle+\left\langle\mathbf{x}_{k+1}^{*}-\mathbf{x}_{k}^{*},\mathbf{x}_{k}^{\delta}-\hat{\mathbf{x}}\right\rangle.$

    In the remaining, we prove Theorem 4.4 from the cases of exact step and the in-exact step.

    Inexact step. For the inexact step, observe that $\mathbf{x}_{k+1}^{*}-\mathbf{x}_{k}^{*}=-\frac{\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}^{\delta}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}\cdot\mathbf{a}_{i_{k}}$. Then, we bound the inner product in (17) as below,

    (18)

    $\displaystyle\begin{aligned} \left\langle\mathbf{x}_{k+1}^{*}-\mathbf{x}_{k}^{*},\mathbf{x}_{k}^{\delta}-\hat{\mathbf{x}}\right\rangle&=\frac{b_{i_{k}}^{\delta}-b_{i_{k}}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}\cdot\left\langle\mathbf{x}_{k+1}^{*}-\mathbf{x}_{k}^{*},\mathbf{a}_{i_{k}}\right\rangle\\
    &=\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}-\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)\cdot\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}\right)}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}.\end{aligned}$

    By reformulating

    (19)

    $\displaystyle-\frac{1}{2}\cdot\frac{\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}^{\delta}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}$
    $\displaystyle=$
    $\displaystyle-\frac{1}{2}\cdot\frac{\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}$

    $\displaystyle+\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)\cdot\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}\right)}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}-\frac{1}{2}\cdot\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}$

    and combining (18) and (19) into (17), we have

    (20)

    $\displaystyle D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k+1},\hat{\mathbf{x}}\right)\leq D_{f}^{\mathbf{x}_{k}^{*}}\left(\mathbf{x}_{k},\hat{\mathbf{x}}\right)-\frac{1}{2}\cdot\frac{\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}+\frac{1}{2}\cdot\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}.$

    Similar to the proof in the noiseless situation, we have

    (21)

    $\displaystyle\mathbb{E}\left[D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k+1},\hat{\mathbf{x}}\right)\right]\leq q_{k}\cdot\mathbb{E}\left[D_{f}^{\mathbf{x}_{k}^{*}}\left(\mathbf{x}_{k},\hat{\mathbf{x}}\right)\right]+\frac{1}{2}\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2},$

    where
    $\sum_{\tau_{k}\in\binom{[m]}{\beta_{k}}}\frac{1}{2}\frac{\left(b_{i(\tau_{k},\mathbf{x}_{k})}^{\delta}-b_{i(\tau_{k},\mathbf{x}_{k})}\right)^{2}}{\sum_{\pi\in\binom{[m]}{\beta_{k}}}\|\mathbf{a}_{i(\pi,\mathbf{x}_{k})}\|^{2}}\leq\frac{1}{2}\cdot\frac{\binom{m}{\beta_{k}}\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2}}{\binom{m}{\beta_{k}}}=\frac{1}{2}\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2}.$

    Inductively, we get

    $\displaystyle\mathbb{E}\left[D_{f}^{\mathbf{x}_{k+1}^{*}}\left(\mathbf{x}_{k},\hat{\mathbf{x}}\right)\right]\leq\prod_{i=0}^{k}q_{i}\cdot\left(2\lambda\|\hat{\mathbf{x}}\|_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}\right)+\frac{\sum_{i=0}^{k}q_{i}}{2}\cdot\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2}.$

    Finally,

    $\displaystyle\mathbb{E}[\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\|_{2}]\leq\sqrt{\prod_{i=0}^{k}q_{i}\cdot\left(2\lambda\|\hat{\mathbf{x}}\|_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}\right)}+\sqrt{\frac{\sum_{i=0}^{k}q_{i}}{2}\cdot\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2}}.$

    Exact step. The idea to prove Theorem 4.4 in the exact step case is similar. But for the exact step, $\mathbf{x}_{k}^{*}=\mathbf{x}_{k}+\lambda\mathbf{s}_{k}$, where $\|\mathbf{s}_{k}\|_{\infty}\leq 1$. Noting that $\langle\mathbf{x}_{k+1},\mathbf{a}_{i_{k}}\rangle=b_{i_{k}}$, thus we derive that

    $\displaystyle\left\langle\mathbf{x}_{k+1}^{*}-\mathbf{x}_{k}^{*},\mathbf{x}_{k}^{\delta}-\hat{\mathbf{x}}\right\rangle$
    $\displaystyle=$
    $\displaystyle\frac{b_{i_{k}}^{\delta}-b_{i_{k}}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}\cdot\left(\left\langle\mathbf{x}_{k+1}-\mathbf{x}_{k},\mathbf{a}_{i_{k}}\right\rangle+\left\langle\mathbf{s}_{k+1}-\mathbf{s}_{k},\mathbf{a}_{i_{k}}\right\rangle\right)$

    $\displaystyle=$
    $\displaystyle\frac{b_{i_{k}}^{\delta}-b_{i_{k}}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}\cdot\left(b_{i_{k}}^{\delta}-b_{i_{k}}+b_{i_{k}}-\left\langle\mathbf{x}_{k},\mathbf{a}_{i_{k}}\right\rangle+\left\langle\mathbf{s}_{k+1}-\mathbf{s}_{k},\mathbf{a}_{i_{k}}\right\rangle\right)$

    $\displaystyle\leq$
    $\displaystyle\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)^{2}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}-\frac{\left(b_{i_{k}}^{\delta}-b_{i_{k}}\right)\cdot\left(\left\langle\mathbf{a}_{i_{k}},\mathbf{x}_{k}\right\rangle-b_{i_{k}}\right)}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}+\frac{2\lambda\left|b_{i_{k}}^{\delta}-b_{i_{k}}\right|\cdot\left\|\mathbf{a}_{i_{k}}\right\|_{1}}{\left\|\mathbf{a}_{i_{k}}\right\|_{2}^{2}}.$

    Utilizing the result above, and the proof in the case of inexact step, we have

    $\displaystyle\mathbb{E}[\|\mathbf{x}_{k+1}-\hat{\mathbf{x}}\|_{2}]\leq\sqrt{\prod_{i=0}^{k}q_{i}\cdot\left(2\lambda\|\hat{\mathbf{x}}\|_{1}+\|\hat{\mathbf{x}}\|_{2}^{2}\right)}+\sqrt{\sum_{i=0}^{k}q_{i}\left\|\mathbf{b}^{\delta}-\mathbf{b}\right\|_{\infty}^{2}\cdot\frac{1+4\lambda\|\mathbf{A}\|_{1,2}}{2}},$

    which completes the proof.

    Remark: Comparing the error bound between SSKM method using the exact step and inexact step, we can find that inexact step can improve the performance of SSKM method by a factor about $\frac{1+4\lambda\|\mathbf{A}\|_{1,2}}{2}$ compared with exact step. In the forthcoming experiments, this theoretical result will be verified.

    ##
    5 Numerical Simulation

    ###
    5.1 Experimental setup

    In this section, we will testify the performance of the SSKM method. The results of the tests demonstrate that SSKM method is numerically advantageous over the randomized sparse Kaczmarz method, which is denoted as SRK in this section.

    In the test, we are going to solve the linear system (1) by two type of different coefficient matrices $\mathbf{A}\in\mathbb{R}^{m\times n}$. One type is the random matrix by using the MATLAB function
    ’randn’, which produces independent standard normal entries for the matrix $\mathbf{A}$.
    Another type of matrices is originated in different applications such as linear programming, combinatorial optimization, DNA electrophoresis model, and world city network.

    In our implementations, solution $\hat{\mathbf{x}}\in\mathbb{R}^{n}$
    is randomly generated
    by using the MATLAB function ”randn”. The nonzero location is chosen randomly according to the sparsity. The observed data $\mathbf{b}\in\mathbb{R}^{m}$ is calculated by $\mathbf{A}\hat{\mathbf{x}}$.

    All computations are started from the
    initial vector $\mathbf{x}_{0}=\bm{0}$, and terminated once the mean square error (MSE), defined by

    (22)

    $\displaystyle\textrm{MSE}=\frac{\|\mathbf{x}_{k}-\hat{\mathbf{x}}\|_{2}^{2}}{\|\hat{\mathbf{x}}\|_{2}^{2}},$

    less than $\textrm{MSE}<10^{-6}$, or the number of iteration steps exceeds $200000$. The latter is labeled by ’–’ in Table 3. All of the experiments are carried out by using MATLAB(Version R2019a) on a personal computer with 2.70GHZ CPU(Intel(R) Core(TM) i7-6820HQ), 32GB memory, and Windows operating system(Windows 10).

    ###
    5.2 Parameter tuning

    In Algorithm 1, SSKM method is affected by the parameter $\lambda$ and sampling number $\beta$. Numerical tests will be applied to show how these two parameters influence the performance.

    Figure 1: Given $n=200$, for each $k$ and $m$, we apply 100 tests for different $\lambda$ and show the $\lambda$ under which we can obtain the least MSE.

    Parameter tuning for $\lambda$.
    In this test, let $n=200$, $m=140:20:300$(which means $m$ is range from 140 to 300 with interval 20), and $k=5:5:30$, the candidates of $\lambda$ are $0.01$, $0.1$, $1$, $5$, $10$. For a given $m$ and $n$, under each $\lambda$, we run experiments for $100$ times with different $\mathbf{A}$ and $\hat{\mathbf{x}}$ by SSKM method with exact step and record the $\lambda$ having the least MSE. $\beta=m/2$ in each step. The results are shown in Fig 1. We can find that the smaller the ratio $m/k$ is, the larger the $\lambda$ is can get a better performance. Especially, when $\lambda=1$, SSKM method can usually achieve the least MSE. As a result, we set $\lambda=1$ in our remaining tests.

    Parameter tuning for $\beta$.
    In this test, we set $n=500$, $m=200$, $k=20$, $\lambda=1$, and the candidates of $\beta$ are chosen from $1$, $\frac{m}{4}$, $\frac{m}{2}$, $m$. $\beta_{k}=\beta$ for all iterations. Under each $\beta$, we also run $100$ times independent experiments. We applied SSKM method by both exact step and inexact step and record their mean MSE and standard variation. The results are shown in Table 2. We can find that the best performance of SSKM method can be achieved when $\beta=50$ for inexact step and $\beta=100$ for exact step. Note that, the results of $\beta=50$ and $\beta=100$ are the same in a level for inexact method, but for exact method, $\beta=100$ can have an obvious advantage. So, in the remaining tests, we will set $\beta=\frac{m}{2}$.

    Table 2: The comparison of MSE among different $\beta$

    Name
    | $\beta=1$
    | $\beta=50$
    | $\beta=100$
    | $\beta=200$

    ---|---|---|---|---

    Inexact
    | Mean MSE
    | 0.01
    | $\mathbf{6.28\times 10^{-4}}$
    | $6.34\times 10^{-4}$
    | $1.73\times 10^{-3}$

    Variation
    | $1.71\times 10^{-3}$
    | $\mathbf{5.40\times 10^{-5}}$
    | $8.16\times 10^{-5}$
    | $8.71\times 10^{-15}$

    Exact
    | Mean MSE
    | $2.37\times 10^{-5}$
    | $1.77\times 10^{-13}$
    | $\mathbf{1.22\times 10^{-17}}$
    | $6.43\times 10^{-7}$

    Variation
    | $1.18\times 10^{-4}$
    | $1.07\times 10^{-12}$
    | $\mathbf{1.07\times 10^{-17}}$
    | $8.51\times 10^{-22}$

    ###
    5.3 Comparisons among state-of-the-arts

    In this experiment, SRK method will be compared with SSKM method. Three aspects will be considered to evaluate their performance, namely MSE, robustness, convergence rate.

    MSE comparison. In the test, given $n=200$, sparsity $k=5:5:30$, $m=140:20:300$. $\lambda=1$ and $\beta=\frac{m}{2}$. Under each $m$ and $k$, we record its mean MSE from 100 tests with different $\hat{\mathbf{x}}$ and $\mathbf{A}$. The results are shown in Figure 2.

    (a)  Recovery results of Exact-SRK.

    (b) Recovery results of Inexact-SRK.

    (c) Recovery results of Exact-SSKM.

    (d) Recovery results of Inexact-SSKM.

    Figure 2: Given $n=200$, testing the performance of different algorithms without noise.

    From Figure 2, we can find that for both methods, MSE increases with $m/n$ when $k$ is given. When $m/n$ is fixed, the MSE decreases with sparsity $k$. This phenomena is compatible with commonsense. Notice that, SSKM method can have a more stable performance and its corresponding MSE is lower. Moreover, we can also find that in the noiseless case, the results of SSKM method utilizing inexact step is worse than the exact step.

    Robustness comparison. In the test, given $n=200$, sparsity $k=5:5:30$, $m=140:20:300$, $\lambda=1$ and $\beta=\frac{m}{2}$. The level of the measurement noise is 10%. For each $m$ and $k$, we record its mean MSE by 100 tests with different $\hat{\mathbf{x}}$ and $\mathbf{A}$. The results are shown in Figure 3.

    (a) Recovery results of Exact-SRK.

    (b) Recovery results of Inexact-SRK.

    (c) Recovery results of Exact-SSKM.

    (d) Recovery results of Inexact-SSKM.

    Figure 3: Given $n=200$, testing the performance of different algorithms with the noise

    From Figure 3, we can find that both methods can resist the noise in some degree. When $m/k$ is larger, we can get a better performance. On the contrary, SSKM method utilizing inexact step performs better than exact step. In [14], similar phenomena can also be noticed. It is caused to the corruption by the noise, which makes the estimation calculated by exact step have larger bias. Thus, the efficiency of the exact step becomes lower.

    Convergence speed comparison. In this test, we only consider the noiseless condition. Given $n=200$, sparsity $k=30$, $m$ is chosen from $150,200,300$, $\lambda=1$ and $\beta=\frac{m}{2}$. For each $m$, we record its MSE from 100 tests with different $\hat{\mathbf{x}}$ and $\mathbf{A}$. The results are shown in Figure 4.

    From Figure 4, we can find that SSKM method can have a faster convergence rate and lower MSE than SRK method. This phenomena is due the greedy sampling rule, which picks out the most violated row. At the same time, we can also find that SSKM method utilizing exact step can have a faster convergence speed than utilizing inexact step.

    (a)

    (b)

    (c)

    Figure 4: Comparison of different methods for convergence speed. Thick line shows median over 100 trials, light area is between minimum and maximum, and darker area indicates 25th and 75th quantile(color figure online).

    ###
    5.4 Real data

    Real matrix.
    In this simulation, we will verify the performance of SSKM method under some real matrices[19]. The matrices are collected in The university of florida sparse matrix collection which are originated in different kinds of applications. In this test, under each matrix $\mathbf{A}$, we generate 100 different ground truth $\hat{\mathbf{x}}$ and calculate $\mathbf{A}\hat{\mathbf{x}}$ as observed data $\mathbf{b}$.

    CPU and IT mean the arithmetical average of the elapsed CPU
    times and the required iteration steps once the MSE is below $10^{-6}$ with respect to 100 times repeated runs of the
    corresponding method.
    $\text{Cond}(A)$ refers to the condition number of $\mathbf{A}$, and the density of $\mathbf{A}$ is also defined as

    $\displaystyle\text{Density}:=\frac{\text{number of nonzeros of $\mathbf{A}$}}{m\times n}.$

    .

    We only make comparison in the noiseless case. The SSKM and SRK method utilize exact step. The results are shown in Table 3.

    From Table 3, we can find out that the SSKM method can achieve the best performance. It requires least iterations and CPU time to terminate. Although the sampling rule of the SSKM method demands a larger burden of time at each iteration, the overall iteration times of it can remedy this drawback and achieve a fewer CPU time.

    Table 3: The results of different methods dealing with the real data.

    Name
    | model1
    | Trefethen_300
    | WorldCities
    | Trefethen_20
    | flower_5_1

    ---|---|---|---|---|---

    $m\times n$
    | $362\times 798$
    | $300\times 300$
    | $315\times 100$
    | $20\times 20$
    | $211\times 201$

    Density
    | 0.34%
    | 5.20%
    | 23.87%
    | 39.50%
    | 1.42%

    Cond($\mathbf{A}$)
    | 17.57
    | 1772.69
    | 66.00
    | 63.09
    | Inf

    Sparsity
    | 20
    | 20
    | 20
    | 20
    | 20

    RK
    | IT
    | –
    | –
    | 2977.9
    | 11886
    | –

    CPU
    | –
    | –
    | 0.41
    | 16.78
    | –

    SRK
    | IT
    | 6023.3
    | 11213
    | 9870.4
    | 27783
    | 4519.8

    CPU
    | 0.58
    | 0.56
    | 0.29
    | 0.62
    | 0.17

    SSKM
    | IT
    | 884.41
    | 2560.2
    | 2575.5
    | 9395.6
    | 864.72

    CPU
    | 0.47
    | 0.49
    | 0.69
    | 0.28
    | 0.15

    Phantom picture.
    In this test, we will study an academic tomography problem. The underlying model in the test problem consists of straight X-rays which penetrate the object, afterwards the damping is recorded. According to Lambert-Beer’s law, and after taking the logarithm of the recorded data, the damping is given as a line integral along the X-ray of the object’s attenuation coefficient, which is formulated as a linear equations model $\mathbf{A}\mathbf{x}=\mathbf{b}$.

    We used the AIRtools toolbox[20] to generate the matrix $\mathbf{A}$. In this test, $n=2500$, $m=2049$. The image of interest is shepplogan shown in Figure 5(a), which is sparse;
    thus we can apply sparse kaczmarz method to recover it from dump. In this test, we compare SSKM with SRK method. The results are shown in Figure 5. Here, both SSKM and SRK method use the exact step in the test.

    (a) Original.

    (b) Recovered by SSKM.

    (c) Recovered by SRK.

    (d) The curves of MSE for SSKM and SRK method.

    Figure 5: Experiment results. (a) is the original picture. (b) is the result recovered by SSKM method.(c) is the result recovered by the SRK method. (d) is the error curve.

    From Figure 5, we can find that the SSKM method has advantages over the SRK by the quality of the recovered image. Although the matrix is of rank deficiency, by utilizing the sparsity structure of image, we can still find the ground truth. It will shed on light on more applications to utilize prior information to recover signal of interest with fewer measurements.

    ##
    6 Conclusion

    In this paper, we introduce the SSKM method to find the sparse solutions of linear systems. It combines the Bregman projection and the Sampling Kaczmarz-Motzkin method. The former helps us to find the sparse solution implicitly; The latter is employed to accelerate the convergence rate of the method. Theoretically, we prove linear convergence of the SSKM method for the noiseless and noisy cases respectively. Numerical tests from both simulations and applications demonstrate the effectiveness of the proposed method.

    ##
    7 Acknowledgment

    The paper is granted by the National Natural Science Foundation:11971480, 61977065, and the Hunan Province excellent youngster Foundation:2020JJ3038.

    ## References

      *
    [1]

    S. Kaczmarz.

    Angenäherte auflösung von systemen lenearer gleichungen.

    Bull.int.acad.pol.sci.lett.a, 1937.

      *
    [2]

    G Richard, Robert.B, and T.H Gabor.

    Algebraic reconstruction techniques (art) for three-dimensional
    electron microscopy and x-ray photography.

    Journal of Theoretical Biology, 29(3):471,IN1,477–476,IN2,481,
    1970.

      *
    [3]

    K.M Sezan and H Stark.

    Applications of convex projection theory to image recovery in
    tomography and related areas.

    Image recovery:Theory and application, pages 451–462, 1987.

      *
    [4]

    C Yair.

    The mathematics of computerized tomography (classics in applied
    mathematics, vol. 32).

    Inverse Problems, 18(1):283–284, 2002.

      *
    [5]

    T Strohmer and R Vershynin.

    A randomized kaczmarz algorithm with exponential convergence.

    Journal of Fourier Analysis and Applications, 15(2):262, 2009.

      *
    [6]

    J Briskman and D Needell.

    Block kaczmarz method with inequalities.

    Journal of Mathematical Imaging and Vision, 52(3):385–396,
    2015.

      *
    [7]

    D Leventhal and A.S Lewis.

    Randomized methods for linear constraints: Convergence rates and
    conditioning.

    Mathematics of Operations Research, 35(3):641–654, 2010.

      *
    [8]

    D Needell and J.A Tropp.

    Paved with good intentions: Analysis of a randomized block kaczmarz
    method.

    Linear Algebra and its Applications, 441:199–221, 2014.

      *
    [9]

    A. Agaskar, C. Wang, and Y. M. Lu.

    Randomized kaczmarz algorithms: Exact mse analysis and optimal
    sampling probabilities.

    In 2014 IEEE Global Conference on Signal and Information
    Processing (GlobalSIP), pages 389–393, 2014.

      *
    [10]

    Y.C Eldar and D Needell.

    Acceleration of randomized kaczmarz method via the
    johnson—lindenstrauss lemma.

    Numerical Algorithms, 58(2):163–177, 2011.

      *
    [11]

    D Needell, R Ward, and N Srebro.

    Stochastic gradient descent, weighted sampling, and the randomized
    kaczmarz algorithm.

    Mathematical Programming, 155(1):1017–1025, 2014.

      *
    [12]

    D.A Lorenz, F Schöpfer, and S Wenger.

    The linearized bregman method via split feasibility problems:
    Analysis and generalizations.

    Siam Journal on Imaging Sciences, 7(2):1237–1262, 2014.

      *
    [13]

    D. A. Lorenz, S. Wenger, F. Schöpfer, and M. Magnor.

    A sparse kaczmarz solver and a linearized bregman method for online
    compressed sensing.

    In 2014 IEEE International Conference on Image Processing
    (ICIP), pages 1347–1351, 2014.

      *
    [14]

    F Schöpfer and D.A Lorenz.

    Linear convergence of the randomized sparse kaczmarz method.

    Mathematical Programming, (173):509–536, 2019.

      *
    [15]

    R.T Rockafellar and R.J.-B Wets.

    Variational analysis, volume 317.

    Springer Science & Business Media, 2009.

      *
    [16]

    M.J Lai and W.T. Yin.

    Augmented $l1$ and nuclear-norm models with a globally linearly
    convergent algorithm.

    Siam Journal Imaging Science, 6(2):1059–1091, 2013.

      *
    [17]

    H Zhang, L.Z Cheng, and W.T Yin.

    A dual algorithm for a class of augmented convex signal recovery
    models.

    Communication in Mathematical Science, 13(1):103–112, 2015.

      *
    [18]

    J Haddock and A Ma.

    Greed works: An improved analysis of sampling kaczmarz-motkzin.

    arXiv: Numerical Analysis, 2019.

      *
    [19]

    T.A Davis and Y.F Hu.

    The university of florida sparse matrix collection.

    ACM Transactions on mathematical software, 38(2):1–25, 2011.

      *
    [20]

    P.C Hansen and S Jakob.

    Air tools ii: algebraic iterative reconstruction methods, improved
    implementation.

    Numerical Algorithms, 2017.