# Data-Time Tradeoffs for Optimal $k$-Thresholding Algorithms in Compressed
Sensing

###### Abstract

Optimal $k$-thresholding algorithms are a class of sparse signal recovery
algorithms that overcome the shortcomings of traditional hard thresholding
algorithms caused by the oscillation of the residual function. In this paper,
we provide a novel theoretical analysis for the data-time tradeoffs of optimal
$k$-thresholding algorithms. Both the analysis and numerical results
demonstrate that when the number of measurements is small, the algorithms
cannot converge; when the number of measurements is suitably large, the number
of measurements required for successful recovery has a negative correlation
with the number of iterations and the algorithms can achieve linear
convergence. Furthermore, the theory presents that the transition point of the
number of measurements is on the order of $k\log({en}/{k})$, where $n$ is the
dimension of the target signal.

Index Terms—  Compressed sensing, sparse optimization, data-time tradeoffs,
optimal $k$-thresholding

##  1 Introduction

Over the past few years, compressed sensing (CS) has attracted plenty of
attention in signal and image processing [1, 2, 3]. CS concerns the problem of
recovering a sparse signal from a small number of measurements
$\bm{y}=\bm{A}\bm{x}^{\star},$ where $\bm{x}^{\star}\in\mathbb{R}^{n}$ is the
target signal, and $\bm{A}\in\mathbb{R}^{m\times n}$ is the sensing matrix.
Finding the original signal by an underdetermined system of linear equations
can be formulated as the so-called $\ell_{0}$-minimization model:

$\min_{\bm{x}}\left\\{\|\bm{x}\|_{0}:\bm{y}=\bm{A}\bm{x}\right\\},$

or formulated as the following optimization problem with a sparsity constraint

$\min_{\bm{x}}\left\\{\|\bm{y}-\bm{A}\bm{x}\|_{2}^{2}:\|\bm{x}\|_{0}\leq
k\right\\},$ (1)

where $k$ is an integer. Although both problems are NP-hard [4], they can be
actually achieved by some efficient algorithms with high probability.

The plausible algorithms to solve such problems have been classified into
three categories: convex optimization [5, 6, 7], heuristic methods [8, 9] and
thresholding methods [10, 11, 12]. Here we focus on the thresholding methods.
Thresholding methods can be classified as soft thresholding [10], hard
thresholding [11], or optimal $k$-thresholding [12]. The soft thresholding
algorithms are established by considering the optimality condition of certain
convex problem. To describe the hard thresholding methods, it is convenient to
introduce the hard thresholding operator $\mathcal{H}_{k}(\bm{z})$, which
retains the $k$ largest absolute entries of $\bm{z}$ and sets the remaining
ones to be $0$. By connecting $\mathcal{H}_{k}(\bm{z})$ and the gradient
method for minimizing the residual function $\|\bm{y}-\bm{A}\bm{x}\|_{2}^{2}$,
Blumensath and Davies [11] proposed an elaborate hard thresholding algorithm
to solve the problem (1). It takes the scheme

$\bm{x}^{p+1}=\mathcal{H}_{k}(\bm{x}^{p}+\bm{A}^{T}(\bm{y}-\bm{A}\bm{x}^{p})),$
(2)

which is referred as iterative hard thresholding (IHT). By adding the pursuit
step such as minimizing the residual subject to the support determined by IHT,
Foucart [13] put forward an accelerated version called hard thresholding
pursuit (HTP). However, in many numerical situations, it demonstrates that the
residual reduction is irrelevant with the thresholding step, causing the
divergence of IHT, even HTP. By linking the thresholding step and residual
reduction together, Zhao [12, 14] proposed an iterative scheme

$\bm{w}(\bm{u}^{p})=\mathrm{min}\big{\\{}\|\bm{y}-\bm{A}(\bm{u}^{p}\odot\bm{w})\|^{2}_{2},~{}\textrm{{e}}^{T}\bm{w}=k,~{}\bm{w}\in\left\\{0,1\right\\}^{n}\big{\\}}$
(3)

