Sparse Randomized Kaczmarz for Support
Recovery of Jointly Sparse Corrupted Multiple
Measurement Vectors

arXiv:1711.02743v2 [eess.SP] 3 Jan 2018

Natalie Durgin, Rachel Grotheer, Chenxi Huang, Shuang Li, Anna Ma, Deanna
Needell, and Jing Qin

Abstract While single measurement vector (SMV) models have been widely studied in signal processing, there is a surging interest in addressing the multiple measurement vectors (MMV) problem. In the MMV setting, more than one measurement vector is available and the multiple signals to be recovered share some commonalities such as a common support. Applications in which MMV is a naturally
occurring phenomenon include online streaming, medical imaging, and video recovery. This work presents a stochastic iterative algorithm for the support recovery
of jointly sparse corrupted MMV. We present a variant of the Sparse Randomized
Natalie Durgin
SpiceWorks
Austin, TX, 78746.
Rachel Grotheer
Goucher College
Baltimore, MD 21204.
e-mail: rachel.grotheer@goucher.edu
Chenxi Huang
Yale University
New Haven, CT 06511.
Shuang Li
Colorado School of Mines
Golden, CO 80401.
Anna Ma
Claremont Graduate University
Claremont, CA 91711.
e-mail: anna.ma@cgu.edu
Deanna Needell
University of California, Los Angeles
Los Angeles, CA 90095.
Jing Qin
Montana State University
Bozeman, MT 59717.

1

2

Kaczmarz algorithm for corrupted MMV and compare our proposed method with
an existing Kaczmarz type algorithm for MMV problems. We also showcase the
usefulness of our approach in the online (streaming) setting and provide empirical
evidence that suggests the robustness of the proposed method to the distribution of
the corruption and the number of corruptions occurring.

1 Introduction
In recent years, there has been a drastic increase in the amount of available data.
This so-called “data deluge” has created a demand for fast, iterative algorithms that
can be used to process large-scale data. Stochastic iterative algorithms, such as the
Randomized Kaczmarz Algorithm or Stochastic Gradient Descent, have become an
increasingly popular option for processing large-scale data [3, 10]. These methods
recover signals X ∈ Rn given a vector of measurements Y ∈ Rm and a measurement
matrix Φ ∈ Rm×n such that:
Y = ΦX,
(1)
without accessing the full measurement matrix in a single iteration. We refer to (1)
as a Single Measurement Vector (SMV) model. In the Multiple Measurement Vector (MMV) setting, one may have thousands of measurement vectors Y (·, j) pouring
in overtime. Each measurement vector Y (·, j) corresponds to a signal X (·, j) where
signals typically share a common property such as sparsity, smoothness, etc. For
simplicity, let Y = [Y (·,1) · · ·Y (·,T ) ] ∈ Rm×T and X = [X (·,1) · · · X (·,T ) ] ∈ Rn×T . Since
high-dimensional data is typically sparse in nature, a commonality of particular interest is jointly sparsity, or when the support of all signals are the same. In particular,
the support of a vector v is defined to be the set of indexes for which v is nonzero
i.e., supp(v) = {i : vi 6= 0}.
Plenty of works have been developed for the MMV setting, especially in applications such as line spectral estimation [14, 20] and modal analysis [13]. In particular,
the authors in these works extend the previous SMV-based algorithms as well as
theoretical analysis in [4, 19, 8] to the MMV case. The theoretical bound in [13]
also indicates that MMV settings could make the problem of compressed signal
recovery much easier than in the SMV setting. In particular, the number of measurements needed for perfect recovery in each signal decreases as the number of
signals increases.
As a motivating example, consider the diffuse optical tomography (DOT) where
the goal is to find small areas of high contrast corresponding to the location of cancerous cells [2]. Since cancerous cells have a much larger absorption coefficient than
healthy cells, the two-dimensional medical image can be interpreted as a sparse signal where each entry of the signal represents the absorption coefficient of a given
pixel and the nonzero entries correspond to tumor locations. In a hyperspectral DOT
setting, hundreds of different wavelengths are used to acquire a variety of images
of the same tissue, allowing practitioners to obtain a more accurate location of tu-