where $\bm{u}^{p}$ is generated by the scheme (2), and defined a thresholding
operator $\mathcal{Z}_{k}^{\\#}(\bm{u}^{p})=\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})$
as the so-called optimal $k$-thresholding operator, and accordingly
established the optimal $k$-thresholding (OT) algorithms and optimal
$k$-thresholding pursuit (OTP) algorithms. To give a tractable algorithm, the
convex relaxed versions of OT and OTP algorithms, called ROT and ROTP
algorithms, were proposed. In ROT, the best $k$ approximation
$\mathcal{H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$ is directly set to the
next iteration, while the ROTP uses the pursuit step to that might be better
than $\mathcal{H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$ (see details in the
algorithms 1 and 2).

Under the assumption that the sensing matrix satisfies the restricted isometry
property (RIP), Zhao [12] provided the convergence analysis of ROT and ROTP.
However, there are two main drawbacks of using RIP in convergence analysis for
the algorithms: 1) RIP is for uniform recovery guarantees, which is looser
than non-uniform analysis. But in the algorithm, the optimal solution is fixed
and hence non-uniform analysis can be applied; 2) convergence analysis based
on RIP cannot characterize the relationship between accuracy, the number of
measurements and the number of iteration, which is of great importance in the
field related with data acquisition from underdetermined systems [15, 16].

To overcome these drawbacks, this paper establishes a novel non-uniform
convergence analysis for the relaxed optimal $k$-thresholding algorithms ROT
and ROTP and provides the data-time tradeoffs for the algorithms under sub-
Gaussian measurements. Theoretical analysis presents that when the number of
measurements is relatively large, with the increase of the number of
measurements, the number of iterations needed for successful reconstruction
decreases accordingly. Moreover, if the number of measurements is on the order
of $k\log({en}/{k})$ with a relatively large constant, we show that the
algorithms can achieve linear convergence rate.

##  2 Preliminaries

In this section, we introduce the algorithms ROT and ROTP and give several
facts using in the following sections. Note that the scheme (3) in OT and OTP
algorithms are in general NP-hard [4]. It is natural to consider the convex
relaxation of (3), which by using the operator $\mathcal{H}_{k}(\cdot)$,
leading to the ROT algorithm proposed in [12] as shown in Algorithm 1.

Algorithm 1 Relaxed optimal $k$-thresholding (ROT) algorithm

0: Matrix $\bm{A}$, measurements $\bm{y}$, sparsity level $k$, maximum
iteration number $P$

0: Estimated result $\bm{x}^{\star}$

1: Initialize $p=0,$ $\varepsilon,$ $\eta,$ and $\bm{x}^{0}$

2: repeat

3: $\bm{u}^{p}=\bm{x}^{p}+\eta\bm{A}^{T}(\bm{y}-\bm{A}\bm{x}^{p})$

4:
$\bm{w}(\bm{u}^{p})=\mathrm{argmin}_{\bm{w}}\big{\\{}\|\bm{y}-\bm{A}(\bm{u}^{p}\odot\bm{w})\|^{2}_{2},~{}\textrm{{e}}^{T}\bm{w}=k,~{}0\leq\bm{w}\leq\textrm{{e}}\big{\\}}$

5: $\bm{x}^{p+1}={\cal H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$

6: $p=p+1$

7: until $p>P$ or $\|{\bm{x}^{p}-\bm{x}^{p-1}}\|_{2}<\varepsilon$

Using the pursuit step over the support of ${\cal
H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$ in ROT leading to the relaxed
optimal $k$-thresholding pursuit (ROTP) algorithm as shown in Algorithm 2.

Algorithm 2 Relaxed optimal $k$-thresholding pursuit (ROTP) algorithm

0: Matrix $\bm{A}$, measurements $\bm{y}$, sparsity level $k$, maximum
iteration number $P$

0: Estimated result $\bm{x}^{\star}$

1: Initialize $p=0,$ $\varepsilon,$ $\eta,$ and $\bm{x}^{0}$

2: repeat

3: $\bm{u}^{p}=\bm{x}^{p}+\eta\bm{A}^{T}(\bm{y}-\bm{A}\bm{x}^{p})$

4:
$\bm{w}(\bm{u}^{p})=\mathrm{argmin}_{\bm{w}}\big{\\{}\|\bm{y}-\bm{A}(\bm{u}^{p}\odot\bm{w})\|^{2}_{2},~{}\textrm{{e}}^{T}\bm{w}=k,~{}0\leq\bm{w}\leq\textrm{{e}}\big{\\}}$

5: $\bm{v}={\cal H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$

6: $\mathbb{S}^{p+1}=\mbox{supp}(\bm{v})$

7:
$\bm{x}^{p+1}=\mathrm{argmin}_{\bm{x}}\big{\\{}\|\bm{y}-\bm{A}\bm{x}\|^{2}_{2},~{}\mbox{supp}(\bm{x})\subseteq\mathbb{S}^{p+1}\big{\\}}$

8: $p=p+1$

9: until $p>P$ or $\|{\bm{x}^{p}-\bm{x}^{p-1}}\|_{2}<\varepsilon$

###  2.1 Useful definitions

A random variable $x$ is called _Sub-Gaussian_ if it has finite sub-Gaussian
norm

$\left\lVert
x\right\rVert_{\psi_{2}}=\inf\left\\{t>0:\textbf{E}\exp\left(\frac{x^{2}}{t^{2}}\right)\leq
2\right\\}.$ (4)

Gaussian, Bernoulli and bounded random variables are typical sub-Gaussian
variable. A random vector $\bm{x}$ is called _Sub-Gaussian_ if for any
$\bm{y}\in\mathbb{R}^{n}$, $\left\langle\bm{x},\bm{y}\right\rangle$ is sub-
Gaussian. The corresponding norm is defined as

$\left\lVert\bm{x}\right\rVert_{\psi_{2}}=\sup_{\bm{y}\in\mathbb{S}^{n-1}}\left\lVert\left\langle\bm{x},\bm{y}\right\rangle\right\rVert_{\psi_{2}}.$
(5)

A random vector $\bm{x}$ is _isotropic_ if it satisfies

$\textbf{E}[\bm{x}\bm{x}^{T}]=\bm{I}.$ (6)

The _Gaussian complexity_ of a bounded subset $\mathbb{T}$ is defined as

$\gamma(\mathbb{T})=\textbf{E}\sup_{\bm{x}\in\mathbb{T}}|\left\langle\bm{g},\bm{x}\right\rangle|.$
(7)

and the _Gaussian width_ of a bounded subset $\mathbb{T}$ is defined as

$w(\mathbb{T})=\textbf{E}\sup_{\bm{x}\in\mathbb{T}}\left\langle\bm{g},\bm{x}\right\rangle.$
(8)

The above two quantities are on the same order [17]

$\frac{1}{3}(w(\mathbb{T})+\|\bm{y}\|_{2})\leq\gamma(\mathbb{T})\leq
2\left(w(\mathbb{T})+\|\bm{y}\|_{2}\right),\forall\,\bm{y}\in\mathbb{T}.$ (9)

###  2.2 Important facts

######  Fact 1 (Matrix deviation inequality, [18])

Let $\bm{A}$ be an ${m\times n}$ random matrix whose rows
$\\{\bm{A}_{i}\\}_{i=1}^{m}$ are independent, centered, isotropic and sub-
Gaussian vectors. For any bounded subset $\mathbb{D}\subseteq\mathbb{R}^{n}$
and $t\geq 0$, the inequality

$\sup\limits_{\bm{x}\in\mathbb{D}}\left|\left\lVert\bm{A}\bm{x}\right\rVert_{2}-\sqrt{m}\left\lVert\bm{x}\right\rVert_{2}\right|\leq
CK^{2}[\gamma(\mathbb{D})+t\cdot\mbox{rad}(\mathbb{D})]$

holds with probability at least $1-2\exp(-t^{2})$. Here,
$\mbox{rad}(\mathbb{D})=\sup_{\bm{x}\in\mathbb{D}}\left\lVert\bm{x}\right\rVert_{2}$,
$K=\max_{i}\left\lVert\bm{A}_{i}\right\rVert_{\psi_{2}}$ and $C>0$ is an
absolute constant.

######  Fact 2 (Gaussian width of $\ell_{0}$-balls, [19])

Let
$\mathbb{D}_{k}=\\{\bm{z}\in\mathbb{R}^{n}\big{|}\left\lVert\bm{z}\right\rVert_{0}\leq
k,\left\lVert\bm{z}\right\rVert_{2}=1\\}$. Then its Gaussian width satisfies

$\displaystyle w(\mathbb{D}_{k})\leq c\sqrt{k\log\frac{en}{k}}.$ (10)

##  3 Theoretical Guarantees

For the convenience of the convergence analysis, we first give some useful
lemmas. By assigning $\mathbb{D}\in\mathbb{S}^{n-1}$ and
$t=\gamma(\mathbb{D})$ from Fact 1, we have the following lemma.

###### Lemma 1

Let $\mathbb{D}\in\mathbb{S}^{n-1}$ and $t=\gamma(\mathbb{D})$ in Fact 1, then
for any $\bm{x}\in\mathbb{D}$, the inequality

$\sqrt{m}-2CK^{2}\gamma(\mathbb{D})\leq\left\lVert\bm{A}\bm{x}\right\rVert_{2}\leq\sqrt{m}+2CK^{2}\gamma(\mathbb{D})$

holds with probability at least $1-2\exp(-\gamma^{2}(\mathbb{D}))$.

The following lemmas will be frequently used in our later analysis (Theorems 1
and 2).

###### Lemma 2

Let $\bm{A}$ be an ${m\times n}$ random matrix as defined in Fact 1. Let
$\mathbb{D}_{k}=\\{y\big{|}\|y\|_{0}\leq k,\|y\|_{2}=1\\}$. Let
$\mathbb{L}\subseteq\\{1,\ldots,n\\}$ be an index set with cardinality $l$.
Let $\eta$ be a step size such that $\eta m\leq 1$. Then we have

a) For any $k$-sparse vector $\bm{v}\in\mathbb{R}^{n}$, with probability at
least $1-4\exp(-\gamma^{2}(\mathbb{D}_{k}+\mathbb{D}_{l}))$, we have
$\left\lVert[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}}\right\rVert_{2}\leq\max\left\\{s_{1},s_{2}\right\\}\cdot\left\lVert\bm{v}\right\rVert_{2}$,
where

$\displaystyle s_{1}$ $\displaystyle=1-\eta
m\cdot\frac{\sqrt{m}-6CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}},$
$\displaystyle s_{2}$
$\displaystyle=\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{2\sqrt{m}}+1\right).$

b) For any $\bm{x}\in\mathbb{R}^{n}$, with probability at least
$1-2\exp(-\gamma^{2}(\mathbb{D}_{l}))$, we have
$\left\lVert[\bm{A}^{T}\bm{x}]_{\mathbb{L}}\right\rVert_{2}\leq\left\lVert\bm{x}\right\rVert_{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{l}))$.

###### Lemma 3

Let $\mathbb{D}_{k}=\\{\bm{z}\big{|}\|\bm{z}\|_{0}\leq k,\|\bm{z}\|_{2}=1\\}$.
Then we have

a) $\gamma(\mathbb{D}_{2k})\leq 2\gamma(\mathbb{D}_{k}).$

b) $\gamma(\mathbb{D}_{k}+\mathbb{D}_{k})\leq 2\gamma(\mathbb{D}_{k}).$

c) $\mathbb{D}_{k}\subseteq\mathbb{D}_{l}$ and
$\gamma(\mathbb{D}_{k})\leq\gamma(\mathbb{D}_{l})$ for $k\leq l$.