3

mors [11]. The result of the hyperspectral imaging process is a jointly sparse MMV,
where each wavelength produces a different image (or signal), and the joint support
across all images represents the locations of cancerous cells.
Signals may share support but it is improbable for them to be perfectly accurate.
Since sensing mechanisms are not impervious to error, signals can contain corruptions. Other sources of corruption in signal processing include spikes in power supply, defective hardware, and adversarial agents [12]. Going back to the hyperspectral
imaging example, “corruptions” in each signal may be caused by noncancerous cells
that absorb more light at a given wavelength than their neighbors. For example, if a
cell contains an anomalous amount of melanin, then it absorbs more light at a specific wavelength compared to a typical noncancerous cell [15, 5]. This produces a
large nonzero absorption coefficient in the location of a healthy cell, i.e., a corruption. These corrupt entries erroneously indicate the presence of cancerous cells in a
location with healthy cells.
Corruptions cause support recovery algorithms such as the MMV Sparse Randomized Kaczmarz (MMV-SRK) algorithm, which we describe in detail in Section
2, to fail due to the algorithmic dependence on the row norms of the signal approximation to estimate the support [1]. In the corrupt MMV settings, the availability
of multiple measurement vectors becomes vital to the estimate of the true support.
Clearly, if only a single measurement vector is available, there would be no way
to distinguish a corrupt nonzero entry without any additional assumptions on the
signal or corruption. Corrupt measurement signals have been studied in the context
of the SMV model. In [18] and [12], additive noise in the measurement scheme is
assumed to be sparse. Both works focus on the compressive sensing setting where
m  n.
The primary objective of this work is to design an algorithm for recovering the
support of jointly sparse, corrupt signals from large-scale MMV. We propose a
new online algorithm called Sparse Randomized Kaczmarz for Corrupted MMV
(cMMV-SRK) for support recovery. Note that the proposed algorithm can recover
the signals very well, but we mainly focus on support recovery in this work. Our
experiments show that the proposed algorithm outperforms the previously proposed
Kaczmarz type algorithm in recovering the joint support from MMV when the signals are corrupted.

1.1 Problem Formulation
The mathematical formulation of the introduced problem can be stated as follows.
Suppose one is given a set of linear measurements Y (·, j) ∈ Rm and a measurement
matrix Φ ∈ Rm×n such that:
Y (·, j) = ΦX (·, j)

for j = 1, . . . T,

(2)

4

with X (·, j) ∈ Rn . We assume that the data is large-scale, meaning we cannot access
all of Φ at once (m and/or n are too large) and must only operate on one row of Φ
at a time. We assume that the system is overdetermined (m  n) and that X (·, j) ’s are
jointly sparse such that supp(X (·, j) ) = S and |S | = k. For an n-dimensional vector
X (·, j) , let X (·, j) |s return X (·, j) with zeros in the n − s smallest (in magnitude) entries.
We also assume that each column of X contains one or more corruptions. In other
words, instead of supp(X (·, j) ) ⊂ S , the joint support set, the support of X (·, j) is:
supp(X (·, j) ) = S ∪ C j ,

C j ⊂ {1, . . . , n},

where C j is the “corrupt index set” and C j are not necessarily the same for every j.
In this work, our goal is to recover the joint support S from the given linear
measurements Y .
The remainder of this manuscript is organized in the following way. Section 2
discusses the Sparse Randomized Kaczmarz method and the MMV-SRK algorithm.
Section 3 provides a discussion on how corruptions can negatively impact the performance of MMV-SRK. Section 3 also presents our method, cMMV-SRK, a variant
of SRK which works in the corrupted signal setting. Numerical experiments using
this method are presented in Section 4 and we conclude with a summary of our
contributions and future directions in Section 5.

2 Related and Existing Work
2.1 Sparse Randomized Kaczmarz
In this work, we utilize the Sparse Randomized Kaczmarz algorithm to recover the
support of each column of X. The original Kaczmarz algorithm was first introduced
in the early 1900s by Kaczmarz himself and was revitalized as the Algebraic Reconstruction Technique in the early 1980s [10, 6]. The Randomized Kaczmarz Algorithm (RK) used here was first introduced by Strohmer and Vershynin and enjoys
an expected linear convergence rate to the solution of a consistent linear system
[17]. The Sparse Randomized Kaczmarz (SRK) algorithm is another variant designed specifically for overdetermined systems with sparse solutions. SRK has also
been empirically shown to solve underdetermined systems with sparse solutions as
well [16].
Algorithm 1 outlines the SRK algorithm. Note that ties are broken lexicographically in Step 5 of Algorithm 1 and all algorithms presented in this work. The estimated support size k̂ is a parameter of the algorithm and is typically chosen to be
larger than the true support size k. In this variant, the algorithm runs for a specified number of iterations (up to τ). However, any stopping criteria one would use
for an iterative algorithm e.g. terminating after the residual meets a certain criteria,
after the updates become small, etc. can be used. Algorithm 1 also differs from the
original presented algorithm by [16] in that at every iteration the support estimate

5

has size k̂ instead of starting with n and shrinking the size to k̂. We find that these
modifications do not significantly affect the behavior of SRK but will facilitate the
theoretical analysis of these methods.
Algorithm 1 Sparse Randomized Kaczmarz
1: procedure SRK(Φ ∈ Rm×n , Y ∈ Rm , k̂, τ)
2:
Initialize X 0 = 0n×1
3:
for t = 1, ..., τ do
kΦ (i,·) k22

4:

Choose row Φ (i,·) with probability

5:
6:

Set support estimate S t = supp(X t−1 |k̂ )
Set row weights

1 : l ∈ St
wl = √1 : l ∈ S t c

kΦk2F

. w ∈ Rn

t

. S t c is the complement set of S t
. a ∈ Rn is the weighted row of Φ

7:

Set a = w · Φ (i,·)

8:

Update X t = X t−1 + Y i −aX
kak2

9:
end for
10:
return X τ
11: end procedure

t−1

aT

2

Algorithm 1 has been shown empirically to find the solution to overdetermined,
consistent (i.e., a solution exists) linear systems but there are no theoretical results
supporting this. One can make a few observations about the behavior of SRK for
support recovery. Concerning the support size estimate k̂, it is clear that if k̂ < k then
the probability that the true support is contained in the support of the approximation
is 0, i.e., P (S ⊂ supp(X τ )) = 0. Additionally, if k̂ = n, then P (S ⊂ supp(X τ )) =
1. In regards to the choice of weighting, as t → ∞, √1t → 0 so that row elements
inside the support estimate contribute mostly to the approximation. If one has a
weighting function that decreases too rapidly, the true support may not be captured
in S t causing the algorithm to fail. If the weighting function decreases too slowly,
then the algorithm will converge more slowly.

2.2 SRK for MMV
Here we present a previous SRK-based approach to the MMV setting proposed
by [1]. Because we are assuming joint sparsity in the MMV model, the estimated
support of a signal reveals information about the support of all signals. The authors
of [1] present Algorithm 2 to leverage this idea. There are a few key aspects to note
about this version of the SRK algorithm. First, the algorithm is running one iteration
of SRK for every signal in the MMV model then updating the support estimate based

6

on the row norms of the estimate X t . Due to this, the algorithm does not lend itself
well to being extended for an online variant which only receives a small number
(possibly 1) of signals at a time. Second, the algorithm uses the same selected row
for each signal. It has been well observed that a random selection scheme reduces
the possibility of a poor choice of row ordering and it may be advantageous to allow
each signal to be projected onto a different randomly selected row [7, 9]
Algorithm 2 Sparse Randomized Kaczmarz for MMV
1: procedure MMV-SRK(Φ ∈ Rm×n , Y ∈ Rm×T , k̂, τ)
2:
Initialize X 0 = 0n×T
3:
for t = 1, . . . , τ do
kΦ (i,·) k22