Now we show the convergence analysis for ROT and ROTP algorithms based on the
above lemmas.

###### Theorem 1

Let $\bm{x}^{\star}\in\mathbb{R}^{n}$ be a $k$-sparse vector such that
$\bm{y}=\bm{A}\bm{x}^{\star}+\bm{n}$, where $\bm{n}\in\mathbb{R}^{m}$ is the
noise level. Let $\bm{A}$ be an ${m\times n}$ random matrix as defined in Fact
1, and $\left\\{\bm{x}^{p}\right\\}$ be the sequence generated by the
algorithm ROT. Let $\eta$ be the step size satisfying $\eta m\leq 1$. Then for
any sequence $\left\\{\bm{x}^{p}\right\\}$ generated by ROT, one has

$\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}\leq\rho_{1}\|\bm{x}^{\star}-\bm{x}^{p-1}\|_{2}+c_{2}\left\lVert\bm{n}\right\rVert_{2}$
(11)

with probability $1-c\exp(-\gamma^{2}(\mathbb{D}_{2k}))$, where $c>0$ is a
constant,

$\displaystyle\rho_{1}=$ $\displaystyle
c_{1}\max\left\\{r_{1},r_{2}\right\\},~{}~{}c_{2}=c_{21}+c_{22},$
$\displaystyle r_{1}=$ $\displaystyle 1-\eta
m\cdot\frac{\sqrt{m}-12CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}},$
$\displaystyle r_{2}=$
$\displaystyle\frac{6CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}}+1\right),$
$\displaystyle c_{1}=$
$\displaystyle\frac{4\sqrt{m}+4CK^{2}\gamma(\mathbb{D}_{k})}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})},$
$\displaystyle c_{21}=$
$\displaystyle\frac{3\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}+2}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})},$
$\displaystyle c_{22}=$
$\displaystyle\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k})).$

Let $m$ be suitably large satisfying $\rho_{1}<1$. Then
$\left\\{\bm{x}^{p}\right\\}$ can approximate $\bm{x}^{\star}$ with the error

$\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}\leq\rho_{1}^{p}\|\bm{x}^{\star}-\bm{x}^{0}\|_{2}+\frac{c_{2}}{1-\rho_{1}}\left\lVert\bm{n}\right\rVert_{2}$
(12)

with probability $1-c^{\prime}\exp(-\gamma^{2}(\mathbb{D}_{2k}))$, where
$c^{\prime}>0$ is a constant. In particular, when $\bm{n}=\bm{0}$,
$\left\\{\bm{x}^{p}\right\\}$ generated by ROT converges to $\bm{x}^{\star}$.

###### Theorem 2

Let the signal model be defined as in Theorem 1. Let $\eta$ be the step size
in the algorithm ROTP satisfying $\eta m\leq 1$. Then if the number of
measurements $m$ is large enough such that $\max\\{r_{1},r_{2}\\}<1$, for any
sequence $\left\\{\bm{x}^{p}\right\\}$ generated by ROTP, one has

$\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}\leq\rho_{2}\|\bm{x}^{\star}-\bm{x}^{p-1}\|_{2}+c_{3}\left\lVert\bm{n}\right\rVert_{2}$

with probability $1-c\exp(-\gamma^{2}(\mathbb{D}_{2k}))$, where

$\displaystyle\rho_{2}=$
$\displaystyle\rho_{1}/\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}},$
$\displaystyle c_{3}=$
$\displaystyle\frac{c_{2}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}}+\frac{\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))}{\left[1-\left(\max\\{r_{1},r_{2}\\}\right)\right]}.$

Let $m$ be suitably large such that $\rho_{2}<1$. Then
$\left\\{\bm{x}^{p}\right\\}$ can approximate $\bm{x}^{\star}$ with the error

$\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}\leq\rho_{2}^{p}\|\bm{x}^{\star}-\bm{x}^{0}\|_{2}+\frac{c_{3}}{1-\rho_{2}}\left\lVert\bm{n}\right\rVert_{2}$
(13)

with probability $1-c^{\prime}\exp(-\gamma^{2}(\mathbb{D}_{2k}))$. In
particular, when $\bm{n}=\bm{0}$, $\left\\{\bm{x}^{p}\right\\}$ generated by
ROTP converges to $\bm{x}^{\star}$.

###### Remark 1

It is clear that the above results shows the tradeoffs in ROT or ROTP between
the number of measurements and the number of iterations. Note that if $m$ is
larger than some value, the convergence rate $\rho_{1}$ or $\rho_{2}$ is less
than $1$; if not, the algorithm might diverge. Besides, notice that the value
$\rho_{1}$ or $\rho_{2}$ decreases with the increase of $m$, leading to a fast
convergence rate. Therefore, we can conclude that when the number of
measurements is large enough, the larger the number of measurements, the
faster convergence rate and hence the smaller number of iterations for fixed
accuracy. In particular, let the step size $\eta$ be equal to ${1}/{m}$. In
this case, the convergence rate satisfying $\rho_{1}<1$ for ROT algorithm is
ensured by $\sqrt{m}>C^{\prime}CK^{2}\gamma(\mathbb{D}_{2k})$, where
$C^{\prime}\approx 50.943$ is the positive root of the equation
$t^{2}-50t-48=0$. Similarly, in the ROTP algroithm, the convergence rate
satisfying $\rho_{2}<1$ is guaranteed by
$\sqrt{m}>C^{\prime\prime}CK^{2}\gamma(\mathbb{D}_{2k})$, where
$C^{\prime\prime}\approx 52.2614$ is the positive real root of the equation
$t^{4}-4t^{3}-2444t^{2}-4032t-2880=0$.

###### Remark 2

Note that in the noise-free situation, i.e., $\bm{n}=\bm{0}$, if the
conditions $\sqrt{m}>50.943CK^{2}\gamma(\mathbb{D}_{2k})$ and $\eta m\leq 1$
hold, the convergence rate in Theorem 1 is strictly less than 1. It means that
a linear convergence rate can be achieved by the algorithm ROT. Similarly, the
algorithm ROTP also achieves a linear convergence rate when certain condition
holds.

###### Remark 3

It should be pointed out that the Gaussian complexity $\gamma(\mathbb{D}_{k})$
and the Gaussian width $w(\mathbb{D}_{k})$ have the same order due to Eq. (9).
This, combined with Fact 2, tells us that $\gamma(\mathbb{D}_{k})$ is on the
order of $\sqrt{k\log({en}/{k})}$, where $n$ and $k$ are the dimension and
sparsity of the target signal, respectively. Based on the main results in
Theorems 1, 2 and Remark 1, it is not hard to see that the transition point of
the number of measurements is on the order of $k\log({en}/{k})$.

(a) ROT algorithm

(b) ROTP algorithm

Fig. 1: The phase transition curves of optimal $k$-thresholding algorithms in
compressed sensing: (a) ROT algorithm. (b) ROTP algorithm. The brightness of
each point denotes the probability of successful reconstruction, ranging from
black (0%) to white (100%).

##  4 Simulations

In this section, we make simulations to validate the theory. To show the
tradeoffs between the number of measurements $m$ and the number of iterations
$p$, we draw the phase transitions for ROT and ROTP algorithms. The target
signal $\bm{x}^{\star}$ is a $k$-sparse $n$-dimensional vector, whose nonzero
entries follow standard Gaussian distribution. The sensing matrix
$\bm{A}\in\mathbb{R}^{m\times n}$ is a Bernoulli matrix whose entries are
independent symmetric Bernoulli variable. In this simulation, $\bm{x}^{0}$ is
set to be $\bm{0}$, the number of dimension is set to be $n=50$, the sparsity
is set to be $k=3$ and the tolerance thresholding is set to be
$\varepsilon=10^{-2}$. For a pair of $m$ and $p$, we run $50$ Monte Carlo
trials and count the number of successful trials which satisfy
${\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}}/{\left\lVert\bm{x}^{\star}\right\rVert_{2}}\leq\varepsilon$.
Then we calculate the successful probability for each pair and get the phase
transition results.