4:

Choose row Φ (i,·) with probability

5:
6:

Set support estimate S t : k̂ indices with largest row norm of X t−1
Set row weights

1 : l ∈ St
wl = √1 : l ∈ S t c

kΦk2F

. w ∈ Rn

t

7:
8:
9:

. S t c is the complement set of S t
. a is the weighted row of Φ

Set a = w · Φ (i,·)
for j = 1, . . . , T do
Update X t(·, j) = X t−1
+
(·, j)

Y (i, j) −aX t−1
(·, j)

10:
end for
11:
Update X t = [X t(·,1) | . . . |X t(·,T ) ]
12:
end for
13:
return X t
14: end procedure

kak22

aT

3 Main Results
3.1 Corrupted MMV
To review, we are interested in constructing an algorithm that recovers the support of jointly sparse corrupted high-dimensional MMV, that is, where we can only
access one row of the measurement matrix Φ at a time. To this end, we propose
Algorithm 3, which we refer to as cMMV-SRK. We first note that the base of this
algorithm is the SRK algorithm (Algorithm 1), which is an effective algorithm for
large-scale problems due to its low memory footprint, requiring only one row of
the measurement matrix to be used at a time. cMMV-SRK has been adapted to the
MMV case using the intuition that the individual signals give us information about
the common support between all signals. We keep track of a bin or tally vector b that

7

estimates the true support of the signals. In particular, we use the nonzeros in b to
indicate the estimated joint support. This binning process allows the algorithm to be
robust in the face of corruptions in the signal, as the corruptions will receive a low
number of tallies compared to the entries in the true support because the corruptions
occur in random positions for every signal. Note that in the corrupted MMV case,
we expect Algorithm 2 to fail as the support estimate step relies on the `2 -norm of
the rows to be large if an index is in the support and small otherwise. The corruptions
may be so large that a single corruption in a row could lead to mis-identification of
the corrupt entry being in the joint support.
Finally, in Algorithm 3 we account for signals being processed one at a time, as
they are in an online or “streaming” setting.
For each signal, let τ̃ j be the number of SRK projections performed on X (·, j) and
let τ̃ = [τ̃1 · · · τ̃T ]. In the online setting, one can imagine that the amount of time
before the next signal is acquired may vary due to, for example, stalls in the measurement process. In order to improve the joint support estimate when τ̃ j varies, we
weight the binning based on τ = maxt τ̃. In other words, we let b q = b q + ττ̃ where
b q is the q-th entry of b . This reweighting scheme places a larger importance on
support estimates which have had more time (iterations) to improve. In the online
setting where τ̃ j s is not known a priori, τ can be set manually. We adopt the following notation for cMMV-SRK: Stj is the estimated support at the t th SRK iteration for
X (·, j) , and S t denotes the joint support estimate.
Algorithm 3 Sparse Randomized Kaczmarz for Corrupted MMV
1: procedure C MMV-SRK( Φ ∈ Rm×n , Y ∈ Rm×T , k̂, τ̃)
2:
Initialize X 0 = 0n×T , b = 0n×1 , τ = max j τ˜j
3:
for j = 1, . . . , T do
4:
for t = 1, . . . , τ̃ j do
kΦ (i,·) k22

5:

Choose row Φ (i,·) with probability

6:
7:

Set support estimate Stj = supp(X t−1
|)
(·, j) k̂
Set row weights

1 : l ∈ St
wl = √1 : l ∈ St c

kΦk2F

. w ∈ Rn

t

. St c is the complement set of St
. a is the weighted row of Φ

8:

Set a = w · Φ (i,·)

9:

Update X t(·, j) = X t−1
+
(·, j)
Stj

Y (i, j) −aX t−1
(·, j)
kak22

aT

= supp(X t(·, j) |k̂ )

10:
Set support estimate
11:
end for
τ̃
12:
If q ∈ Stj then b q = b q + τj
13:
Set initial support estimate for next signal S j = supp(bτ̃ |k̂ )
14:
end for
15:
return Joint support estimate S T
16: end procedure

8

If the number of inner iterations τ̃ j is large enough, the support estimate should be
such that it contains the joint support (along with the corruption index). Because we
are tallying the support estimate after every τ iterations, it is clear that the entries
in the joint support will have an overwhelming number of tallies compared to all
other entries. The experimental results in the next section support these claims and
we leave the analytical study of these algorithms for future work.

4 Experiments
In this section, we compare Algorithm 2 and Algorithm 3 under a variety of settings, specifically comparing the robustness of each algorithm in the presence of
corruptions in the signal. To test this robustness, we vary the number of corrupt entries, the distribution from which the corruptions are drawn, the number of columns
in X, and the number of projection computations τ̃ j made for each signal. In what
follows, we will refer to τ as the number of SRK iterations. These experiments are
summarized in Table 1. In all experiments, the results are averaged over 40 trials and
the nonzero entries of X are drawn independently and identically distributed (i.i.d.)
from N (0, 1). Note that on the x-axis we plot the number of “iterations” where a
single iteration is defined by a projection. In other words, the x-axis denotes every
time Step 9 is performed in Algorithm 3 and Algorithm 2.
Table 1: Summary of Experiment Parameters. This table provides a summary of
experiment parameters and Figure references for each experiment.
Figures
Figure 1a
Figure 1b
Figure 2a
Figure 2b
Figure 3
Figure 4

Φ entries Distribution of Corruptions Number of Corruptions τ̃ j
Gaussian
N (7, 1)
1
40
Uniform
N (7, 1)
1
80
Gaussian
N (0, 1)
1
40
Uniform
N (0, 1)
1
80
Gaussian
N (7, 1)
Varies
50
Gaussian
N (7, 1)
Varies
Varies

T
300
600
300
600
300
800

Figure 1 compares Algorithm 2 and Algorithm 3 with m = 1000, n = 100, and k =
10. The support size estimate is k̂ = 1.5k. To create X, we uniformly at random select
k of n indexes to be joint support S and set Y = ΦX. The corrupt entries are drawn
uniformly at random from {1, ...N} \ S . To start off, each signal has one corrupt
entry. We choose corruptions i.i.d. from N (7, 1) to simulate corruptions being large
spikes in the signal (possibly caused by system malfunction or an adversarial agent).
The maximum number of SRK iterations for each signal is τ = 30. In Figure 1a, we
i.i.d
create Φ ∈ Rm×n ∼ N (0, 1) and T = 300. In Figure 1b, the entries of Φ ∈ Rm×n
are drawn from a uniform distribution ranging from 0 to 1.We note that, in both
cases, Algorithm 3 is able to recover the full support after a sufficient number of
iterations, whereas Algorithm 2 is only able to recover at most about 20% of the

9

support, regardless of the number of iterations. Since Algorithm 2 relies on row
norms to estimate the joint support, it is to be expected that the relatively large value
of the corruption would cause it to often be erroneously chosen to be part of the
joint support estimate. As a result, this experiment highlights the advantage of the
binning in Algorithm 3 in the presence of a single corruption with a high magnitude.

(a) Φ ∼ N (0, 1)

(b) Φ ∼ Uni f ([0, 1])

Fig. 1: Comparing SRK and MMV-SRK for support recovery when there is a single
corrupt entry per signal whose magnitude is drawn from N (7, 1).
In Figure 2, we experiment further with the magnitude of the corruption. Here
we have that m = 1000, n = 100, and k = 10 but instead of the corrupt entries being
drawn from a mean 7 and standard deviation 1 distribution, it is drawn from a standard normal distribution, as are the entries in the support. This allows us to test the
robustness of our method to the choice of distribution. Note that Algorithm 2 is able
to find an increasingly accurate approximation for the support in this case, and will
be able to recover the full support after a sufficiently large number of iterations. Because the magnitudes of the corruptions are smaller, the algorithm still has a chance
of detecting the correct support using row norms to estimate S . However, Algorithm 3 is able to obtain an accurate support estimate much faster than Algorithm
2.
In the next two experiments, we test the robustness of our proposed algorithm
against multiple corruptions. In Figure 3, we allow for each signal to have multiple
corruptions. For each signal, or column of X, we uniformly at random select an integer from 1-3 to be the number of corruptions. The value of the corruptions are drawn
i.i.d. from N (7, 1) and an example of the resulting matrix can be seen in Figure 3a.
The performance of the methods can be seen in Figure 3b. We note that the results
of this experiment are very similar to those of the experiment in Figure 1 since the
corruptions are drawn from the same distribution. As we would expect, again due
to the use of row norms, in the presence of multiple corruptions Algorithm 2 gives
a less accurate estimate than in the presence of only one corruption drawn from this
distribution, recovering no more than about 15% of the support.

10

(a) Φ ∼ N (0, 1)

(b) Φ ∼ Uni f ([0, 1])

Fig. 2: Comparing SRK and MMV-SRK for support recovery when there is a single
corrupt entry per signal whose magnitude is drawn from N (0, 1).

(a) X matrix with 1-3 corruptions per signal
(b) Performance of Algorithm 3 with multiple corruptions

Fig. 3: Investigating the robustness of cMMV-SRK when a random number (multiple) corruptions are introduced. Here, a signal can have between 1 and 3 corruptions.
The corrupts magnitude of the corruptions are drawn from N (7, 1).

Finally, Figure 4 shows the performance results for Algorithm 3 in a simulated
online setting. Instead of allowing the algorithm to loop for a fixed number of projections for each signal, we have 90% of the signals with τ̃ j ∈ [5, 15] and the other
10% of signals with τ̃ j ∈ [95, 100]. The purpose of this is to simulate a variation
in the amount of time a system has to work with a signal. The longer runs represent stalls in the online setting. For each signal, we first draw a random Bernoulli
variable z with probability of success p = .1. If z = 1, then we choose an integer in
[95, 100] uniformly at random. If z = 0, then an integer in [5, 15] is chosen uniformly
at random. Algorithm 2 cannot be investigated under this setting as the support estimate relies on processing all signals in every iteration. We note that with respect to
other parameters, the only difference between this experiment and that in Figure 3
is the size of T . We choose T to be large enough such that the maximal number of
projections made is 15000 (as in Figure 3).

11

Fig. 4: Investigating the robustness of cMMV-SRK in a simulated online setting
when a random number (multiple) corruptions are introduced. Here, a signal can
have between 1 and 3 corruptions whose magnitudes are drawn from N (7, 1).

The experiments shown in this section highlights the usefulness of Algorithm 3
for support recovery of jointly sparse MMVs, especially in the presence of (even
quite large) corruptions. In each comparison between Algorithm 2 and Algorithm
3, our proposed method outperforms the previously proposed method for support
recovery. Additionally, the proposed method lends itself to the online setting.

5 Conclusion
In this work, we construct an algorithm for the support recovery of corrupted jointly
sparse MMV. Our empirical results demonstrate that the proposed algorithm outperforms the previously proposed method, MMV-SRK, for support recovery of jointly
sparse MMV, specifically when corruptions are present in the signal. Furthermore,
empirical evidence indicates that our method is robust to the magnitude of corruptions and the number of corruptions. This improvement is due to the fact that the
support estimate in Algorithm 2 depends on the row norms of the signals, which
in this case would be dominated by the corruption. In comparison, the estimate for
Algorithm 3 only depends on the number of times an index appears in the support
estimate of a signal. Lastly, our method lends itself well into the online setting when
measurement vectors are streaming in continuously. We leave the analytical study
of our method for future work.
Acknowledgements The initial research for this effort was conducted at the Research Collaboration Workshop for Women in Data Science and Mathematics, July 17-21 held at ICERM. Funding
for the workshop was provided by ICERM, AWM and DIMACS (NSF grant CCF-1144502). SL
was supported by NSF CAREER grant CCF−1149225. DN was partially supported by the Alfred
P. Sloan Foundation, NSF CAREER #1348721, and NSF BIGDATA #1740325. JQ was supported
by the faculty start-up fund of Montana State University.

12

References
[1] Aggarwal HK, Majumdar A (2014) Extension of sparse randomized kaczmarz
algorithm for multiple measurement vectors. arXiv preprint arXiv:14012288
[2] Arridge SR, Schotland JC (2009) Optical tomography: forward and inverse
problems. Inverse Problems 25(12)
[3] Bottou L (2010) Large-scale machine learning with stochastic gradient descent. In: Proceedings of COMPSTAT’2010, Springer, pp 177–186
[4] Candès EJ, Fernandez-Granda C (2014) Towards a mathematical theory
of super-resolution. Communications on Pure and Applied Mathematics
67(6):906–956
[5] Fodor L, Elman M, Ullmann Y (2011) Aesthetic Applications of Intense
Pulsed Light. Springer-Verlag London
[6] Gordon R, Bender R, Herman GT (1970) Algebraic reconstruction techniques
(ART) for three-dimensional electron microscopy and X-ray photography. J
Theoret Biol 29:471–481
[7] Hamaker C, Solmon DC (1978) The angles between the null spaces of X-rays.
J Math Anal Appl 62(1):1–23
[8] Heckel R, Soltanolkotabi M (2017) Generalized line spectral estimation via
convex optimization. IEEE Transactions on Information Theory
[9] Herman G, Meyer L (1993) Algebraic reconstruction techniques can be made
computationally efficient. IEEE Trans Medical Imaging 12(3):600–609
[10] Kaczmarz S (1937) Angenäherte auflösung von systemen linearer gleichungen. Bull Int Acad Polon Sci Lett Ser A pp 335–357
[11] Larusson F, Fantini S, Miller EL (2011) Hyperspectral image reconstruction
for diffuse optical tomography. Biomedical Optics Express 2(4):946–965
[12] Laska JN, Davenport MA, Baraniuk RG (2009) Exact signal recovery from
sparsely corrupted measurements through the pursuit of justice. In: Signals,
Systems and Computers, 2009 Conference Record of the Forty-Third Asilomar
Conference on, IEEE, pp 1556–1560
[13] Li S, Yang D, Tang G, Wakin MB (2017) Atomic norm minimization
for modal analysis from random and compressed samples. arXiv preprint
arXiv:170300938
[14] Li Y, Chi Y (2016) Off-the-grid line spectrum denoising and estimation
with multiple measurement vectors. IEEE Transactions on Signal Processing
64(5):1257–1269
[15] Lu G, Fei B (2014) Medical hyperspectral imaging: a review. Journal of
Biomedical Optics 19(1)
[16] Mansour H, Yilmaz Ö (2013) A fast randomized kaczmarz algorithm for
sparse solutions of consistent linear systems. CoRR abs/1305.3803, URL
http://arxiv.org/abs/1305.3803
[17] Strohmer T, Vershynin R (2009) Comments on the randomized
Kaczmarz method. J Fourier Anal Appl 15(4):437–440, DOI
10.1007/s00041-009-9082-0, URL http://dx.doi.org/10.1007/
s00041-009-9082-0

13

[18] Studer C, Kuppinger P, Pope G, Bolcskei H (2012) Recovery of sparsely corrupted signals. IEEE Transactions on Information Theory 58(5):3115–3130
[19] Tang G, Bhaskar BN, Shah P, Recht B (2013) Compressed sensing off the grid.
IEEE transactions on information theory 59(11):7465–7490
[20] Yang Z, Xie L (2014) Exact joint sparse frequency recovery via optimization
methods. IEEE Transactions on Signal Processing 64(19):5145–5157