The numerical results are shown in Fig. 1. Note the white area for ROTP
algorithm is much larger than that for ROT algorithm, which means ROTP
algorithm has a much better recovery performance than ROT algorithm. Both
algorithms illustrate the data-time tradeoffs as discussed in the Remarks. The
curves present that when the number of measurements is smaller than a certain
number, the algorithms cannot recover the target signal. Moreover, when the
number of measurements is larger than a certain number, the number of
measurements required for successful recovery decreases with the increase of
the number of iterations and the number of iterations required for successful
recovery decreases with the increase of the the number of measurements. The
observed phenomenon in the simulations corresponds with our theoretical
results in Theorems 1 and 2.

##  5 Conclusion and future work

In this paper, we have provided the analysis for the data-time tradeoffs for
optimal $k$-thresholding algorithms in compressed sensing. The theory has
shown that the number of measurements should be suitably large to guarantee
the convergence of the optimal $k$-thresholding algorithms. It also presented
that the number of measurements required for successful reconstruction has a
negative correlation with the number of iterations. Simulations have been
provided to validate the correctness of our theory.

For future work, it would be interesting to extend the data-time tradeoffs
analysis for optimal $k$-thresholding algorithms from compressed sensing to
other important linear inverse problems such as quantized compressed sensing,
corrupted sensing and so on.

## References

  * [1] Emmanuel J Candès and Terence Tao,  “Decoding by linear programming,”  IEEE Transactions on Information Theory, vol. 51, no. 12, pp. 4203–4215, 2005.
  * [2] David L Donoho,  “Compressed sensing,”  IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289–1306, 2006.
  * [3] Emmanuel J Candès,  “Compressive sampling,”  Proceedings of International Congress of Mathematics, vol. 3, pp. 1433–1452, 2006.
  * [4] Balas Kausik Natarajan,  “Sparse approximate solutions to linear systems,”  SIAM Journal on Computing, vol. 24, no. 2, pp. 227–234, 1995.
  * [5] Scott Shaobing Chen, David L Donoho, and Michael A Saunders,  “Atomic decomposition by basis pursuit,”  SIAM Review, vol. 43, no. 1, pp. 129–159, 2001.
  * [6] Emmanuel J Candès, Michael B Wakin, and Stephen P Boyd,  “Enhancing sparsity by reweighted $\ell_{1}$ minimization,”  Journal of Fourier Analysis and applications, vol. 14, no. 5-6, pp. 877–905, 2008.
  * [7] Yun-Bin Zhao and Duan Li,  “Reweighted $\ell_{1}$ minimization for sparse solutions to underdetermined linear systems,”  SIAM Journal on Optimization, vol. 22, no. 3, pp. 1065–1088, 2012\.
  * [8] Stéphane G Mallat and Zhifeng Zhang,  “Matching pursuits with time-frequency dictionaries,”  IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397–3415, 1993.
  * [9] Wei Dai and Olgica Milenkovic,  “Subspace pursuit for compressive sensing signal reconstruction,”  IEEE transactions on Information Theory, vol. 55, no. 5, pp. 2230–2249, 2009.
  * [10] Ingrid Daubechies, Michel Defrise, and Christine De Mol,  “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,”  Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, vol. 57, no. 11, pp. 1413–1457, 2004.
  * [11] Thomas Blumensath and Mike E Davies,  “Iterative hard thresholding for compressed sensing,”  Applied and Computational Harmonic Analysis, vol. 27, no. 3, pp. 265–274, 2009.
  * [12] Yun-Bin Zhao,  “Optimal k-thresholding algorithms for sparse optimization problems,”  SIAM Journal on Optimization, vol. 30, no. 1, pp. 31–55, 2020.
  * [13] Simon Foucart,  “Hard thresholding pursuit: an algorithm for compressive sensing,”  SIAM Journal on Numerical Analysis, vol. 49, no. 6, pp. 2543–2563, 2011.
  * [14] Yun-Bin Zhao,  Sparse optimization theory and methods,  CRC Press, 2018.
  * [15] Samet Oymak, Benjamin Recht, and Mahdi Soltanolkotabi,  “Sharp time–data tradeoffs for linear inverse problems,”  IEEE Transactions on Information Theory, vol. 64, no. 6, pp. 4129–4158, 2017.
  * [16] Jinchi Chen and Yulong Liu,  “Data-time tradeoffs for corrupted sensing,”  IEEE Signal Processing Letters, vol. 25, no. 7, pp. 941–945, 2018\.
  * [17] Jinchi Chen and Yulong Liu,  “Stable recovery of structured signals from corrupted sub-gaussian measurements,”  IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2976–2994, 2018.
  * [18] Roman Vershynin,  “Four lectures on probabilistic methods for data science,”  The Mathematics of Data, IAS/Park City Mathematics Series, pp. 231–271, 2017.
  * [19] Martin J Wainwright,  High-dimensional statistics: A non-asymptotic viewpoint, vol. 48,  Cambridge University Press, 2019.

##  Appendix A Proof of Theorem 1

Before proving the theorem, we review some important facts.

######  Fact A.1 ([12])

Let $\bm{x}$ be a $k$-sparse vector and $\mathbb{S}$ be the support of
$\bm{x}$. Let $\bm{w}^{p}$ be a solution to the problem (A.2), and
$\bm{v}={\cal H}_{k}(\bm{u}^{p}\odot\bm{w}^{p})$ be a vector with the support
$\mathbb{S}^{p+1}$. Then we have

$\|\bm{x}-\bm{v}\|_{2}\leq\|(\bm{u}^{p}\odot\bm{w}^{p}-\bm{x})_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}+\|(\bm{u}^{p}\odot\bm{w}^{p}-\bm{x})_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}$

######  Fact A.2 ([12])

Let $k$ and $\overline{k}$ be two integer numbers such that
$0\leq\overline{k}\leq k$. Let
$\bm{w}\in\mathcal{W}^{k}=\left\\{\bm{w}:\bm{e}^{T}\bm{w}=k,~{}\bm{w}\in\left\\{0,1\right\\}^{n}\right\\}$
be the vector with the support $\mathbb{S}$, and $\overline{\mathbb{S}}$ be
the complementary set. Let $\overline{\mathbb{S}}$ has the disjointed
partition $\mathbb{S}_{i},~{}i=1,...,\overline{n}$ such that

$\overline{\mathbb{S}}=\mathbb{S}_{1}\cup\mathbb{S}_{2}\cup...\cup\mathbb{S}_{\overline{n}-1}\cup\mathbb{S}_{\overline{n}}$

satisfying the following properties:

  * •

$|\mathbb{S}_{i}|\leq k$ for $i=1,2,...,\overline{n}-1$ and
$|\mathbb{S}_{\overline{n}}|\leq\overline{k}<k$;

  * •

$\mathbb{S}_{i}$ is the index set for the $i$th largest $k$ components in
$\bm{w}_{\overline{\mathbb{S}}}$.

Let $\alpha_{(i)}$ denote the largest entry of $\bm{w}$ on the support
$\mathbb{S}_{i}$. Then we have

$\sum_{i=1}^{\overline{n}}\alpha_{(i)}\leq 2-\frac{1}{k}<2.$

Now we are ready to prove the theorem. By using
$\bm{u}^{p}=\bm{x}^{p}+\eta\bm{A}^{T}(\bm{y}-\bm{A}\bm{x}^{p})$ and
$\bm{y}=\bm{A}\bm{x}^{\star}+\bm{n}$, we obtain

$\bm{x}^{\star}-\bm{u}^{p}=(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})-\eta\bm{A}^{T}\bm{n}.$
(A.1)

Let $\bm{w}(\bm{u}^{p})$ be a solution to the following problem in ROT at the
$p$-th iteration

$\min_{\bm{w}}\left\\{\|\bm{y}-\bm{A}(\bm{u}^{p}\odot\bm{w})\|^{2}_{2}:~{}\textrm{{e}}^{T}\bm{w}=k,~{}\bm{0}\leq
w\leq\textrm{{e}}\right\\}.$ (A.2)

Then the next iteration is updated by $\bm{x}^{p+1}\in{\cal
H}_{k}(\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}))$. Let $\mathbb{S}^{p+1}$ and
$\mathbb{S}$ be the support of $\bm{x}^{p+1}$ and $\bm{x}^{\star}$,
respectively. By Lemma A.1, we have

$\|\bm{x}^{\star}-\bm{x}^{p+1}\|_{2}\leq\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}+\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}.$
(A.3)

Now we estimate the first term of the right side of (A.3). Due to the fact
that $\bm{x}^{\star}_{\mathbb{S}^{p+1}\setminus\mathbb{S}}=0$ and
$\bm{w}_{i}^{p}\in[0,1],i=1,\ldots,n$, we have

$\displaystyle\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p}\right]-\bm{x}^{\star})_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}$
$\displaystyle=\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}$
$\displaystyle=\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}$
$\displaystyle=\|\left[(\eta\bm{A}^{T}\bm{n}-(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p}))\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}$
$\displaystyle\leq\eta\|\left[\bm{A}^{T}\bm{n}\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}+\|\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2},$
(A.4)

where the third equality follows from (A.1). By using Lemma 2 with
$\bm{v}=\bm{x}^{\star}-\bm{x}^{p}\in\mathbb{D}_{2k}$ and
$\mathbb{L}=\mathbb{S}^{p+1}\setminus\mathbb{S}$, we can estimate the two
terms in the above inequality. Note that $\mathbb{D}_{l}=\mathbb{D}_{k}$. Then
we have

$\left\lVert[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\right\rVert_{2}\leq\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}$
(A.5)

and

$\left\lVert[\bm{A}^{T}\bm{n}]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\right\rVert_{2}\leq\left\lVert\bm{n}\right\rVert_{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))$
(A.6)

where

$r_{1}=1-\eta
m\cdot\frac{\sqrt{m}-6CK^{2}\gamma(\mathbb{D}_{2k}+\mathbb{D}_{k})}{\sqrt{m}},~{}~{}r_{2}=\frac{3CK^{2}\gamma(\mathbb{D}_{2k}+\mathbb{D}_{k})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{2k}+\mathbb{D}_{k})}{2\sqrt{m}}+1\right).$

Note that
$\gamma(\mathbb{D}_{2k}+\mathbb{D}_{k})\leq\gamma(\mathbb{D}_{2k}+\mathbb{D}_{2k})\leq
2\gamma(\mathbb{D}_{2k})$ which follows from b) and c) in Lemma 3. The
constants $r_{1}$ and $r_{2}$ can be simplified to

$r_{1}=1-\eta
m\cdot\frac{\sqrt{m}-12CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}},~{}~{}r_{2}=\frac{6CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}}+1\right).$
(A.7)

Combining (A.4), (A.5) and (A.6) yields that

$\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\setminus\mathbb{S}}\|_{2}\leq\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+\eta\left\lVert\bm{n}\right\rVert_{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k})).$
(A.8)

Next we estimate the second term of the right side of (A.3). By using Lemma 1
with $\mathbb{D}=\mathbb{D}_{2k}$, we have

$\left\lVert\bm{A}\frac{\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}}{\|\left[\bm{u}^{p}\odot\bm{w}(u^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}}\right\rVert_{2}\geq\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})$
(A.9)

with probability at least $1-2\mathrm{exp}(-\gamma^{2}(\mathbb{D}_{2k}))$.
Note that

$\displaystyle\|y-\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})\right]\|_{2}$
$\displaystyle=\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]-\bm{n}\|_{2}$
$\displaystyle=\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}+\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}-\bm{n}\|_{2}$
$\displaystyle\geq\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}-\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}$
$\displaystyle~{}~{}~{}~{}-\|\bm{n}\|_{2}$
$\displaystyle\geq\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}(\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k}))-\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}$
$\displaystyle~{}~{}~{}~{}-\|\bm{n}\|_{2},$ (A.10)

where the first equality uses $y=\bm{A}\bm{x}^{\star}+\bm{n}$, the first
inequality uses the triangle inequality and the last inequality follows from
(A.9). Thus we have

$\|\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\mathbb{S}^{p+1}\cup\mathbb{S}}\|_{2}\leq\frac{1}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})}\left\\{\|y-\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})\right]\|_{2}+T+\|\bm{n}\|_{2}\right\\},$
(A.11)

where
$T=\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}$.
Let $\hat{\bm{w}}\in\mathcal{W}^{(k)}$ be the vector such that
$\bm{x}^{\star}=\bm{x}^{\star}\odot\hat{\bm{w}}.$

$\displaystyle\|y-\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})\right]\|_{2}$
$\displaystyle\leq\|y-\bm{A}(\bm{u}^{p}\odot\hat{\bm{w}})\|_{2},$
$\displaystyle=\|\bm{A}\bm{x}^{\star}+\bm{n}-\bm{A}(\bm{u}^{p}\odot\hat{\bm{w}})\|_{2}=\|[\bm{A}(\bm{x}^{\star}-\bm{u}^{p})\odot\hat{\bm{w}}]+\bm{n}\|_{2},$
$\displaystyle\leq\|\bm{A}\left[(\bm{x}^{\star}-\bm{u}^{p})\odot\hat{\bm{w}}\right]\|_{2}+\|\bm{n}\|_{2},$
$\displaystyle\leq(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\|(\bm{x}^{\star}-\bm{u}^{p})\odot\hat{\bm{w}}\|_{2}+\|\bm{n}\|_{2},$
(A.12)

where the second inequality uses the triangle inequality and the last
inequality follows from Lemma 1 with $\mathbb{D}=\mathbb{D}_{k}$. Using the
fact that
$\bm{x}^{\star}-\bm{u}^{p}=(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})-\eta\bm{A}^{T}\bm{n}$
and Lemma 2 yields

$\displaystyle\|(\bm{x}^{\star}-\bm{u}^{p})\odot\hat{\bm{w}}\|_{2}$
$\displaystyle\leq\left\lVert\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})\right]\odot\hat{\bm{w}}\right\rVert_{2}+\eta\left\lVert\left[\bm{A}^{T}\bm{n}\right]\odot\hat{\bm{w}}\right\rVert_{2},$
$\displaystyle\leq\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2},$
(A.13)

where $r_{1}$ and $r_{2}$ are given in (A.7). Combining (A) and (A) leads to

$\|y-\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})\right]\|_{2}\leq(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+\left[\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}+1\right]\|\bm{n}\|_{2}.$
(A.14)

In the last part of the proof, we estimate the term $T$ in (A.11). Due to the
fact that $\bm{x}^{*}_{\overline{S^{p+1}\cup S}}=0$, $T$ has the following
form

$T=\|\bm{A}\left[\bm{u}^{p}\odot\bm{w}(\bm{u}^{p})-\bm{x}^{\star}\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}=\|\bm{A}\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}.$

Let $\mathbb{T}_{i},~{}i=1,2,...,\overline{n}$ be the disjoint subset of
$\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}$ such that

$\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}=\mathbb{T}_{1}\cup\mathbb{T}_{2}\cup...\cup\mathbb{T}_{\overline{n}}$

and satisfying the following properties

  * •

$|\mathbb{T}_{i}|=k$ for all $i=1,2,...,\overline{n}$ and
$|\mathbb{T}_{\overline{n}}|=\overline{k}<k$;

  * •

$\mathbb{T}_{i}$ is the index set for $i$th largest $k$ components in
$\bm{w}(\bm{u}^{p})_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}$.

It is obvious that
$|\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}|=(\overline{n}-1)k+\overline{k}$.
Based on such partition of $\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}$, the
term
$\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}$
can be written as

$\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}=\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{1}}+\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{2}}+...+\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{\overline{n}}}.$

Thus $T$ can be reduced to

$\displaystyle T$
$\displaystyle=\|\sum_{i}^{\overline{n}}\bm{A}\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}\leq\sum_{i}^{\overline{n}}\|\bm{A}\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}$
(A.15)
$\displaystyle\leq(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\sum_{i}^{\overline{n}}\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2},$
(A.16)

where the last inequality follows from Lemma 1. By using the Eq. (A.1) and the
triangle inequality, for each term
$\|[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})]_{\mathbb{T}_{i}}\|_{2}$,
we have

$\displaystyle\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}$
$\displaystyle=\|\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})\odot\bm{w}(\bm{u}^{p})-\eta\bm{A}^{T}\bm{n}\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}$
$\displaystyle\leq\|\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}+\eta\|\left[\bm{A}^{T}\bm{n}\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}.$

Define
$\alpha_{i}\triangleq\max\left\\{(\bm{w}(\bm{u}^{p}))_{j}:~{}j\in\mathbb{T}_{i}\right\\}$,
then

$\displaystyle\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}$
$\displaystyle\leq\alpha_{i}\|\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p})\right]_{\mathbb{T}_{i}}\|_{2}+\eta\alpha_{i}\|\left[\bm{A}^{T}\bm{n}\right]_{\mathbb{T}_{i}}\|_{2},$
$\displaystyle\leq\alpha_{i}\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+\eta\alpha_{i}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2},$

where $r_{1}$ and $r_{2}$ are given in (A), and thus

$\sum_{i}^{\overline{n}}\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\mathbb{T}_{i}}\|_{2}\leq\sum_{i}^{\overline{n}}\alpha_{i}\max\left\\{r_{1},r_{2}\right\\}\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+\eta\sum_{i}^{\overline{n}}\alpha_{i}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}.$

Using Lemma A.2 with
$\bm{w}=\bm{w}(\bm{u}^{p}),~{}\mathbb{S}=\mathbb{S}^{p+1}\cup\mathbb{S}$ and
$\mathbb{S}_{i}=\mathbb{T}_{i}$ yields

$T\leq
2\max\left\\{r_{1},r_{2}\right\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\cdot\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}+2\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}\left\lVert\bm{n}\right\rVert_{2}.$
(A.17)

Merging (A.17), (A.11) and (A.14) leads to

$\displaystyle\|\left[(\bm{u}^{p}-\bm{x}^{\star})\odot\bm{w}(\bm{u}^{p})\right]_{\overline{\mathbb{S}^{p+1}\cup\mathbb{S}}}\|_{2}$
$\displaystyle\leq\frac{3\max\left\\{r_{1},r_{2}\right\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})}\left\lVert\bm{x}^{\star}-\bm{x}^{p}\right\rVert_{2}$
$\displaystyle~{}~{}~{}~{}+\frac{3\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}+2}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})}\left\lVert\bm{n}\right\rVert_{2},$

which combined with (A.3) and (A.8) leads to

$\|\bm{x}^{\star}-\bm{x}^{p+1}\|_{2}\leq
c_{1}\max\left\\{r_{1},r_{2}\right\\}\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}+c_{2}\left\lVert\bm{n}\right\rVert_{2},$
(A.18)

where

$\displaystyle c_{1}$
$\displaystyle=\frac{4\sqrt{m}+6CK^{2}\gamma(\mathbb{D}_{k})-2CK^{2}\gamma(\mathbb{D}_{2k})}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})}\leq\frac{4\sqrt{m}+4CK^{2}\gamma(\mathbb{D}_{k})}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})},$
$\displaystyle c_{2}$
$\displaystyle=\frac{3\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}+2}{\sqrt{m}-2CK^{2}\gamma(\mathbb{D}_{2k})}+\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k})).$

Let $\rho_{1}=c_{1}\max\left\\{r_{1},r_{2}\right\\}$. By using the fact that
$\sum_{j=1}^{\infty}s^{j}=\frac{1}{1-s}$, the result (A.18) can be reduced to

$\|\bm{x}^{\star}-\bm{x}^{p+1}\|_{2}\leq\rho_{1}^{p+1}\|\bm{x}^{\star}-\bm{x}^{0}\|_{2}+\frac{c_{2}}{1-\rho_{1}}\left\lVert\bm{n}\right\rVert_{2}.$

If $m$ is large enough, $\rho_{1}^{p}$ has to be less than $1$. We will
discuss the conditions when $\rho_{1}^{p}\leq 1$ in Remark 1.

##  Appendix B Proof of Theorem 2

Since ROTP and ROT share the same steps from $3$ to $5$, so we can use Theorem
1 to bound $\|\bm{x}^{\star}-\bm{v}\|_{2}$ as follows

$\|\bm{x}^{\star}-\bm{v}\|_{2}\leq\rho_{1}\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}+c_{2}\left\lVert\bm{n}\right\rVert_{2}.$
(A.19)

Next, we will relate $\|\bm{x}^{\star}-\bm{x}^{p+1}\|_{2}$ with
$\|\bm{x}^{\star}-\bm{v}\|_{2}$. Due to $\bm{x}^{p+1}$ is the solution of the
problem

$\bm{x}^{p+1}=\mathrm{argmin}_{\bm{x}}\big{\\{}\|\bm{y}-\bm{A}\bm{x}\|^{2}_{2},~{}\mbox{supp}(\bm{x})\subseteq\mathbb{S}^{p+1}\big{\\}},$

then we have
$\left[\bm{A}^{T}(\bm{y}-\bm{A}\bm{x}^{p+1})\right]_{\mathbb{S}^{p+1}}=0$.
Together with $\bm{y}=\bm{A}\bm{x}^{\star}+\bm{n}$, we have

$\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p+1})\right]_{\mathbb{S}^{p+1}}=\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}+\eta\left(\bm{A}^{T}\bm{n}\right)_{\mathbb{S}^{p+1}}.$
(A.20)

By using the triangle inequality, we obtain

$\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}\leq\left\lVert\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p+1})\right]_{\mathbb{S}^{p+1}}\right\rVert_{2}+\eta\left\lVert\left(\bm{A}^{T}\bm{n}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}.$
(A.21)

Since the cardinality of $\mathbb{S}^{p+1}$ is $k$ and
$(\bm{x}^{\star}-\bm{x}^{p+1})$ is a $2k$-sparse vector, using Lemma 2 yields

$\left\lVert\left[(\bm{I}-\eta\bm{A}^{T}\bm{A})(\bm{x}^{\star}-\bm{x}^{p+1})\right]_{\mathbb{S}^{p+1}}\right\rVert_{2}\leq\max\\{r_{1},r_{2}\\}\left\lVert(\bm{x}^{\star}-\bm{x}^{p+1})\right\rVert_{2},$
(A.22)

and

$\left\lVert\left(\bm{A}^{T}\bm{n}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}\leq(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}.$
(A.23)

So we get

$\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}\leq\max\\{r_{1},r_{2}\\}\left\lVert(\bm{x}^{\star}-\bm{x}^{p+1})\right\rVert_{2}+\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}.$
(A.24)

Due to the fact that $(\bm{x}^{p+1})_{\overline{\mathbb{S}^{p+1}}}=0$ and
$\bm{v}_{\overline{\mathbb{S}^{p+1}}}=0$, we have

$\displaystyle\left\lVert\bm{x}^{\star}-\bm{x}^{p+1}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}^{2}+\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}^{2}$
$\displaystyle=\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}^{2}+\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}^{2}$
$\displaystyle\leq\left(\max\\{r_{1},r_{2}\\}\right)^{2}\left\lVert(\bm{x}^{\star}-\bm{x}^{p+1})\right\rVert_{2}^{2}+\eta^{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}\left\lVert\bm{n}\right\rVert_{2}^{2}$
$\displaystyle\quad+2\eta\max\\{r_{1},r_{2}\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert(\bm{x}^{\star}-\bm{x}^{p+1})\right\rVert_{2}\left\lVert\bm{n}\right\rVert_{2}+\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}^{2},$
(A.25)

which is equivalent to

$\left[1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}\right]\left\lVert\bm{x}^{\star}-\bm{x}^{p+1}\right\rVert_{2}^{2}\\\
\leq\eta^{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}\left\lVert\bm{n}\right\rVert_{2}^{2}+2\eta\max\\{r_{1},r_{2}\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert(\bm{x}^{\star}-\bm{x}^{p+1})\right\rVert_{2}\left\lVert\bm{n}\right\rVert_{2}+\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}^{2}.$
(A.26)

By using the formula of roots of a quadric equation, we can give the upper
bound of
$\left\lVert\left(\bm{x}^{\star}-\bm{x}^{p+1}\right)_{\mathbb{S}^{p+1}}\right\rVert_{2}$

$\displaystyle\left\lVert\bm{x}^{\star}-\bm{x}^{p+1}\right\rVert_{2}$
$\displaystyle\leq\frac{2\eta\max\\{r_{1},r_{2}\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}+\sqrt{4\eta^{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))^{2}\left\lVert\bm{n}\right\rVert_{2}^{2}+4\left[1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}\right]\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}^{2}}}{2\left[1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}\right]}$
$\displaystyle\leq\frac{2\eta\max\\{r_{1},r_{2}\\}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}+2\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}+2\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}}{2\left[1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}\right]}$
$\displaystyle=\frac{\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}}{\left[1-\left(\max\\{r_{1},r_{2}\\}\right)\right]}+\frac{\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}}$
$\displaystyle\leq\frac{\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}}{\left[1-\left(\max\\{r_{1},r_{2}\\}\right)\right]}+\frac{\left\lVert\bm{x}-\bm{v}\right\rVert_{2}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}},$
(A.27)

where the second inequality uses that $a^{2}+b^{2}\leq(a+b)^{2}$ for any
$a,b\geq 0$ and the last inequality follows from that
$\left\lVert\left(\bm{x}-\bm{v}\right)_{\overline{\mathbb{S}^{p+1}}}\right\rVert_{2}\leq\left\lVert\bm{x}-\bm{v}\right\rVert_{2}$.

Together with (A.19), we complete the proof

$\displaystyle\left\lVert\bm{x}^{\star}-\bm{x}^{p+1}\right\rVert_{2}$
$\displaystyle\leq\frac{\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))\left\lVert\bm{n}\right\rVert_{2}}{\left[1-\left(\max\\{r_{1},r_{2}\\}\right)\right]}+\frac{\rho_{1}\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}+c_{2}\left\lVert\bm{n}\right\rVert_{2}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}},$
(A.28)
$\displaystyle\leq\rho_{2}\|\bm{x}^{\star}-\bm{x}^{p}\|_{2}+c_{3}\left\lVert\bm{n}\right\rVert_{2}$
(A.29)

where

$\displaystyle\rho_{2}=$
$\displaystyle\frac{\rho_{1}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}},$
(A.30) $\displaystyle c_{3}=$
$\displaystyle\frac{c_{2}}{\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}}+\frac{\eta(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{k}))}{\left[1-\left(\max\\{r_{1},r_{2}\\}\right)\right]}.$
(A.31)

Let $\rho_{2}=\rho_{1}/\sqrt{1-\left(\max\\{r_{1},r_{2}\\}\right)^{2}}$.
Similar as the proof of Theorem 1, we obtain the desired results (13). The
conditions when $\rho_{2}<1$ are discussed in Remark 1.

##  Appendix C Proof of Lemmas

In this section, we will provide the proof for the lemmas.

###  C.1 Proof of Lemma 2

Proof of part a): Let

$\bm{\mu}=\frac{[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}}}{\left\lVert[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}}\right\rVert_{2}}\in\mathbb{D}_{l}$
(A.32)

and

$\bm{\nu}=\frac{\bm{v}}{\left\lVert\bm{v}\right\rVert_{2}}\in\mathbb{D}_{k}.$
(A.33)

So we have

$\displaystyle\left\lVert[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}}\right\rVert_{2}$
$\displaystyle=\left\langle[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}},\bm{\mu}\right\rangle$
$\displaystyle=\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v},\bm{\mu}\right\rangle$
$\displaystyle=\left\lVert\bm{v}\right\rVert_{2}\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle.$
(A.34)

As for
$\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle$, we
have

$\displaystyle\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle$
$\displaystyle=\left\langle\bm{\nu},\bm{\mu}\right\rangle-\eta\left\langle\bm{A}\bm{\nu},\bm{A}\bm{\mu}\right\rangle$
$\displaystyle=\frac{1}{4}\left(\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\eta\left\lVert\bm{A}(\bm{\nu}+\bm{\mu})\right\rVert_{2}^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\eta\left\lVert\bm{A}(\bm{\nu}-\bm{\mu})\right\rVert_{2}^{2}\right).$
(A.35)

Notice that $\mathbb{D}_{l}=-\mathbb{D}_{l}$, so we have

$\displaystyle\bm{\nu}+\bm{\mu}\in\mathbb{D}_{k}+\mathbb{D}_{l},~{}\bm{\nu}-\bm{\mu}\in\mathbb{D}_{k}-\mathbb{D}_{l}=\mathbb{D}_{k}+\mathbb{D}_{l}.$
(A.36)

Using Fact 1 with $\mathbb{D}=\mathbb{D}_{k}+\mathbb{D}_{l}$,
$t=\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})$ and
$\mbox{rad}(\mathbb{D}_{k}+\mathbb{D}_{l})\leq 2$, we obtain

$\left\lVert\bm{A}(\bm{\nu}+\bm{\mu})\right\rVert_{2}^{2}\geq\left(\max\\{\sqrt{m}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}-3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l}),0\\}\right)^{2}$
(A.37)

and

$\left\lVert\bm{A}(\bm{\nu}-\bm{\mu})\right\rVert_{2}^{2}\leq\left[\sqrt{m}\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}+3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\right]^{2}$
(A.38)

with probability at least
$1-2\exp(-\gamma^{2}(\mathbb{D}_{k}+\mathbb{D}_{l}))$ respectively.

Next, we separate the problems into two cases.

Case I: If
$\sqrt{m}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}-3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\geq
0$, we have

$\displaystyle~{}~{}~{}\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle=\left\langle\bm{\nu},\bm{\mu}\right\rangle-\eta\left\langle\bm{A}\bm{\nu},\bm{A}\bm{\mu}\right\rangle$
$\displaystyle=\frac{1}{4}\left[\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\eta\left\lVert\bm{A}(\bm{\nu}+\bm{\mu})\right\rVert_{2}^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\eta\left\lVert\bm{A}(\bm{\nu}-\bm{\mu})\right\rVert_{2}^{2}\right)$
$\displaystyle\leq\frac{1}{4}\left[\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\eta\left(\sqrt{m}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}-3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\right)^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\eta\left(\sqrt{m}\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\right)^{2}\right]$
$\displaystyle=\frac{1}{4}(1-\eta
m)(\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2})+\frac{3}{2}\eta\sqrt{m}CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\left(\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}+\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}\right)$
$\displaystyle=(1-\eta
m)\left\langle\bm{\nu},\bm{\mu}\right\rangle+\frac{3}{2}\eta\sqrt{m}CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\left(\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}+\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}\right)$
$\displaystyle\leq 1-\eta
m+6\eta\sqrt{m}CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})$
$\displaystyle=1-\eta
m\cdot\frac{\sqrt{m}-6CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}},$
(A.39)

where the last inequality uses
$\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}\leq 2$ and
$\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}\leq 2$.

Case II: If
$\sqrt{m}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}-3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})<0$,
we have

$\displaystyle~{}~{}~{}\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle=\left\langle\bm{\nu},\bm{\mu}\right\rangle-\eta\left\langle\bm{A}\bm{\nu},\bm{A}\bm{\mu}\right\rangle$
$\displaystyle=\frac{1}{4}\left[\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\eta\left\lVert\bm{A}(\bm{\nu}+\bm{\mu})\right\rVert_{2}^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\eta\left\lVert\bm{A}(\bm{\nu}-\bm{\mu})\right\rVert_{2}^{2}\right)$
$\displaystyle\leq\frac{1}{4}\left[\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\eta\left(\sqrt{m}\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}+3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})\right)^{2}\right]$
$\displaystyle=\frac{1}{4}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}-\frac{1}{4}(1-\eta
m)\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}^{2}+\frac{1}{4}\eta
3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})(3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})+2\sqrt{m}\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2})$
$\displaystyle\leq\frac{1}{4}\left\lVert\bm{\nu}+\bm{\mu}\right\rVert_{2}^{2}+\frac{3}{4}\eta
CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})(3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})+2\sqrt{m}\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2})$
$\displaystyle\leq\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}\left[\frac{1}{4}\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}+\frac{1}{4}\eta
m\left(\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}+2\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}\right)\right]$
$\displaystyle\leq\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{2\sqrt{m}}+1\right),$
(A.40)

where the second inequality we uses $\eta m\leq 1$, and the last inequality
uses $\eta m\leq 1$, $\left\lVert\bm{\nu}-\bm{\mu}\right\rVert_{2}\leq 2$ and
$8CK^{2}\gamma(\mathbb{D}_{k})\leq\sqrt{m}$.

Therefore, we obtain

$\displaystyle\left\lVert[(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{v}]_{\mathbb{L}}\right\rVert_{2}$
$\displaystyle=\left\lVert\bm{v}\right\rVert_{2}\left\langle(\bm{I}-\eta\bm{A}^{T}\bm{A})\bm{\nu},\bm{\mu}\right\rangle\leq\max\left\\{s_{1},s_{2}\right\\}\cdot\left\lVert\bm{v}\right\rVert_{2},$
(A.41)

where

$\displaystyle s_{1}$ $\displaystyle=1-\eta
m\cdot\frac{\sqrt{m}-6CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}},$
(A.42) $\displaystyle s_{2}$
$\displaystyle=\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{\sqrt{m}}\left(\frac{3CK^{2}\gamma(\mathbb{D}_{k}+\mathbb{D}_{l})}{2\sqrt{m}}+1\right).$
(A.43)

Proof of part b): Let

$\bm{z}=\frac{[\bm{A}^{T}\bm{x}]_{\mathbb{L}}}{\left\lVert[\bm{A}^{T}\bm{x}]_{\mathbb{L}}\right\rVert_{2}}\in\mathbb{D}_{l},$
(A.44)

then we have

$\displaystyle\left\lVert[\bm{A}^{T}\bm{x}]_{\mathbb{L}}\right\rVert_{2}$
$\displaystyle=\left\langle[\bm{A}^{T}\bm{x}]_{\mathbb{L}},\bm{z}\right\rangle$
$\displaystyle=\left\langle\bm{A}^{T}\bm{x},\bm{z}\right\rangle$
$\displaystyle=\left\langle\bm{x},\bm{A}\bm{z}\right\rangle$
$\displaystyle\leq\left\lVert\bm{x}\right\rVert_{2}\left\lVert\bm{A}\bm{z}\right\rVert_{2}$
$\displaystyle\leq\left\lVert\bm{x}\right\rVert_{2}(\sqrt{m}+2CK^{2}\gamma(\mathbb{D}_{l})).$
(A.45)

with probability at least $1-2\exp(-\gamma^{2}(\mathbb{D}_{l}))$, where the
first inequality uses Holder’s inequality and the last inequality uses Lemma
1.

###  C.2 Proof of Lemma 3

Proof of part a): For any $\bm{x}\in\mathbb{D}_{2k}$, there exists two vectors
$\bm{y},\bm{z}\in\mathbb{D}_{k}$ such that
$\bm{x}=(\bm{y}+\bm{z})/\left\lVert\bm{y}+\bm{z}\right\rVert_{2}$ and
$y_{i}z_{i}=0,i=1,\ldots,n$, which means the locations of non-zeros for
$\bm{y}$ and $\bm{z}$ are totally different. Then we have

$\displaystyle\gamma(\mathbb{D}_{2k})$
$\displaystyle=\textbf{E}\sup_{\bm{x}\in\mathbb{D}_{2k}}|\left\langle\bm{g},\bm{x}\right\rangle|$
$\displaystyle=\textbf{E}\sup_{(\bm{y}+\bm{z})/\left\lVert\bm{y}+\bm{z}\right\rVert_{2}\in\mathbb{D}_{2k}}\left|\left\langle\bm{g},\frac{\bm{y}+\bm{z}}{\left\lVert\bm{y}+\bm{z}\right\rVert_{2}}\right\rangle\right|$
$\displaystyle=\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k},\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\frac{\bm{y}+\bm{z}}{\left\lVert\bm{y}+\bm{z}\right\rVert_{2}}\right\rangle\right|$
$\displaystyle\leq\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\frac{\bm{y}}{\left\lVert\bm{y}+\bm{z}\right\rVert_{2}}\right\rangle\right|+\textbf{E}\sup_{\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\frac{\bm{z}}{\left\lVert\bm{y}+\bm{z}\right\rVert_{2}}\right\rangle\right|$
$\displaystyle\leq\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\frac{\bm{y}}{\left\lVert\bm{y}\right\rVert_{2}}\right\rangle\right|+\textbf{E}\sup_{\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\frac{\bm{z}}{\left\lVert\bm{y}\right\rVert_{2}}\right\rangle\right|$
$\displaystyle=\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\bm{y}\right\rangle\right|+\textbf{E}\sup_{\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\bm{z}\right\rangle\right|$
$\displaystyle=2\gamma(\mathbb{D}_{k}),$ (A.46)

where the first inequality uses the triangle inequality and the second
inequality applies the fact that the locations of non-zeros for $\bm{y}$ and
$\bm{z}$ are totally different.

Proof of part b): For any $\bm{x}\in\mathbb{D}_{k}+\mathbb{D}_{k}$, there
exists $\bm{y},\bm{z}\in\mathbb{D}_{k}$ such that $\bm{x}=\bm{y}+\bm{z}$. So
we have

$\displaystyle\gamma(\mathbb{D}_{k}+\mathbb{D}_{k})$
$\displaystyle=\textbf{E}\sup_{\bm{x}\in\mathbb{D}_{k}+\mathbb{D}_{k}}|\left\langle\bm{g},\bm{x}\right\rangle|$
$\displaystyle=\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k},\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},{\bm{y}+\bm{z}}\right\rangle\right|$
$\displaystyle\leq\textbf{E}\sup_{\bm{y}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},{\bm{y}}\right\rangle\right|+\textbf{E}\sup_{\bm{z}\in\mathbb{D}_{k}}\left|\left\langle\bm{g},\bm{z}\right\rangle\right|$
$\displaystyle=2\gamma(\mathbb{D}_{k}).$ (A.47)

Proof of part c): By the definition of $\mathbb{D}_{k}$, it is clear that
$\mathbb{D}_{k}\subseteq\mathbb{D}_{l}$ when $k\leq l$. Therefore, we have
$\gamma(\mathbb{D}_{k})\leq\gamma(\mathbb{D}_{l})$.