### C.4.1 Reminders on Properties of RIP Matrices

We first remind the definition of Restricted Isometry Constant in (4) and a few properties of RIP matrices.

**Fact 1:** For any $k, k' \in [1, n]$, such that $k \le k'$, we have

$$ \delta_k \le \delta_{k'}. \qquad (41) $$

**Fact 2:** For any $R, S \subseteq [1, n]$, such that $R \cap S = \emptyset$ and $A$ satisfies the $(|R| + |S|)$-RIP. We remind Lemma 1 of [16] (see also [12]): For any $x \in \mathbb{R}^{|S|}$

$$ \|A_R^T A_S x\|_2 \le \delta_{|R|+|S|} \|x\|_2. \qquad (42) $$

For completeness, we prove this inequality below. Let $A, R, S$ and $x$ be as above, we have,

$$ \|A_R^T A_S \frac{x}{\|x\|_2}\|_2 = \max_{x': \|x'\|_2=1} \langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle. $$

Using $\langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle = \langle A_R x', A_S \frac{x}{\|x\|_2} \rangle \le \frac{1}{2} \|A_R x' + A_S \frac{x}{\|x\|_2}\|_2^2$, the fact that $R \cap S = \emptyset$, and that $A$ satisfies the $(|R| + |S|)$-RIP defined in (4), we obtain for all $x' \in \mathbb{R}^{|R|}$ such that $\|x'\|_2 = 1$

$$ \langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle \le \frac{1}{2}(1 + \delta_{|R|+|S|}) \left( \|x'\|_2^2 + \|\frac{x}{\|x\|_2}\|_2^2 \right) = (1 + \delta_{|R|+|S|}). $$

This concludes the proof of (42).

**Fact 3:** Let us assume that $A$ satisfies the $|S|$-RIP. Taking inspiration of Proposition 3.1 of [38], for any singular value $\lambda \in \mathbb{R}$ of $A_S$, and the corresponding right singular vector $x_\lambda \in \mathbb{R}^{|S|}$, we have $\|A_S x_\lambda\|_2 = \lambda$. Using (4), $1 - \delta_{|S|} \le \lambda^2 \le 1 + \delta_{|S|}$. All singular values of $A_S$ and $A_S^T$ lie between $\sqrt{1 - \delta_{|S|}}$ and $\sqrt{1 + \delta_{|S|}}$.

As a consequence, for any $u \in \mathbb{R}^m$, we have

$$ \|A_S^T u\|_2 \le \sqrt{1 + \delta_{|S|}} \|u\|_2. \qquad (43) $$

**Fact 4:** Let us assume that $A$ satisfies the $|S|$-RIP. Using the same reasoning, we find that the eigenvalues of $A_S^T A_S$ lie between $1 - \delta_{|S|}$ and $1 + \delta_{|S|}$. This implies that $A_S^T A_S$ is non-singular and that the eigenvalues of $(A_S^T A_S)^{-1}$ lie between $\frac{1}{1 + \delta_{|S|}}$ and $\frac{1}{1 - \delta_{|S|}}$. Then $A_S$ is full column rank and for any $x \in \mathbb{R}^{|S|}$

$$ \|(A_S^T A_S)^{-1} x\|_2 \le \frac{1}{1 - \delta_{|S|}} \|x\|_2. \qquad (44) $$

**Fact 5:** Let us assume that $A$ satisfies the $|S|$-RIP. By using one last time the same reasoning, we find that the eigenvalues of $A_S^T A_S - I_{|S|}$ lie between $-\delta_{|S|}$ and $\delta_{|S|}$. Finally, for any $x \in \mathbb{R}^{|S|}$,

$$ \|(A_S^T A_S - I_{|S|})x\|_2 \le \delta_{|S|} \|x\|_2. \qquad (45) $$

### C.4.2 Preliminaries

In this section, the facts from Appendix C.4.1 are used to bound from above the error $\|(x^t - x^*)_{|S^t|}\|_2$, where $(.)_{|S^t|$}$ is the restriction of the vector to the support $S^t$ and $S^t$ is defined in Algorithm 1, line 6. This bound will lead to an upper bound on $\|b^t\|_2$. Throughout the section, we assume $A$ satisfies the $(2k + 1)$-RIP. Figure 5 might help visualize the different sets of indices considered in the proof.

**Lemma C.10.** If $A$ satisfies the $(2k + 1)$-RIP, for any $t \in \mathbb{N}$,

$$ \|(x^t - x^*)_{|S^t|} \|_2 \le \frac{\delta_{2k}}{1 - \delta_k} \frac{\|u^t\|_2}{\eta} + \frac{\sqrt{1 + \delta_k}}{1 - \delta_k} \|e\|_2. $$
### C.4.1 Reminders on Properties of RIP Matrices

We first remind the definition of Restricted Isometry Constant in (4) and a few properties of RIP matrices.

**Fact 1:** For any $k, k' \in [1, n]$, such that $k \le k'$, we have

$$ \delta_k \le \delta_{k'}. \quad (41) $$

**Fact 2:** For any $R, S \subseteq [1, n]$, such that $R \cap S = \emptyset$ and $A$ satisfies the $(|R| + |S|)$-RIP. We remind Lemma 1 of [16] (see also [12]): For any $x \in \mathbb{R}^{|S|}$

$$ \|A_R^T A_S x\|_2 \le \delta_{|R|+|S|} \|x\|_2. \quad (42) $$

For completeness, we prove this inequality below. Let $A, R, S$ and $x$ be as above, we have,

$$ \|A_R^T A_S \frac{x}{\|x\|_2}\|_2 = \max_{x': \|x'\|_2=1} \langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle. $$

Using $\langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle = \langle A_R x', A_S \frac{x}{\|x\|_2} \rangle \le \frac{1}{2} \|A_R x' + A_S \frac{x}{\|x\|_2}\|_2^2$, the fact that $R \cap S = \emptyset$, and that $A$ satisfies the $(|R| + |S|)$-RIP defined in (4), we obtain for all $x' \in \mathbb{R}^{|R|}$ such that $\|x'\|_2 = 1$

$$ \langle x', A_R^T A_S \frac{x}{\|x\|_2} \rangle \le \frac{1}{2}(1 + \delta_{|R|+|S|}) \left( \|x'\|_2^2 + \|\frac{x}{\|x\|_2}\|_2^2 \right) = (1 + \delta_{|R|+|S|}). $$

This concludes the proof of (42).

**Fact 3:** Let us assume that $A$ satisfies the $|S|$-RIP. Taking inspiration of Proposition 3.1 of [38], for any singular value $\lambda \in \mathbb{R}$ of $A_S$, and the corresponding right singular vector $x_\lambda \in \mathbb{R}^{|S|}$, we have $\|A_S x_\lambda\|_2 = \lambda$. Using (4), $1 - \delta_{|S|} \le \lambda^2 \le 1 + \delta_{|S|}$. All singular values of $A_S$ and $A_S^T$ lie between $\sqrt{1 - \delta_{|S|}}$ and $\sqrt{1 + \delta_{|S|}}$.

As a consequence, for any $u \in \mathbb{R}^m$, we have

$$ \|A_S^T u\|_2 \le \sqrt{1 + \delta_{|S|}} \|u\|_2. \quad (43) $$

**Fact 4:** Let us assume that $A$ satisfies the $|S|$-RIP. Using the same reasoning, we find that the eigenvalues of $A_S^T A_S$ lie between $1 - \delta_{|S|}$ and $1 + \delta_{|S|}$. This implies that $A_S^T A_S$ is non-singular and that the eigenvalues of $(A_S^T A_S)^{-1}$ lie between $\frac{1}{1 + \delta_{|S|}}$ and $\frac{1}{1 - \delta_{|S|}}$. Then $A_S$ is full column rank and for any $x \in \mathbb{R}^{|S|}$

$$ \|(A_S^T A_S)^{-1} x\|_2 \le \frac{1}{1 - \delta_{|S|}} \|x\|_2. \quad (44) $$

**Fact 5:** Let us assume that $A$ satisfies the $|S|$-RIP. By using one last time the same reasoning, we find that the eigenvalues of $A_S^T A_S - I_{|S|}$ lie between $-\delta_{|S|}$ and $\delta_{|S|}$. Finally, for any $x \in \mathbb{R}^{|S|}$,

$$ \|(A_S^T A_S - I_{|S|})x\|_2 \le \delta_{|S|} \|x\|_2. \quad (45) $$

### C.4.2 Preliminaries

In this section, the facts from Appendix C.4.1 are used to bound from above the error $\|(x^t - x^*)_{|S^t|}\|_2$, where $(.)_{|S^t|}$ is the restriction of the vector to the support $S^t$ and $S^t$ is defined in Algorithm 1, line 6. This bound will lead to an upper bound on $\|b^t\|_2$. Throughout the section, we assume $A$ satisfies the $(2k+1)$-RIP. Figure 5 might help visualize the different sets of indices considered in the proof.

**Lemma C.10.** If $A$ satisfies the $(2k+1)$-RIP, for any $t \in \mathbb{N}$,

$$ \|(x^t - x^*)_{|S^t|}\|_2 \le \frac{\delta_{2k}}{1 - \delta_k} \frac{\|u^t\|_2}{\eta} + \frac{\sqrt{1 + \delta_k}}{1 - \delta_k} \|e\|_2. $$
Proof. For any $t \in \mathbb{N}$, using the definition of $x^t$ in Algorithm 1 and (15), we find

$$
\begin{align}
x_{|S^t}^t &= A_{S^t}^\dagger y \\
&= A_{S^t}^\dagger (A_{S^*} x_{|S^*}^* + e) \\
&= A_{S^t}^\dagger A_{S^* \cap S^t} x_{|S^* \cap S^t}^* - \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t + A_{S^t}^\dagger e. \tag{46}
\end{align}
$$

We also have

$$
\begin{align}
A_{S^t}^\dagger A_{S^* \cap S^t} x_{|S^* \cap S^t}^* &= A_{S^t}^\dagger [A_{S^* \cap S^t} \quad A_{S^t \setminus S^*}] \begin{bmatrix} x_{|S^* \cap S^t}^* \\ 0 \end{bmatrix} \nonumber \\
&= A_{S^t}^\dagger A_{S^t} x_{|S^t}^* \tag{47}
\end{align}
$$

Since $\delta_{2k+1} < 1$, (41) implies that $\delta_k \le \delta_{2k+1} < 1$ and the smallest singular value of $A_{S^t}$ is larger than $\sqrt{1 - \delta_k} \ge \sqrt{1 - \delta_{2k+1}} > 0$. Therefore $A_{S^t}$ is full column rank and

$$
A_{S^t}^{\dagger} = (A_{S^t}^{T} A_{S^t})^{-1} A_{S^t}^{T}. \quad (48)
$$

Combining (46), (47) and (48), we obtain

$$
x_{|S^t}^t = x_{|S^t}^* - \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t + A_{S^t}^\dagger e.
$$

Using (48), we find

$$
\begin{align*}
\|(x^t - x^*)_{|S^t}\|_2 &= \left\| \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t - A_{S^t}^\dagger e \right\|_2 \\
&\le \frac{1}{\eta} \|(A_{S^t}^T A_{S^t})^{-1} A_{S^t}^T A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t\|_2 + \|(A_{S^t}^T A_{S^t})^{-1} A_{S^t}^T e\|_2.
\end{align*}
$$

Finally, using (44), then (42), (41), (43) and (15), we finish the proof

$$
\begin{align*}
\|(x^t - x^*)_{|S^t}\|_2 &\le \frac{1}{1 - \delta_k} \left( \frac{1}{\eta} \|A_{S^t}^T A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t\|_2 + \|A_{S^t}^T e\|_2 \right) \\
&\le \frac{1}{1 - \delta_k} \left( \frac{\delta_{2k}}{\eta} \|u_{|S^* \cap \overline{S^t}}^t\|_2 + \sqrt{1 + \delta_k} \|e\|_2 \right) \\
&= \frac{\delta_{2k}}{1 - \delta_k} \frac{\|u^t\|_2}{\eta} + \frac{\sqrt{1 + \delta_k}}{1 - \delta_k} \|e\|_2.
\end{align*}
$$

□

We have the following upper bound on $\|b^t\|_2$. This bound is given in Theorem C.9.

**Lemma C.11 (Bound of $b^t$ - RIP case).** If A satisfies the (2k + 1)-RIP, for any $t \in \mathbb{N}$,

$$
\| \frac{u^t}{\eta} - A^T (Ax^t - y) \|_{\infty} = \frac{1}{\eta} \|b^t\|_{\infty} \le \alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2,
$$

where $\alpha_k^{\text{RIP}}$ and $\gamma_k^{\text{RIP}}$ are defined in (5).

Proof. Let $t \in \mathbb{N}$ and $i \in [1, n]$, reminding the definition of $b^t$ in (19), we have

$$
\begin{align}
|b_i^t| &= |u_i^t - \eta(A_i)^T (Ax^t - y)| \nonumber \\
&= |u_i^t - \eta(A_i)^T A(x^t - x^*) + \eta(A_i)^T e| \tag{49} \\
&= |u_i^t - \eta(A_i)^T A_{S^* \cup S^t} (x^t - x^*)_{|S^* \cup S^t} + \eta(A_i)^T e|. \nonumber
\end{align}
$$

We distinguish three cases: $i \in S^t$, $i \in \overline{S^*} \cap \overline{S^t}$ and $i \in S^* \cap \overline{S^t}$. We prove that in the three cases

$$
|b_i^t| \le \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2). \quad (50)
$$

1st case: If $i \in S^t$, using (22), $b_i^t = 0$ and (50) holds.
Proof. For any $t \in \mathbb{N}$, using the definition of $x^t$ in Algorithm 1 and (15), we find

$$
\begin{align}
x_{|S^t}^t &= A_{S^t}^\dagger y \nonumber \\
&= A_{S^t}^\dagger (A_{S^*} x_{|S^*}^* + e) \nonumber \\
&= A_{S^t}^\dagger A_{S^* \cap S^t} x_{|S^* \cap S^t}^* - \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t + A_{S^t}^\dagger e. \tag{46}
\end{align}
$$

We also have

$$
\begin{align}
A_{S^t}^\dagger A_{S^* \cap S^t} x_{|S^* \cap S^t}^* &= A_{S^t}^\dagger [A_{S^* \cap S^t} \quad A_{S^t \setminus S^*}] \begin{bmatrix} x_{|S^* \cap S^t}^* \\ 0 \end{bmatrix} \nonumber \\
&= A_{S^t}^\dagger A_{S^t} x_{|S^t}^* \tag{47}
\end{align}
$$

Since $\delta_{2k+1} < 1$, (41) implies that $\delta_k \le \delta_{2k+1} < 1$ and the smallest singular value of $A_{S^t}$ is larger than $\sqrt{1 - \delta_k} \ge \sqrt{1 - \delta_{2k+1}} > 0$. Therefore $A_{S^t}$ is full column rank and

$$
A_{S^t}^{\dagger} = (A_{S^t}^{T} A_{S^t})^{-1} A_{S^t}^{T}. \quad (48)
$$

Combining (46), (47) and (48), we obtain

$$
x_{|S^t}^t = x_{|S^t}^* - \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t + A_{S^t}^\dagger e.
$$

Using (48), we find

$$
\begin{align*}
\|(x^t - x^*)_{|S^t}\|_2 &= \left\| \frac{1}{\eta} A_{S^t}^\dagger A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t - A_{S^t}^\dagger e \right\|_2 \\
&\le \frac{1}{\eta} \|(A_{S^t}^T A_{S^t})^{-1} A_{S^t}^T A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t\|_2 + \|(A_{S^t}^T A_{S^t})^{-1} A_{S^t}^T e\|_2.
\end{align*}
$$

Finally, using (44), then (42), (41), (43) and (15), we finish the proof

$$
\begin{align*}
\|(x^t - x^*)_{|S^t}\|_2 &\le \frac{1}{1 - \delta_k} \left( \frac{1}{\eta} \|A_{S^t}^T A_{S^* \cap \overline{S^t}} u_{|S^* \cap \overline{S^t}}^t\|_2 + \|A_{S^t}^T e\|_2 \right) \\
&\le \frac{1}{1 - \delta_k} \left( \frac{\delta_{2k}}{\eta} \|u_{|S^* \cap \overline{S^t}}^t\|_2 + \sqrt{1 + \delta_k} \|e\|_2 \right) \\
&= \frac{\delta_{2k}}{1 - \delta_k} \frac{\|u^t\|_2}{\eta} + \frac{\sqrt{1 + \delta_k}}{1 - \delta_k} \|e\|_2.
\end{align*}
$$

□

We have the following upper bound on $\|b^t\|_2$. This bound is given in Theorem C.9.

**Lemma C.11 (Bound of $b^t$ - RIP case).** If A satisfies the (2k + 1)-RIP, for any $t \in \mathbb{N}$,

$$
\| \frac{u^t}{\eta} - A^T (Ax^t - y) \|_{\infty} = \frac{1}{\eta} \|b^t\|_{\infty} \le \alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2,
$$

where $\alpha_k^{\text{RIP}}$ and $\gamma_k^{\text{RIP}}$ are defined in (5).

Proof. Let $t \in \mathbb{N}$ and $i \in [1, n]$, reminding the definition of $b^t$ in (19), we have

$$
\begin{align}
|b_i^t| &= |u_i^t - \eta(A_i)^T (Ax^t - y)| \nonumber \\
&= |u_i^t - \eta(A_i)^T A(x^t - x^*) + \eta(A_i)^T e| \tag{49} \\
&= |u_i^t - \eta(A_i)^T A_{S^* \cup S^t} (x^t - x^*)_{|S^* \cup S^t} + \eta(A_i)^T e|. \nonumber
\end{align}
$$

We distinguish three cases: $i \in S^t$, $i \in \overline{S^*} \cap \overline{S^t}$ and $i \in S^* \cap \overline{S^t}$. We prove that in the three cases

$$
|b_i^t| \le \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2). \quad (50)
$$

1st case: If $i \in S^t$, using (22), $b_i^t = 0$ and (50) holds.
**2<sup>nd</sup> case:** If $i \in \overline{S^*} \cap \overline{S^t}$, using the definition of $u^t$ in (15), (42), (41) and the fact that $\|A_i\|_2 = 1$ we obtain

$$
\begin{aligned}
|b_i^t| &= |-\eta(A_i)^T A_{S^* \cup S^t} (x^t - x^*)|_{S^* \cup S^t} + \eta(A_i)^T e| \\
&\leq \eta (\|(A_i)^T A_{S^* \cup S^t} (x^t - x^*)\|_{S^* \cup S^t} + \|(A_i)^T e\|_2) \\
&\leq \eta (\delta_{2k+1} \|(x^t - x^*)\|_{S^* \cup S^t} + \|e\|_2) \\
&= \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2)
\end{aligned}
$$

**3<sup>rd</sup> case:** If $i \in S^* \cap \overline{S^t}$, reminding that $\{i\}$ is the complement of $\{i\} \subseteq [1, n]$, and since $(A_i)^T A_{\{i\}} = \|A_i\|_2 = 1$ and $x_i^t = 0$, (49) becomes

$$
\begin{aligned}
|b_i^t| &= |-\eta x_i^* - \eta(A_i)^T A(x^t - x^*) + \eta(A_i)^T e| \\
&= \eta|-x_i^* - (A_i)^T A_{\{i\}}(x^t - x^*)|_{\{i\}} - (A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&= \eta|-x_i^* - (x_i^t - x_i^*) - (A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&= \eta|-(A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&\leq \eta \left( |(A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + |(A_i)^T e| \right).
\end{aligned}
$$

Using (42), (41) and $\|A_i\|_2 = 1$, we obtain

$$
\begin{aligned}
|b_i^t| &\le \eta (\delta_{2k} \|x^t - x^*\|_2 + \|e\|_2) \\
&\le \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2).
\end{aligned}
$$

Regrouping the three cases, we conclude that for all $i \in [1, n]$, (50) holds. We now finish the proof.
Using (15) followed by Lemma C.10, we find

$$
\begin{aligned}
|b_i^t| &\le \eta \left( \delta_{2k+1} \left( \|(x^t - x^*)\|_{S^t} + \frac{\|u^t\|_2}{\eta} \right) + \|e\|_2 \right) \\
&\le \eta \left( \delta_{2k+1} \left( \frac{\delta_{2k}}{1-\delta_k} + 1 \right) \frac{\|u^t\|_2}{\eta} + \left( \delta_{2k+1} \frac{\sqrt{1+\delta_k}}{1-\delta_k} + 1 \right) \|e\|_2 \right) \\
&\le \eta (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2),
\end{aligned}
$$

where the last inequality holds because $\frac{\|u^t\|_2}{\eta} \le \|x^*\|_2$. $\square$

### C.4.3 End of the Proof of Theorem C.9

We now resume to the proof of Theorem C.9 and assume A satisfies the (2k + 1)-RIP and $x^*$ satisfies ($RC_{RIP}$). We remind the definitions of $T_{max}$ in (21) and $T_{RIP}$ in (6).

Using (20) and Lemma C.11, we have

$$ \varepsilon = \sup_{t \in \mathbb{N}} \|b^t\|_{\infty} \leq \eta (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2). \quad (51) $$

Combined with (RC<sub>RIP</sub>), that is $\gamma_k^{\text{RIP}} \|e\|_2 < \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{\text{RIP}} \|x^*\|_2$, this implies that
$$ \varepsilon < \frac{\eta}{2k} \min_{i \in S^*} |x_i^*|. $$

Therefore (RC) holds and Theorem C.4 implies that there exists $t_s \le T_{max}$ such that $S^* \subseteq S^{t_s}$, with

$$ T_{max} = \frac{2k \|\mathcal{X}^0\|_{\infty} + (k+1)\eta \min_{i \in S^*} |x_i^*|}{\eta \min_{i \in S^*} |x_i^*| - 2k\varepsilon}. $$

Using (51), we obtain

$$ T_{max} \le \frac{2k \|\mathcal{X}^0\|_{\infty} + (k+1)\eta \min_{i \in S^*} |x_i^*|}{\eta \min_{i \in S^*} |x_i^*| - 2k\varepsilon (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2)} = T_{RIP}. $$

We still need to prove that, when $\min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1-\delta_{2k}}}$ $\|e\|_2$, $t_{BEST}$ satisfies $S^* \subseteq S^{t_{BEST}}$, as well as the last upper-bound of Theorem C.9.
**2<sup>nd</sup> case:** If $i \in \overline{S^*} \cap \overline{S^t}$, using the definition of $u^t$ in (15), (42), (41) and the fact that $\|A_i\|_2 = 1$ we obtain

$$
\begin{aligned}
|b_i^t| &= |-\eta(A_i)^T A_{S^* \cup S^t} (x^t - x^*)|_{S^* \cup S^t} + \eta(A_i)^T e| \\
&\leq \eta (\|(A_i)^T A_{S^* \cup S^t} (x^t - x^*)\|_{S^* \cup S^t} + \|(A_i)^T e\|_2) \\
&\leq \eta (\delta_{2k+1} \|(x^t - x^*)\|_{S^* \cup S^t} + \|e\|_2) \\
&= \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2)
\end{aligned}
$$

**3<sup>rd</sup> case:** If $i \in S^* \cap \overline{S^t}$, reminding that $\{i\}$ is the complement of $\{i\} \subseteq [1, n]$, and since $(A_i)^T A_{\{i\}} = \|A_i\|_2 = 1$ and $x_i^t = 0$, (49) becomes

$$
\begin{aligned}
|b_i^t| &= |-\eta x_i^* - \eta(A_i)^T A(x^t - x^*) + \eta(A_i)^T e| \\
&= \eta|-x_i^* - (A_i)^T A_{\{i\}}(x^t - x^*)|_{\{i\}} - (A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&= \eta|-x_i^* - (x_i^t - x_i^*) - (A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&= \eta|-(A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + (A_i)^T e| \\
&\leq \eta \left( |(A_i)^T A_{\overline{\{i\}}}(x^t - x^*)|_{\overline{\{i\}}} + |(A_i)^T e| \right).
\end{aligned}
$$

Using (42), (41) and $\|A_i\|_2 = 1$, we obtain

$$
\begin{aligned}
|b_i^t| &\leq \eta (\delta_{2k} \|x^t - x^*\|_2 + \|e\|_2) \\
&\leq \eta (\delta_{2k+1} \|x^t - x^*\|_2 + \|e\|_2).
\end{aligned}
$$

Regrouping the three cases, we conclude that for all $i \in [1, n]$, (50) holds. We now finish the proof.
Using (15) followed by Lemma C.10, we find

$$
\begin{aligned}
|b_i^t| &\le \eta \left( \delta_{2k+1} \left( \|(x^t - x^*)\|_{S^t} + \frac{\|u^t\|_2}{\eta} \right) + \|e\|_2 \right) \\
&\le \eta \left( \delta_{2k+1} \left( \frac{\delta_{2k}}{1-\delta_k} + 1 \right) \frac{\|u^t\|_2}{\eta} + \left( \delta_{2k+1} \frac{\sqrt{1+\delta_k}}{1-\delta_k} + 1 \right) \|e\|_2 \right) \\
&\le \eta (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2),
\end{aligned}
$$

where the last inequality holds because $\frac{\|u^t\|_2}{\eta} \le \|x^*\|_2$. $\square$

### C.4.3 End of the Proof of Theorem C.9

We now resume to the proof of Theorem C.9 and assume A satisfies the (2k + 1)-RIP and $x^*$ satisfies ($RC_{RIP}$). We remind the definitions of $T_{max}$ in (21) and $T_{RIP}$ in (6).

Using (20) and Lemma C.11, we have

$$ \varepsilon = \sup_{t \in \mathbb{N}} \|b^t\|_{\infty} \leq \eta (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2). \quad (51) $$

Combined with (RC<sub>RIP</sub>), that is $\gamma_k^{\text{RIP}} \|e\|_2 < \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{\text{RIP}} \|x^*\|_2$, this implies that
$$ \varepsilon < \frac{\eta}{2k} \min_{i \in S^*} |x_i^*|. $$

Therefore (RC) holds and Theorem C.4 implies that there exists $t_s \le T_{max}$ such that $S^* \subseteq S^{t_s}$, with

$$ T_{max} = \frac{2k \|\mathcal{X}^0\|_{\infty} + (k+1)\eta \min_{i \in S^*} |x_i^*|}{\eta \min_{i \in S^*} |x_i^*| - 2k\varepsilon}. $$

Using (51), we obtain

$$ T_{max} \le \frac{2k \|\mathcal{X}^0\|_{\infty} + (k+1)\eta \min_{i \in S^*} |x_i^*|}{\eta \min_{i \in S^*} |x_i^*| - 2k\varepsilon (\alpha_k^{\text{RIP}} \|x^*\|_2 + \gamma_k^{\text{RIP}} \|e\|_2)} = T_{RIP}. $$

We still need to prove that, when $\min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1-\delta_{2k}}}$ $\|e\|_2$, $t_{BEST}$ satisfies $S^* \subseteq S^{t_{BEST}}$, as well as the last upper-bound of Theorem C.9.
Assume by contradiction that

$$ \min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1 - \delta_{2k}}} \|e\|_2 \quad (52) $$

holds but $S^* \not\subseteq S^{t_{BEST}}$. The construction of $t_{BEST}$, in line 11 of Algorithm 1, and the existence $t_s$ such that $S^* \subseteq S^{t_s}$ guarantee that

$$ \|Ax^{t_{BEST}} - y\| \le \|Ax^{t_s} - y\| \le \|Ax^* - y\| = \|e\|_2. $$

Therefore, using the left inequality in (4), we obtain

$$ \begin{aligned} \sqrt{1 - \delta_{2k}} \|x^{t_{BEST}} - x^*\|_2 &\le \|A(x^{t_{BEST}} - x^*)\|_2 \\ &\le \|Ax^{t_{BEST}} - y\|_2 + \|Ax^* - y\|_2 \\ &\le 2\|e\|_2. \end{aligned} $$

On the other hand, since we assumed $S^* \not\subseteq S^{t_{BEST}}$ we have

$$ \|x^{t_{BEST}} - x^*\|_2 \ge \min_{i \in S^*} |x_i^*|. $$

We conclude that $\min_{i \in S^*} |x_i^*| \le \frac{2}{\sqrt{1-\delta_{2k}}} \|e\|_2$ which contradicts (52).

As a conclusion, when $\min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1-\delta_{2k}}} \|e\|_2$, we have $S^* \subseteq S^{t_{BEST}}$.

In this case, since the support of $x^{t_{BEST}} - x^*$ is of size smaller than $k$, we can redo the above calculation and obtain

$$ \sqrt{1 - \delta_k} \|x^{t_{BEST}} - x^*\|_2 \le \|A(x^{t_{BEST}} - x^*)\|_2 \le 2\|e\|_2. $$

This leads to the last inequality of Theorem C.9 and concludes the proof.

## C.5 Proof of Corollary 4.2

We assume that $x^*$ satisfies ($RC_{SRIP}$) and that $\|e\|_2 = 0$. Let us first prove that $x^*$ satisfies ($RC_{RIP}$). Using ($RC_{SRIP}$) we have

$$ \begin{aligned} 0 < 1 - \Lambda &\le 1 - 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \\ &= \frac{2k}{\min_{i \in S^*} |x_i^*|} \left( \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{RIP} \|x^*\|_2 \right). \end{aligned} $$

As a consequence, since $2k > 0$ and $\min_{i \in S^*} |x_i^*| > 0$,

$$ 0 < \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{RIP} \|x^*\|_2. \quad (53) $$

We conclude that $x^*$ satisfies the ($RC_{RIP}$) for $A$.

Applying Theorem 4.1 and since $\|e\|_2 = 0$ and $X^0 = 0$, we know that there exists $t \le T_{RIP} = \frac{(k+1)}{1-2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}}$ such that $S^* \subseteq S^t$. It is not difficult to check that the function $f: \mathbb{R} \to \mathbb{R}$ defined for all $u \in \mathbb{R}$ by $f(u) = \frac{k+1}{1-u}$ is increasing on $[0, 1)$. By applying $f$ to

$$ 0 \le 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \le \Lambda < 1, $$

we obtain

$$ T_{RIP} = f \left( 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \right) \le f(\Lambda) = T_{SRIP}, $$

where $T_{SRIP}$ is defined in Corollary 4.2.

Therefore $t \le T_{SRIP}$ and we conclude that there exists $t \le T_{SRIP}$ such that $S^* \subseteq S^t$.

The last statement of Corollary 4.2 is a direct consequence of Theorem 4.1 and $x^*$ satisfies (7) with $\|e\| = 0$.

This concludes the proof of Corollary 4.2.
Assume by contradiction that

$$ \min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1 - \delta_{2k}}} \|e\|_2 \quad (52) $$

holds but $S^* \not\subseteq S^{t_{BEST}}$. The construction of $t_{BEST}$, in line 11 of Algorithm 1, and the existence $t_s$ such that $S^* \subseteq S^{t_s}$ guarantee that

$$ \|Ax^{t_{BEST}} - y\| \le \|Ax^{t_s} - y\| \le \|Ax^* - y\| = \|e\|_2. $$

Therefore, using the left inequality in (4), we obtain

$$ \begin{aligned} \sqrt{1 - \delta_{2k}} \|x^{t_{BEST}} - x^*\|_2 &\le \|A(x^{t_{BEST}} - x^*)\|_2 \\ &\le \|Ax^{t_{BEST}} - y\|_2 + \|Ax^* - y\|_2 \\ &\le 2\|e\|_2. \end{aligned} $$

On the other hand, since we assumed $S^* \not\subseteq S^{t_{BEST}}$ we have

$$ \|x^{t_{BEST}} - x^*\|_2 \ge \min_{i \in S^*} |x_i^*|. $$

We conclude that $\min_{i \in S^*} |x_i^*| \le \frac{2}{\sqrt{1-\delta_{2k}}} \|e\|_2$ which contradicts (52).

As a conclusion, when $\min_{i \in S^*} |x_i^*| > \frac{2}{\sqrt{1-\delta_{2k}}} \|e\|_2$, we have $S^* \subseteq S^{t_{BEST}}$.

In this case, since the support of $x^{t_{BEST}} - x^*$ is of size smaller than $k$, we can redo the above calculation and obtain

$$ \sqrt{1 - \delta_k} \|x^{t_{BEST}} - x^*\|_2 \le \|A(x^{t_{BEST}} - x^*)\|_2 \le 2\|e\|_2. $$

This leads to the last inequality of Theorem C.9 and concludes the proof.

## C.5 Proof of Corollary 4.2

We assume that $x^*$ satisfies ($RC_{SRIP}$) and that $\|e\|_2 = 0$. Let us first prove that $x^*$ satisfies ($RC_{RIP}$). Using ($RC_{SRIP}$) we have

$$ \begin{aligned} 0 < 1 - \Lambda &\le 1 - 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \\ &= \frac{2k}{\min_{i \in S^*} |x_i^*|} \left( \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{RIP} \|x^*\|_2 \right). \end{aligned} $$

As a consequence, since $2k > 0$ and $\min_{i \in S^*} |x_i^*| > 0$,

$$ 0 < \frac{\min_{i \in S^*} |x_i^*|}{2k} - \alpha_k^{RIP} \|x^*\|_2. \quad (53) $$

We conclude that $x^*$ satisfies the ($RC_{RIP}$) for $A$.

Applying Theorem 4.1 and since $\|e\|_2 = 0$ and $X^0 = 0$, we know that there exists $t \le T_{RIP} = \frac{(k+1)}{1-2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}}$ such that $S^* \subseteq S^t$. It is not difficult to check that the function $f: \mathbb{R} \to \mathbb{R}$ defined for all $u \in \mathbb{R}$ by $f(u) = \frac{k+1}{1-u}$ is increasing on $[0, 1)$. By applying $f$ to

$$ 0 \le 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \le \Lambda < 1, $$

we obtain

$$ T_{RIP} = f \left( 2k\alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} \right) \le f(\Lambda) = T_{SRIP}, $$

where $T_{SRIP}$ is defined in Corollary 4.2.

Therefore $t \le T_{SRIP}$ and we conclude that there exists $t \le T_{SRIP}$ such that $S^* \subseteq S^t$.

The last statement of Corollary 4.2 is a direct consequence of Theorem 4.1 and $x^*$ satisfies (7) with $\|e\| = 0$.

This concludes the proof of Corollary 4.2.
## C.6 Comments on (RC<sub>RIP</sub>) and (RC<sub>SRIIP</sub>)

The hypotheses of Theorem 4.1 are on the RIP of A and there are two hypotheses on $x^*$: (RC<sub>RIP</sub>) and (7). The condition (RC<sub>RIP</sub>) is described below Corollary 4.2. In Corollary 4.2, the condition becomes (RC<sub>SRIIP</sub>). We adapt in the section the analysis of the (RC<sub>RIP</sub>) to condition (RC<sub>SRIIP</sub>) and show that it is not vacuous under a similar constraint on $\alpha_k^{RIP}$.

If $\alpha_k^{RIP}$ is too large, there does not exist any $x^*$ satisfying (RC<sub>SRIIP</sub>). It is for instance the case if $\alpha_k^{RIP} \ge 0.5$. On the contrary, a sufficient condition of existence of vectors $x^*$ satisfying (RC<sub>SRIIP</sub>) is that the constant $\alpha_k^{RIP}$ satisfies $2k^{3/2} \alpha_k^{RIP} \le \Lambda < 1$. In this case, when all non-zero entries of $x^*$ are equal, we have $\|x^*\|_2 = \sqrt{|S^*|} \min_{i \in S^*} |x_i^*|$ and $2k \alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} = 2k \alpha_k^{RIP} \sqrt{|S^*|} \le 2k^{3/2} \alpha_k^{RIP} \le \Lambda < 1$. Summarizing, when $2k^{3/2} \alpha_k^{RIP} < 1$, there exist vectors $x^*$ satisfying (RC<sub>SRIIP</sub>) and the condition of Corollary 4.2 is not vacuous.

As a conclusion, when $\alpha_k^{RIP} < \frac{1}{2}k^{-3/2}$, both Theorem 4.1 and Corollary 4.2 can be applied for a non-empty set of vectors $x^*$. Moreover, we can prove that the interior of the sets of $x^*$ satisfying respectively (RC<sub>RIP</sub>) and (RC<sub>SRIIP</sub>) are not empty. The two sets grow as $\alpha_k^{RIP}$ decreases. When $\|e\|_2 = 0$, the two sets are conical.

# D Additional Results for Phase Transition Diagram Experiment

We consider the same experiment as in Section 5.1 but in the noiseless setting. The analog of the curves of Figure 2 are in Figure 6. Again, an artifact stemming from the discrete values of $(m, n, k)$ is responsible for the smooth and decreasing part observed on the left side of the phase transition curves, in a region where $k=1$. Without noise, all algorithms exhibit a similar phase transition curve and maintain the same ranking as in the noisy setting. The conclusions that are drawn in the noiseless setting from Figure 6 are analog to those in Section 5.1 in the noisy setting.

<figure><img src="image_11.png" /><figcaption>Figure 6: Phase transition diagram (noiseless setting). Problems below each curve are solved by the related algorithm with a success rate larger than 95%. $\zeta = m/n$ denotes the ratio between the number of rows and the number of columns in A while $\rho = k/m$ denotes the ratio between the sparsity and the number of rows in A. Matrix A have i.i.d. standard Gaussian entries and non-zero entries in $x^*$ are drawn uniformly in $[-2, -1] \cup [1, 2]$. $n = 500$ is fixed and results are obtained from 1000 runs.</figcaption></figure>

# E Additional Results in Deconvolution

To supplement Section 5.2, we present additional results for the initial experimental setup. In Appendix E.1, we provide the results for the full signal of Figure 3. In Appendix E.2, we display the loss along the iterative process for the experiment shown in Figure 3. In Appendix E.3 (resp. Appendix E.4), we show the average number of explored supports (resp. the average loss and Wasserstein distance) over the $r=200$ problems solved to construct Figure 4 as $k$ varies. We present results for the noiseless case when $e=0$ in Appendix E.5. Finally, we present the analog of Figure 4 for different configurations. We depict the case where the sparsity provided to the algorithm is incorrect in Appendix E.6. The noise
### C.6 Comments on (RC<sub>RIP</sub>) and (RC<sub>SRIIP</sub>)

The hypotheses of Theorem 4.1 are on the RIP of A and there are two hypotheses on $x^*$: (RC<sub>RIP</sub>) and (7). The condition (RC<sub>RIP</sub>) is described below Corollary 4.2. In Corollary 4.2, the condition becomes (RC<sub>SRIIP</sub>). We adapt in the section the analysis of the (RC<sub>RIP</sub>) to condition (RC<sub>SRIIP</sub>) and show that it is not vacuous under a similar constraint on $\alpha_k^{RIP}$.

If $\alpha_k^{RIP}$ is too large, there does not exist any $x^*$ satisfying (RC<sub>SRIIP</sub>). It is for instance the case if $\alpha_k^{RIP} \ge 0.5$. On the contrary, a sufficient condition of existence of vectors $x^*$ satisfying (RC<sub>SRIIP</sub>) is that the constant $\alpha_k^{RIP}$ satisfies $2k^{3/2} \alpha_k^{RIP} \le \Lambda < 1$. In this case, when all non-zero entries of $x^*$ are equal, we have $\|x^*\|_2 = \sqrt{|S^*|} \min_{i \in S^*} |x_i^*|$ and $2k \alpha_k^{RIP} \frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|} = 2k \alpha_k^{RIP} \sqrt{|S^*|} \le 2k^{3/2} \alpha_k^{RIP} \le \Lambda < 1$. Summarizing, when $2k^{3/2} \alpha_k^{RIP} < 1$, there exist vectors $x^*$ satisfying (RC<sub>SRIIP</sub>) and the condition of Corollary 4.2 is not vacuous.

As a conclusion, when $\alpha_k^{RIP} < \frac{1}{2}k^{-3/2}$, both Theorem 4.1 and Corollary 4.2 can be applied for a non-empty set of vectors $x^*$. Moreover, we can prove that the interior of the sets of $x^*$ satisfying respectively (RC<sub>RIP</sub>) and (RC<sub>SRIIP</sub>) are not empty. The two sets grow as $\alpha_k^{RIP}$ decreases. When $\|e\|_2 = 0$, the two sets are conical.

## D Additional Results for Phase Transition Diagram Experiment

We consider the same experiment as in Section 5.1 but in the noiseless setting. The analog of the curves of Figure 2 are in Figure 6. Again, an artifact stemming from the discrete values of $(m, n, k)$ is responsible for the smooth and decreasing part observed on the left side of the phase transition curves, in a region where $k=1$. Without noise, all algorithms exhibit a similar phase transition curve and maintain the same ranking as in the noisy setting. The conclusions that are drawn in the noiseless setting from Figure 6 are analog to those in Section 5.1 in the noisy setting.

<figure><img src="image_10.png" /><figcaption>Figure 6: Phase transition diagram (noiseless setting). Problems below each curve are solved by the related algorithm with a success rate larger than 95%. $\zeta = m/n$ denotes the ratio between the number of rows and the number of columns in A while $\rho = k/m$ denotes the ratio between the sparsity and the number of rows in A. Matrix A have i.i.d. standard Gaussian entries and non-zero entries in $x^*$ are drawn uniformly in $[-2, -1] \cup [1, 2]$. $n = 500$ is fixed and results are obtained from 1000 runs.</figcaption></figure>

## E Additional Results in Deconvolution

To supplement Section 5.2, we present additional results for the initial experimental setup. In Appendix E.1, we provide the results for the full signal of Figure 3. In Appendix E.2, we display the loss along the iterative process for the experiment shown in Figure 3. In Appendix E.3 (resp. Appendix E.4), we show the average number of explored supports (resp. the average loss and Wasserstein distance) over the $r=200$ problems solved to construct Figure 4 as $k$ varies. We present results for the noiseless case when $e=0$ in Appendix E.5. Finally, we present the analog of Figure 4 for different configurations. We depict the case where the sparsity provided to the algorithm is incorrect in Appendix E.6. The noise
robustness is studied in Appendix E.7 and the variant $y = A(x^* + e')$ of the initial problem $y = Ax^* + e'$ is studied in Appendix E.8. The impact of increasing the magnitude of $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$, testing the importance of conditions $RC_{RIP}$ and $RC_{SRIP}$, is shown in Appendix E.9. The impact of the variation of the step size for IHT and HTP is presented in Appendix E.10. Lastly, considerations on a random search are discussed in Appendix E.11.

## E.1 Deconvolution: Examining the Specific Instance from Figure 3

In Figure 7, we present the full signal corresponding to the cropped instance in Figure 3. For clarity, Figure 8 displays the same crop as Figure 3, presenting the results obtained with all studied algorithms.

In this representation, nearly all algorithms can identify isolated spikes. However, challenges arise when spikes are close, leading algorithms to struggle with precise localization. Notably, IHT and HTP exhibit false detections in the most energetic part of the signal (around positions 140, 180, 260, and 400), getting trapped in local minima. On this experiment (this is not the case in general), initializing SEA with ELS or OMP allows $SEA_{ELS}$ and $SEA_{OMP}$ to find a better approximation of $S^*$ than $SEA_0$. These two versions of SEA successfully recover the original signal, except for two spikes between positions 410 and 425. In contrast, other algorithms fail due to the coherence of $A$ and the presence of additive noise.

<figure><img src="image_12.png" /><figcaption>Figure 7: Full version of Figure 3. Representation of an instance of $x^*$, $y$ and the solutions provided by the algorithms ($k = 20, n = 500$).</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 8: Crop from the dashed area in Figure 7, matching the location of Figure 3 with results from all analyzed algorithms. This region corresponds to the most densely populated area within the signal.</figcaption></figure>

## E.2 Deconvolution: Loss along the Iterative Process

Figures 9 and 10 illustrate the behavior of HTP, IHT, ELS, $SEA_0$, $SEA_{OMP}$ and $SEA_{ELS}$, for the same 20-sparse vector $x^*$ used in Figure 3 (Section 5.2) and Figures 7 and 8 (Appendix E.1), throughout the iterative process.
robustness is studied in Appendix E.7 and the variant $y = A(x^* + e')$ of the initial problem $y = Ax^* + e'$ is studied in Appendix E.8. The impact of increasing the magnitude of $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$, testing the importance of conditions $RC_{RIP}$ and $RC_{SRIP}$, is shown in Appendix E.9. The impact of the variation of the step size for IHT and HTP is presented in Appendix E.10. Lastly, considerations on a random search are discussed in Appendix E.11.

## E.1 Deconvolution: Examining the Specific Instance from Figure 3

In Figure 7, we present the full signal corresponding to the cropped instance in Figure 3. For clarity, Figure 8 displays the same crop as Figure 3, presenting the results obtained with all studied algorithms.

In this representation, nearly all algorithms can identify isolated spikes. However, challenges arise when spikes are close, leading algorithms to struggle with precise localization. Notably, IHT and HTP exhibit false detections in the most energetic part of the signal (around positions 140, 180, 260, and 400), getting trapped in local minima. On this experiment (this is not the case in general), initializing SEA with ELS or OMP allows $SEA_{ELS}$ and $SEA_{OMP}$ to find a better approximation of $S^*$ than $SEA_0$. These two versions of SEA successfully recover the original signal, except for two spikes between positions 410 and 425. In contrast, other algorithms fail due to the coherence of $A$ and the presence of additive noise.

<figure><img src="image_11.png" /><figcaption>Figure 7: Full version of Figure 3. Representation of an instance of $x^*$, $y$ and the solutions provided by the algorithms ($k = 20, n = 500$).</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 8: Crop from the dashed area in Figure 7, matching the location of Figure 3 with results from all analyzed algorithms. This region corresponds to the most densely populated area within the signal.</figcaption></figure>

## E.2 Deconvolution: Loss along the Iterative Process

Figures 9 and 10 illustrate the behavior of HTP, IHT, ELS, $SEA_0$, $SEA_{OMP}$ and $SEA_{ELS}$, for the same 20-sparse vector $x^*$ used in Figure 3 (Section 5.2) and Figures 7 and 8 (Appendix E.1), throughout the iterative process.
<figure><img src="image_14.png" /><figcaption>Figure 9: Representation of $\ell_{2,rel\_loss}(x^t)$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}}(t))$ (dashed lines) for each iteration of several algorithms, for the experiment of Figure 3.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>Figure 10: Representation of $\ell_{2,rel\_loss}(x^{t(s)})$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}(t(s))})$ (dashed lines) for each new explored support of several algorithms, for the experiment of Figure 3.</figcaption></figure>

More precisely, in Figure 9 the solid curves represent $\ell_{2,rel\_loss}(x^t)$ when $t$ varies in $[0, 1000]$, where $\ell_{2,rel\_loss}$ is defined by

$$ \ell_{2,rel\_loss}(x) = \frac{\|Ax - y\|_2}{\|y\|_2}. \qquad (54) $$

The dashed lines represent $\ell_{2,rel\_loss}(x^{t_{BEST}(t)})$ where $t_{BEST}(t) = \underset{t' \in [0, t]}{\operatorname{argmin}} \|Ax^{t'} - y\|_2$ and $t$ varies in $[0, 1000]$.

Overall, no algorithm succeeds in reaching zero error. ELS performs only one iteration before stopping in a local minimum ($\ell_{2,rel\_loss}(x^1) \approx 0.2$). HTP completes a few iterations before stopping. IHT outperforms HTP by exploring a bit more. One can observe that, due to the exploratory nature of SEA, $\ell_{2,rel\_loss}(x^t)$ oscillates for both versions of SEA. This exploration enables $SEA_{ELS}$ to refine the ELS estimate within 300 iterations. Despite faster decay around the 100th iteration, $SEA_{OMP}$ finally reaches $SEA_{ELS}$ after 620 iterations.

We observe that HTP and IHT exhibit poor performance due to the high coherence of A. As demonstrated in Appendix E.1, these algorithms initially make the mistake of erroneously assigning several neighboring atoms to represent the same large bump and fail to correct this error during the iterative process.

Figure 10 illustrates the same iterative process as Figure 9, focusing on support exploration rather than the iteration count for each algorithm. Here, the solid curves represent $\ell_{2,rel\_loss}(x^{t(s)})$ when $s$ varies
<figure><img src="image_13.png" /><figcaption>Figure 9: Representation of $\ell_{2,rel\_loss}(x^t)$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}}(t))$ (dashed lines) for each iteration of several algorithms, for the experiment of Figure 3.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 10: Representation of $\ell_{2,rel\_loss}(x^{t(s)})$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}(t(s))})$ (dashed lines) for each new explored support of several algorithms, for the experiment of Figure 3.</figcaption></figure>

More precisely, in Figure 9 the solid curves represent $\ell_{2,rel\_loss}(x^t)$ when $t$ varies in $[0, 1000]$, where $\ell_{2,rel\_loss}$ is defined by

$$ \ell_{2,rel\_loss}(x) = \frac{\|Ax - y\|_2}{\|y\|_2}. \qquad (54) $$

The dashed lines represent $\ell_{2,rel\_loss}(x^{t_{BEST}(t)})$ where $t_{BEST}(t) = \underset{t' \in [0,t]}{\operatorname{argmin}} \|Ax^{t'} - y\|_2$ and $t$ varies in $[0, 1000]$.

Overall, no algorithm succeeds in reaching zero error. ELS performs only one iteration before stopping in a local minimum ($\ell_{2,rel\_loss}(x^1) \approx 0.2$). HTP completes a few iterations before stopping. IHT outperforms HTP by exploring a bit more. One can observe that, due to the exploratory nature of SEA, $\ell_{2,rel\_loss}(x^t)$ oscillates for both versions of SEA. This exploration enables $SEA_{ELS}$ to refine the ELS estimate within 300 iterations. Despite faster decay around the 100th iteration, $SEA_{OMP}$ finally reaches $SEA_{ELS}$ after 620 iterations.

We observe that HTP and IHT exhibit poor performance due to the high coherence of A. As demonstrated in Appendix E.1, these algorithms initially make the mistake of erroneously assigning several neighboring atoms to represent the same large bump and fail to correct this error during the iterative process.

Figure 10 illustrates the same iterative process as Figure 9, focusing on support exploration rather than the iteration count for each algorithm. Here, the solid curves represent $\ell_{2,rel\_loss}(x^{t(s)})$ when $s$ varies
from 0 to the number of explored supports, where $t(s)$ is the iteration associated to the $s^{th}$ explored support (without redundancy). As in the previous figure, the dashed lines represent $\ell_{2,rel\_loss}(x^{t_{BEST}}(t(s)))$ where $t_{BEST}(t(s)) = \underset{t' \in [0,t(s)]}{\operatorname{argmin}} \|Ax^{t'} - y\|_2^2$. This is the loss associated to the best estimate found while exploring the $s^{th}$ supports.

We observe that HTP explores very little before stopping in a local minimum. Despite performing only one iteration, ELS explores 500 supports within the neighborhood of its OMP initialization for a slight improvement. Here, $\text{SEA}_0$ explores one new support at each iteration, while $\text{SEA}_{\text{ELS}}$ explores fewer, improving upon ELS by exploring less than 250 supports. Again, despite faster decay at the beginning, $\text{SEA}_{\text{OMP}}$ finally reaches $\text{SEA}_{\text{ELS}}$ after exploring around 520 supports. This reveals how efficient each algorithm is at finding relevant supports.

## E.3 Deconvolution: Number of Explored Supports

As discussed in Section 3.3, the overall cost of the algorithms depends on the number of explored supports. In Figure 11, we illustrate the number of explored supports in two different ways. First, in Figure 11 (left), we present the average number of explored supports for the entire problem resolution — representing the overall cost. This includes supports explored before initialization. For instance, $\text{SEA}_{\text{OMP}}$ includes both the supports explored by OMP for its initialization and those explored subsequently in the SEA procedure. Then, in Figure 11 (right), we present the average number of explored supports that actually required computation after initialization. These curves reveal the cost of the algorithms after initialization, where supports seen before the initialization (e.g., those of OMP for $\text{SEA}_{\text{OMP}}$) are not included as they do not incur additional computing time.

<figure><img src="image_16.png" /><figcaption>Figure 11: Left: Average number of explored supports by algorithms solving the 200 problems in Section 5.2, across sparsity levels $k \in [1, 50]$. Right: Average number of explored supports from algorithms initialization in the same setup.</figcaption></figure>

Examining the overall cost of the algorithms on the left, we observe three types of exploration profiles. Some algorithms, such as OMP, OMPR, and HTP, exhibit minimal exploration. Notably, as $k$ increases, HTP explores fewer supports. On the other hand, algorithms like ELS explore extensively. SEA falls in between, exploring a few supports for small $k$ and more as $k$ increases until reaching a threshold. Despite exploring at least two times fewer supports than ELS, SEA's more efficient exploration allows it to achieve better results, as demonstrated in Figure 4.

From this figure, we observe that adding SEA to ELS ($\text{SEA}_{\text{ELS}}$) does not significantly alter the order of magnitude of the cost. Turning our attention to the cost after initialization on the right, we do not observe $\text{HTP}_{\text{ELS}}$ and $\text{HTP}_{\text{OMP}}$ because they do not explore after their initialization, as shown in Figure 10 for $\text{HTP}_{\text{ELS}}$. OMP and $\text{SEA}_0$ curves remain unchanged because they do not have any initializing algorithms.

All SEA variants exhibit a similar order of magnitude of explored supports. However, we conclude that the stronger the initialization (with $0 < \text{OMP} < \text{ELS}$), the more challenging the exploration becomes due to the high coherence of $A$ and the local minima in which OMP and ELS end up.
from 0 to the number of explored supports, where $t(s)$ is the iteration associated to the $s^{th}$ explored support (without redundancy). As in the previous figure, the dashed lines represent $\ell_{2,rel\_loss}(x^{t_{BEST}}(t(s)))$ where $t_{BEST}(t(s)) = \underset{t' \in [0,t(s)]}{\operatorname{argmin}} \|Ax^{t'} - y\|_2^2$. This is the loss associated to the best estimate found while exploring the $s^{th}$ supports.

We observe that HTP explores very little before stopping in a local minimum. Despite performing only one iteration, ELS explores 500 supports within the neighborhood of its OMP initialization for a slight improvement. Here, $\text{SEA}_0$ explores one new support at each iteration, while $\text{SEA}_{\text{ELS}}$ explores fewer, improving upon ELS by exploring less than 250 supports. Again, despite faster decay at the beginning, $\text{SEA}_{\text{OMP}}$ finally reaches $\text{SEA}_{\text{ELS}}$ after exploring around 520 supports. This reveals how efficient each algorithm is at finding relevant supports.

## E.3 Deconvolution: Number of Explored Supports

As discussed in Section 3.3, the overall cost of the algorithms depends on the number of explored supports. In Figure 11, we illustrate the number of explored supports in two different ways. First, in Figure 11 (left), we present the average number of explored supports for the entire problem resolution — representing the overall cost. This includes supports explored before initialization. For instance, $\text{SEA}_{\text{OMP}}$ includes both the supports explored by OMP for its initialization and those explored subsequently in the SEA procedure. Then, in Figure 11 (right), we present the average number of explored supports that actually required computation after initialization. These curves reveal the cost of the algorithms after initialization, where supports seen before the initialization (e.g., those of OMP for $\text{SEA}_{\text{OMP}}$) are not included as they do not incur additional computing time.

<figure><img src="image_15.png" /><figcaption>Figure 11: Left: Average number of explored supports by algorithms solving the 200 problems in Section 5.2, across sparsity levels $k \in [1, 50]$. Right: Average number of explored supports from algorithms initialization in the same setup.</figcaption></figure>

Examining the overall cost of the algorithms on the left, we observe three types of exploration profiles. Some algorithms, such as OMP, OMPR, and HTP, exhibit minimal exploration. Notably, as $k$ increases, HTP explores fewer supports. On the other hand, algorithms like ELS explore extensively. SEA falls in between, exploring a few supports for small $k$ and more as $k$ increases until reaching a threshold. Despite exploring at least two times fewer supports than ELS, SEA's more efficient exploration allows it to achieve better results, as demonstrated in Figure 4.

From this figure, we observe that adding SEA to ELS ($\text{SEA}_{\text{ELS}}$) does not significantly alter the order of magnitude of the cost. Turning our attention to the cost after initialization on the right, we do not observe $\text{HTP}_{\text{ELS}}$ and $\text{HTP}_{\text{OMP}}$ because they do not explore after their initialization, as shown in Figure 10 for $\text{HTP}_{\text{ELS}}$. OMP and $\text{SEA}_0$ curves remain unchanged because they do not have any initializing algorithms.

All SEA variants exhibit a similar order of magnitude of explored supports. However, we conclude that the stronger the initialization (with $0 < \text{OMP} < \text{ELS}$), the more challenging the exploration becomes due to the high coherence of $A$ and the local minima in which OMP and ELS end up.
## E.4 Deconvolution: Average Loss and Wasserstein Distance when $k$ Varies

In this section, we complement the analysis of the experiment described in Section 5.2, the results of which are already depicted in Figure 4.

In Figure 12, we present the average – over the $r = 200$ problems – of the relative $l_2$ loss ($l_{2,rel\_loss}$), defined in (54), for the outputs of all algorithms and for $k \in [1, 50]$. We observe that all versions of SEA achieve the lowest errors for $k < 20$. The largest gap between SEA and its competitors is observed for $k$ between 9 and 13. For clarity, the curves for HTP and IHT are visible for small $k$ only. Due to the high coherence of $A$ and their method of selecting multiple elements of the support estimate at once, both IHT and HTP attempt to reconstruct single peaks with multiple atoms, leading to much larger errors than those of the competitors.

<figure><img src="image_17.png" /><figcaption>Figure 12: Mean of $l_{2,rel\_loss}(x)$ – defined in (54) – for the outputs of the algorithms on the 200 problems of Section 5.2, for each sparsity level $k \in [1, 50]$.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Figure 13: Mean of the Wassertstein distance between the outputs of the algorithms and the solutions $x^*$ of the 200 problems of Section 5.2, for each sparsity level $k \in [1, 50]$.</figcaption></figure>

In Figure 13, we show the mean of the Wasserstein-1-distance (also called Earth mover's distance) over the same problems. It illustrates how 'far' the chosen spikes are from the true ones. Again, all the versions of SEA achieve the smallest distances for $k < 18$. As $k$ increases, despite being the best at finding the exact position of the spikes (see Figure 4), $SEA_0$ and, to a lesser extent, $SEA_{OMP}$ and $SEA_{ELS}$, choose spikes 'far' from the true ones when they are mistaken, while IHT improves for the highest $k$.

## E.5 Deconvolution: Results in the Noiseless Setup

We consider the same experiment as in Section 5.2 but in a noiseless setting ($e = 0$). Thus, we set again $n = 500$, a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation equal to 3. We tested every algorithm on $r = 200$ noiseless problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$.

### E.5.1 Visualization of a Specific Instance

The counterparts of the curves in Figures 7 and 8 from Appendix E.2 in the noiseless case are shown in Figures 14 and 15. The algorithms behave in a similar way to the noisy case. However, with no perturbation in the signal, all versions of SEA successfully recover the exact positions of the spikes, whereas no other algorithm achieves such a performance.

### E.5.2 Loss along the Iterative Process

The analogs of Figures 9 and 10 from Appendix E.2 are respectively shown in Figures 16 and 17. The conclusions drawn here in the noiseless setting are similar to those in Appendix E.2.

Similarly to the noisy case, it can be observed in Figure 16 that due to the exploratory nature of SEA, $l_{2,rel\_loss}(x^t)$ oscillates for all versions of SEA. However, this does not prevent $SEA_0$ from finding a better approximation of $S^*$ than ELS in the first 80 iterations and eventually recovering $S^*$ despite the high coherence of $A$. Indeed, for all SEA versions, once $S^*$ is recovered in the noiseless setting, for $t$ sufficiently large, $x^t = x^*$, and therefore $Ax^t - y = 0$. Using the update rule of $X^t$ in line 8 of Algorithm 1, we observe that $X^t$ should no longer evolve, and no new support is explored. This behavior is evident not only from Figure 16 but also from Figure 17. Furthermore, as can be seen in Figure 14, ELS does not improve OMP thus leading to an identical initialization for $SEA_{OMP}$ and $SEA_{ELS}$. Consequently, these
## E.4 Deconvolution: Average Loss and Wasserstein Distance when $k$ Varies

In this section, we complement the analysis of the experiment described in Section 5.2, the results of which are already depicted in Figure 4.

In Figure 12, we present the average – over the $r = 200$ problems – of the relative $l_2$ loss ($l_{2,rel\_loss}$), defined in (54), for the outputs of all algorithms and for $k \in [1, 50]$. We observe that all versions of SEA achieve the lowest errors for $k < 20$. The largest gap between SEA and its competitors is observed for $k$ between 9 and 13. For clarity, the curves for HTP and IHT are visible for small $k$ only. Due to the high coherence of $A$ and their method of selecting multiple elements of the support estimate at once, both IHT and HTP attempt to reconstruct single peaks with multiple atoms, leading to much larger errors than those of the competitors.

<figure><img src="image_16.png" /><figcaption>Figure 12: Mean of $l_{2,rel\_loss}(x)$ – defined in (54) – for the outputs of the algorithms on the 200 problems of Section 5.2, for each sparsity level $k \in [1, 50]$.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Figure 13: Mean of the Wassertstein distance between the outputs of the algorithms and the solutions $x^*$ of the 200 problems of Section 5.2, for each sparsity level $k \in [1, 50]$.</figcaption></figure>

In Figure 13, we show the mean of the Wasserstein-1-distance (also called Earth mover's distance) over the same problems. It illustrates how 'far' the chosen spikes are from the true ones. Again, all the versions of SEA achieve the smallest distances for $k < 18$. As $k$ increases, despite being the best at finding the exact position of the spikes (see Figure 4), $SEA_0$ and, to a lesser extent, $SEA_{OMP}$ and $SEA_{ELS}$, choose spikes 'far' from the true ones when they are mistaken, while IHT improves for the highest $k$.

## E.5 Deconvolution: Results in the Noiseless Setup

We consider the same experiment as in Section 5.2 but in a noiseless setting ($e = 0$). Thus, we set again $n = 500$, a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation equal to 3. We tested every algorithm on $r = 200$ noiseless problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$.

### E.5.1 Visualization of a Specific Instance

The counterparts of the curves in Figures 7 and 8 from Appendix E.2 in the noiseless case are shown in Figures 14 and 15. The algorithms behave in a similar way to the noisy case. However, with no perturbation in the signal, all versions of SEA successfully recover the exact positions of the spikes, whereas no other algorithm achieves such a performance.

### E.5.2 Loss along the Iterative Process

The analogs of Figures 9 and 10 from Appendix E.2 are respectively shown in Figures 16 and 17. The conclusions drawn here in the noiseless setting are similar to those in Appendix E.2.

Similarly to the noisy case, it can be observed in Figure 16 that due to the exploratory nature of SEA, $l_{2,rel\_loss}(x^t)$ oscillates for all versions of SEA. However, this does not prevent $SEA_0$ from finding a better approximation of $S^*$ than ELS in the first 80 iterations and eventually recovering $S^*$ despite the high coherence of $A$. Indeed, for all SEA versions, once $S^*$ is recovered in the noiseless setting, for $t$ sufficiently large, $x^t = x^*$, and therefore $Ax^t - y = 0$. Using the update rule of $X^t$ in line 8 of Algorithm 1, we observe that $X^t$ should no longer evolve, and no new support is explored. This behavior is evident not only from Figure 16 but also from Figure 17. Furthermore, as can be seen in Figure 14, ELS does not improve OMP thus leading to an identical initialization for $SEA_{OMP}$ and $SEA_{ELS}$. Consequently, these
<figure><img src="image_19.png" /><figcaption>Figure 14: Representation of an instance of $x^*$ and $y$ with the solutions provided by the algorithms when $k = 20$ and $n = 500$ in the noiseless case: Full signal.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 15: Crop from the dashed area in Figure 14. This region corresponds to the most densely populated area within the signal.</figcaption></figure>

last two algorithms thus follow the same trajectory. From Figure 17, we however observe thatSEA<sub>ELS</sub> and SEA<sub>OMP</sub> must explore twice as many supports as SEA<sub>0</sub>.

### E.5.3 Number of Explored Supports

The analog of Figure 11 from Appendix E.3 is shown in Figure 18. The conclusions drawn here in the noiseless case are similar to those in Appendix E.3.

All the algorithms behave in the same way as in the noisy experiment.

### E.5.4 Average dist<sub>supp</sub>, Loss, and Wasserstein Distance when k Varies

The analogs of Figures 4, 12 and 13 are respectively displayed in Figures 19 to 21. The results in the noiseless setting closely mirror those in Section 5.2 and Appendix E.4 in the noisy setting.

In Figure 19, for sparsity levels $k < 30$, SEA<sub>0</sub>, SEA<sub>OMP</sub>, and SEA<sub>ELS</sub> outperform the other algorithms. Across all studied sparsity levels, SEA<sub>0</sub> is reaching the best performances.

Moving to Figure 20, the absence of noise makes the problems easier to solve. Despite overall improvement, SEA<sub>0</sub> still attains the lowest error for the smallest $k$, followed by SEA<sub>ELS</sub>. Once again, HTP and IHT exhibit much larger errors than their competitors.

In Figure 21, as $k$ increases, SEA<sub>0</sub>, followed by SEA<sub>ELS</sub> and eventually IHT, exhibits the lowest Wasserstein distance.

## E.6 Deconvolution: Impact of an Erroneous Input Sparsity $k$

We consider the same experiment as in Section 5.2 but in the case where the sparsity $k$ is wrongly estimated. Thus, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse
<figure><img src="image_18.png" /><figcaption>Figure 14: Representation of an instance of $x^*$ and $y$ with the solutions provided by the algorithms when $k = 20$ and $n = 500$ in the noiseless case: Full signal.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Figure 15: Crop from the dashed area in Figure 14. This region corresponds to the most densely populated area within the signal.</figcaption></figure>

last two algorithms thus follow the same trajectory. From Figure 17, we however observe thatSEA<sub>ELS</sub> and SEA<sub>OMP</sub> must explore twice as many supports as SEA<sub>0</sub>.

### E.5.3 Number of Explored Supports

The analog of Figure 11 from Appendix E.3 is shown in Figure 18. The conclusions drawn here in the noiseless case are similar to those in Appendix E.3.

All the algorithms behave in the same way as in the noisy experiment.

### E.5.4 Average dist<sub>supp</sub>, Loss, and Wasserstein Distance when k Varies

The analogs of Figures 4, 12 and 13 are respectively displayed in Figures 19 to 21. The results in the noiseless setting closely mirror those in Section 5.2 and Appendix E.4 in the noisy setting.

In Figure 19, for sparsity levels $k < 30$, SEA<sub>0</sub>, SEA<sub>OMP</sub>, and SEA<sub>ELS</sub> outperform the other algorithms. Across all studied sparsity levels, SEA<sub>0</sub> is reaching the best performances.

Moving to Figure 20, the absence of noise makes the problems easier to solve. Despite overall improvement, SEA<sub>0</sub> still attains the lowest error for the smallest $k$, followed by SEA<sub>ELS</sub>. Once again, HTP and IHT exhibit much larger errors than their competitors.

In Figure 21, as $k$ increases, SEA<sub>0</sub>, followed by SEA<sub>ELS</sub> and eventually IHT, exhibits the lowest Wasserstein distance.

## E.6 Deconvolution: Impact of an Erroneous Input Sparsity $k$

We consider the same experiment as in Section 5.2 but in the case where the sparsity $k$ is wrongly estimated. Thus, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse
<figure><img src="image_21.png" /><figcaption>Figure 16: Representation of $\ell_{2,rel\_loss}(x^t)$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}}(t))$ (dashed lines) for each iteration of several algorithms, for the noiseless experiment.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Figure 17: Representation of $\ell_{2,rel\_loss}(x^{t(s)})$ (solid lines) and $\ell_{2,rel\_loss}(x^{t_{BEST}}(t(s)))$ (dashed lines) for each new explored support of several algorithms, for the noiseless experiment.</figcaption></figure>
<figure><img src="image_20.png" /><figcaption>Figure 16: Representation of $l_{2,rel\_loss}(x^t)$ (solid lines) and $l_{2,rel\_loss}(x^{t_{BEST}}(t))$ (dashed lines) for each iteration of several algorithms, for the noiseless experiment.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Figure 17: Representation of $l_{2,rel\_loss}(x^{t(s)})$ (solid lines) and $l_{2,rel\_loss}(x^{t_{BEST}}(t(s)))$ (dashed lines) for each new explored support of several algorithms, for the noiseless experiment.</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>Figure 18: Left: Mean of the number of the explored supports by algorithms solving the 200 problems in the noiseless case, across sparsity levels $k \in [1, 50]$. Right: Mean of the number of the explored supports from algorithms initialization in the same setup.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 19: Mean of support distance $dist_{supp}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ in the noiseless setup.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Figure 20: Mean of $\ell_{2,rel,loss}(x)$ – defined in (54) – for the outputs of the algorithms on the 200 problems of the noiseless setup.</figcaption></figure>

<caption>Figure 21: Mean of the Wassertstein distance between the outputs of the algorithms and the solutions $x^*$ of the 200 problems of the noiseless setup.</caption>

$x^*$, with $k \in \{4p, p \in [1, 12]\}$. The difference here is that the algorithms are asked to recover a signal of sparsity $k' \neq k$.

The analogs of Figure 4 when $k' = 0.75k$ and $k' = 1.25k$ are depicted in Figures 22 and 23. Thus, not all values $k \in [1, 50]$ are tested because we wanted to keep a constant ratio $k'/k$ equal to 0.75 or 1.25. To ensure fairness in the underestimated case, we introduce a slightly different metric from $dist_{supp}$, which allows algorithms to achieve a distance equal to 0:
<figure><img src="image_22.png" /><figcaption>Figure 18: Left: Mean of the number of the explored supports by algorithms solving the 200 problems in the noiseless case, across sparsity levels $k \in [1, 50]$. Right: Mean of the number of the explored supports from algorithms initialization in the same setup.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Figure 19: Mean of support distance $dist_{supp}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ in the noiseless setup.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 20: Mean of $\ell_{2,rel,loss}(x)$ – defined in (54) – for the outputs of the algorithms on the 200 problems of the noiseless setup.</figcaption></figure>

<caption>Figure 21: Mean of the Wassertstein distance between the outputs of the algorithms and the solutions $x^*$ of the 200 problems of the noiseless setup.</caption>

$x^*$, with $k \in \{4p, p \in [1, 12]\}$. The difference here is that the algorithms are asked to recover a signal of sparsity $k' \neq k$.

The analogs of Figure 4 when $k' = 0.75k$ and $k' = 1.25k$ are depicted in Figures 22 and 23. Thus, not all values $k \in [1, 50]$ are tested because we wanted to keep a constant ratio $k'/k$ equal to 0.75 or 1.25. To ensure fairness in the underestimated case, we introduce a slightly different metric from $dist_{supp}$, which allows algorithms to achieve a distance equal to 0:
$$ dist_{\text{supp},k'}(x) = \frac{k' - |S^* \cap \text{supp}(x)|}{k'} $$

This metric shows how good is each algorithm at recovering only elements of $S^*$.

In Figure 22, we see that improving OMP and ELS is more difficult for $\text{SEA}_{\text{OMP}}$ and $\text{SEA}_{\text{ELS}}$, with $\text{SEA}_{\text{els}}$ being the lowest $dist_{\text{supp}}$ as in Figure 4. In Figures 22 and 23, we see that all algorithms reach a lower $dist_{\text{supp}}$ than in Figure 4. Thus, in these configurations, $\text{SEA}_{\text{els}}$ is still the algorithm reaching the lowest $dist_{\text{supp}}$. The better performance for $\frac{k'}{k} > 1$ is expected according to the definition of the mean support distance. Additionally, when $\frac{k'}{k} < 1$, the algorithms can focus on the largest entries of $x^*$ which are easier to recover.

Figures 24 and 25 complement the results presented in Figures 22 and 23 with another metric. Here we illustrate how the performance degrades when evaluating the mean support distance based on the largest estimated entries. Thus we introduce $K = \min\{k, k'\}$, and for any $x \in \mathbb{R}^n$ and $i \in [1, n]$

$$ dist_{\text{supp,largest}}(x) = \frac{K - |\text{supp}(x_{\text{largest}_K}^*) \cap \text{supp}(x_{\text{largest}_K})|}{K} \quad \text{with } (x_{\text{largest}_K})_i = \begin{cases} x_i & \text{if } i \in \text{largest}_K(x) \\ 0 & \text{if } i \notin \text{largest}_K(x) \end{cases} $$

When $k$ is underestimated (Figure 24), $dist_{\text{supp,largest}}$ depicts the capacity of each algorithm to recover $\text{supp}(x_{\text{largest}_K}^*)$, the support of the largest entries of $x^*$. When $k$ is overestimated (Figure 25), $dist_{\text{supp,largest}}$ depicts the capacity of each algorithm to recover $S^*$ in the largest entries of the provided solution. With this new metric, we observe in Figure 24 that the performance of all algorithms degrades. We also see the same phenomenon in Figure 25 with $\text{SEA}_{\text{els}}$ being less affected than the other algorithms and OMPR showing the best performance for $k < 11$.

<figure><img src="image_26.png" /><figcaption>Figure 22: Mean of support distance $dist_{\text{supp},k'}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is underestimated ($k' = 0.75k$).</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Figure 23: Mean of support distance $dist_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is overestimated ($k' = 1.25k$).</figcaption></figure>

## E.7 Deconvolution: Noise Robustness

We consider the same experiment as in Section 5.2 but using a noise $e$ uniformly drawn from the sphere of radius $\alpha \|Ax^*\|_2$ with $\alpha \in \{0.2, 0.3\}$ instead of $\alpha = 0.1$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$. The difference here is that we change the magnitude of the noise of the noisy problems.

The analogs of Figure 4 when $\alpha = 0.2$ and $\alpha = 0.3$ are depicted in Figures 26 and 27. As the noise increases, the performance of all algorithms degrades, without changing their ranking or the conclusions of the experiment.

## E.8 Deconvolution: Noise Before the Linear Transformation

We consider the same experiment as in Section 5.2 but add the noise $e$ differently. Instead, of generating $y = Ax^* + e$ with $e$ uniformly drawn from the sphere of radius $0.1 \|Ax^*\|_2$, we generate $y = A(x^* + e)$,
$$ dist_{\text{supp},k'}(x) = \frac{k' - |S^* \cap \text{supp}(x)|}{k'} $$

This metric shows how good is each algorithm at recovering only elements of $S^*$.

In Figure 22, we see that improving OMP and ELS is more difficult for $\text{SEA}_{\text{OMP}}$ and $\text{SEA}_{\text{ELS}}$, with $\text{SEA}_{\text{els}}$ being the lowest $dist_{\text{supp}}$ as in Figure 4. In Figures 22 and 23, we see that all algorithms reach a lower $dist_{\text{supp}}$ than in Figure 4. Thus, in these configurations, $\text{SEA}_{\text{els}}$ is still the algorithm reaching the lowest $dist_{\text{supp}}$. The better performance for $\frac{k'}{k} > 1$ is expected according to the definition of the mean support distance. Additionally, when $\frac{k'}{k} < 1$, the algorithms can focus on the largest entries of $x^*$ which are easier to recover.

Figures 24 and 25 complement the results presented in Figures 22 and 23 with another metric. Here we illustrate how the performance degrades when evaluating the mean support distance based on the largest estimated entries. Thus we introduce $K = \min\{k, k'\}$, and for any $x \in \mathbb{R}^n$ and $i \in [1, n]$

$$ dist_{\text{supp},\text{largest}}(x) = \frac{K - |\text{supp}(x_{\text{largest}}^*) \cap \text{supp}(x_{\text{largest}}^*)|}{K} \quad \text{with} \quad (x_{\text{largest}})_i = \begin{cases} x_i & \text{if } i \in \text{largest}_K(x) \\ 0 & \text{if } i \notin \text{largest}_K(x). \end{cases} $$

When $k$ is underestimated (Figure 24), $dist_{\text{supp},\text{largest}}$ depicts the capacity of each algorithm to recover $\text{supp}(x_{\text{largest}}^*)$, the support of the largest entries of $x^*$. When $k$ is overestimated (Figure 25), $dist_{\text{supp},\text{largest}}$ depicts the capacity of each algorithm to recover $S^*$ in the largest entries of the provided solution. With this new metric, we observe in Figure 24 that the performance of all algorithms degrades. We also see the same phenomenon in Figure 25 with $\text{SEA}_{\text{els}}$ being less affected than the other algorithms and OMPR showing the best performance for $k < 11$.

<figure><img src="image_25.png" /><figcaption>Figure 22: Mean of support distance $dist_{\text{supp},k'}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is underestimated ($k' = 0.75k$).</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>Figure 23: Mean of support distance $dist_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is overestimated ($k' = 1.25k$).</figcaption></figure>

## E.7 Deconvolution: Noise Robustness

We consider the same experiment as in Section 5.2 but using a noise $e$ uniformly drawn from the sphere of radius $\alpha \|Ax^*\|_2$ with $\alpha \in \{0.2, 0.3\}$ instead of $\alpha = 0.1$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$. The difference here is that we change the magnitude of the noise of the noisy problems.

The analogs of Figure 4 when $\alpha = 0.2$ and $\alpha = 0.3$ are depicted in Figures 26 and 27. As the noise increases, the performance of all algorithms degrades, without changing their ranking or the conclusions of the experiment.

## E.8 Deconvolution: Noise Before the Linear Transformation

We consider the same experiment as in Section 5.2 but add the noise $e$ differently. Instead, of generating $y = Ax^* + e$ with $e$ uniformly drawn from the sphere of radius $0.1 \|Ax^*\|_2$, we generate $y = A(x^* + e)$,
<figure><img src="image_28.png" /><figcaption>Figure 24: Mean of $\text{dist}_{\text{supp,largest}}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is underestimated ($k' = 0.75k$).</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 25: Mean of $\text{dist}_{\text{supp,largest}}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is overestimated ($k' = 1.25k$).</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>Figure 26: Mean of support distance $\text{dist}_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the noise $e$ is uniformly drawn from the sphere of radius $0.2 \|Ax^*\|_2$.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Figure 27: Mean of support distance $\text{dist}_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the noise $e$ is uniformly drawn from the sphere of radius $0.3 \|Ax^*\|_2$.</figcaption></figure>

with $e$ uniformly drawn from the sphere of radius $0.1 \|x^*\|_2$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$. The difference here is that we changed the way of adding the noise in the observations.

The analog of Figure 4 is depicted in Figure 28. The differences between these two figures are not significant. Thus, in this configuration, $\text{SEA}_0$ is the algorithm reaching the lowest $\text{dist}_{\text{supp}}$ and we have the same conclusions as in Section 5.2.

## E.9 Deconvolution: Increasing the Ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$

The ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$ is of importance in conditions $RC_{\text{RIP}}$ and $RC_{\text{SRIP}}$. We experimentally study whether it actually impacts the performance or whether it is an artifact of the proof. We consider the same experiment as in Section 5.2 but with the non-zero entries of $x^*$ drawn uniformly in $[[-10, -1]] \cup [1, 10]$ instead of $[-2, -1] \cup [1, 2]$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$.

The analog of Figure 4 is depicted in Figure 29. Here, OMP, OMPR, and ELS perform slightly better, while all the versions of SEA perform slightly worse. IHT and HTP also perform worse. However, the ranking of the algorithms remains the same. Thus, we can experimentally see that increasing the ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$ reduces SEA performance.
<figure><img src="image_27.png" /><figcaption>Figure 24: Mean of $\text{dist}_{\text{supp,largest}}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is underestimated ($k' = 0.75k$).</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>Figure 25: Mean of $\text{dist}_{\text{supp,largest}}$ between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the sparsity is overestimated ($k' = 1.25k$).</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>Figure 26: Mean of support distance $\text{dist}_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the noise $e$ is uniformly drawn from the sphere of radius $0.2 \|Ax^*\|_2$.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>Figure 27: Mean of support distance $\text{dist}_{\text{supp}}$ (defined in (8)) between $S^*$ and the support of the solutions provided by several algorithms as a function of the sparsity level $k$ when the noise $e$ is uniformly drawn from the sphere of radius $0.3 \|Ax^*\|_2$.</figcaption></figure>

with $e$ uniformly drawn from the sphere of radius $0.1 \|x^*\|_2$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$. The difference here is that we changed the way of adding the noise in the observations.

The analog of Figure 4 is depicted in Figure 28. The differences between these two figures are not significant. Thus, in this configuration, $\text{SEA}_0$ is the algorithm reaching the lowest $\text{dist}_{\text{supp}}$ and we have the same conclusions as in Section 5.2.

## E.9 Deconvolution: Increasing the Ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$

The ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$ is of importance in conditions $RC_{\text{RIP}}$ and $RC_{\text{SRIP}}$. We experimentally study whether it actually impacts the performance or whether it is an artifact of the proof. We consider the same experiment as in Section 5.2 but with the non-zero entries of $x^*$ drawn uniformly in $[[-10, -1]] \cup [1, 10]$ instead of $[-2, -1] \cup [1, 2]$. Again, we set $n = 500$ and use a convolution matrix $A$ corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different $k$-sparse $x^*$, with $k \in [1, 50]$.

The analog of Figure 4 is depicted in Figure 29. Here, OMP, OMPR, and ELS perform slightly better, while all the versions of SEA perform slightly worse. IHT and HTP also perform worse. However, the ranking of the algorithms remains the same. Thus, we can experimentally see that increasing the ratio $\frac{\|x^*\|_2}{\min_{i \in S^*} |x_i^*|}$ reduces SEA performance.
<figure><img src="image_32.png" /><figcaption>Figure 28: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level k when y = A(x* + e) with e uniformly drawn from the sphere of radius 0.1||x*||<sub>2</sub>.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>Figure 29: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level k when the non-zero entries of x* are drawn uniformly in [[-10, -1]] ∪ [[1, 10]].</figcaption></figure>

## E.10 Deconvolution: Step Size of IHT and HTP

In Section 5, we arbitrarily fixed the step size $\eta = \frac{1.8}{L}$ where L is the spectral radius of A. In this section, we study the influence of the step size on HTP and IHT. We also consider the Normalized Iterative Thresholding (NIHT) [9] algorithm which is based on IHT but includes an adaptive step size $\eta^t$ which depends on the iteration $t$. The step size is chosen as:

$$ \eta^t = \frac{\|(A^T(y - Ax^t))_{S^t}\|_2^2}{\|A((A^T(y - Ax^t))_{S^t})\|_2^2} $$

If $\eta^t > 0.99 \|x^t - x^{t+1}\|_2^2 / \|A(x^t - x^{t+1})\|_2^2$, $\eta^t$ is halved until this inequality becomes unsatisfied, as explained in [25].

We consider the same experiment as in Section 5.2 for NIHT, IHT, and HTP with different step sizes. Again, we set $n = 500$ and use a convolution matrix A corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different k-sparse $x^*$, with $k \in [1, 50]$. IHT and HTP were tested with a step size $\eta \in \{\frac{2}{L} | \text{ for } l = [-3, +3]\}$.

The analog of Figure 4 is depicted in Figure 30. For all considered step sizes, IHT and HTP cannot improve the solution provided by ELS and OMP when we consider the dist<sub>supp</sub> metric. We reach the same conclusion for NIHT. The ranking of HTP does not depend on the selected step size. The lowest dist<sub>supp</sub> is reached with a step size $\eta = \frac{8}{L}$. Increasing the step size further did not improve the results and made HTP diverge. IHT is more sensitive to step size variations than HTP. The lowest dist<sub>supp</sub> is reached with a step size $\eta = \frac{2}{L}$. Increasing the step size further made IHT diverge. The dynamic step size of NIHT made NIHT better than SEA<sub>OMP</sub> and SEA<sub>ELS</sub> for $k > 25$. However, IHT with $\eta = \frac{2}{L}$ becomes better than NIHT for $k > 36$. Thus, even by considering these variabilities, SEA<sub>0</sub> remains the best algorithm in this setting.

## E.11 Deconvolution: Random Search as a Pure Exploration Baseline.

A random search to recover the correct support could be used as a baseline to assess the performance of SEA. However, we discarded this option because the probability of recovery is too small. For instance, if we draw $r = 100000$ independent random supports from a uniform distribution, the probability of recovering the correct support of size $k = 20$ in a signal of size $n = 500$ is $1 - \left(1 - \frac{1}{\binom{n}{k}}\right)^r \sim 3.75 \times 10^{-31}$.

To establish a lower bound on support recovery performance, we conducted a random search for a number of supports equal to the maximal number of iterations (1000). The obtained results in this context were significantly inferior to any other tested algorithm.
<figure><img src="image_31.png" /><figcaption>Figure 28: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level k when y = A(x* + e) with e uniformly drawn from the sphere of radius 0.1||x*||<sub>2</sub>.</figcaption></figure>

<figure><img src="image_32.png" /><figcaption>Figure 29: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level k when the non-zero entries of x* are drawn uniformly in [-10, -1] ∪ [1, 10].</figcaption></figure>

## E.10 Deconvolution: Step Size of IHT and HTP

In Section 5, we arbitrarily fixed the step size $\eta = \frac{1.8}{L}$ where L is the spectral radius of A. In this section, we study the influence of the step size on HTP and IHT. We also consider the Normalized Iterative Thresholding (NIHT) [9] algorithm which is based on IHT but includes an adaptive step size $\eta^t$ which depends on the iteration $t$. The step size is chosen as:

$$ \eta^t = \frac{\|(A^T(y - Ax^t))_{S^t}\|_2^2}{\|A((A^T(y - Ax^t))_{S^t})\|_2^2} $$

If $\eta^t > 0.99\|x^t - x^{t+1}\|_2^2/\|A(x^t - x^{t+1})\|_2^2$, $\eta^t$ is halved until this inequality becomes unsatisfied, as explained in [25].

We consider the same experiment as in Section 5.2 for NIHT, IHT, and HTP with different step sizes. Again, we set $n = 500$ and use a convolution matrix A corresponding to a Gaussian filter with a standard deviation of 3. Every algorithm is tested on $r = 200$ noisy problems, for different k-sparse $x^*$, with $k \in [1, 50]$. IHT and HTP were tested with a step size $\eta \in \{\frac{2}{L} | \text{ for } l = [-3, +3]\}$.

The analog of Figure 4 is depicted in Figure 30. For all considered step sizes, IHT and HTP cannot improve the solution provided by ELS and OMP when we consider the dist<sub>supp</sub> metric. We reach the same conclusion for NIHT. The ranking of HTP does not depend on the selected step size. The lowest dist<sub>supp</sub> is reached with a step size $\eta = \frac{8}{L}$. Increasing the step size further did not improve the results and made HTP diverge. IHT is more sensitive to step size variations than HTP. The lowest dist<sub>supp</sub> is reached with a step size $\eta = \frac{2}{L}$. Increasing the step size further made IHT diverge. The dynamic step size of NIHT made NIHT better than SEA<sub>OMP</sub> and SEA<sub>ELS</sub> for $k > 25$. However, IHT with $\eta = \frac{2}{L}$ becomes better than NIHT for $k > 36$. Thus, even by considering these variabilities, SEA<sub>0</sub> remains the best algorithm in this setting.

## E.11 Deconvolution: Random Search as a Pure Exploration Baseline.

A random search to recover the correct support could be used as a baseline to assess the performance of SEA. However, we discarded this option because the probability of recovery is too small. For instance, if we draw $r = 100000$ independent random supports from a uniform distribution, the probability of recovering the correct support of size $k = 20$ in a signal of size $n = 500$ is $1 - \left(1 - \frac{1}{\binom{n}{k}}\right)^r \sim 3.75 \times 10^{-31}$.

To establish a lower bound on support recovery performance, we conducted a random search for a number of supports equal to the maximal number of iterations (1000). The obtained results in this context were significantly inferior to any other tested algorithm.
<figure><img src="image_34.png" /><figcaption>Figure 30: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level *k* with different step size values for IHT and HTP. The area between the highest and the lowest curve for different step sizes is displayed in blue and red for IHT and HTP. NIHT<sub>OMP</sub> and IHT<sub>OMP</sub> are superimposed. NIHT<sub>ELS</sub> and IHT<sub>ELS</sub> are superimposed.</figcaption></figure>
<figure><img src="image_33.png" /><figcaption>Figure 30: Mean of support distance dist<sub>supp</sub> (defined in (8)) between S* and the support of the solutions provided by several algorithms as a function of the sparsity level *k* with different step size values for IHT and HTP. The area between the highest and the lowest curve for different step sizes is displayed in blue and red for IHT and HTP. NIHT<sub>OMP</sub> and IHT<sub>OMP</sub> are superimposed. NIHT<sub>ELS</sub> and IHT<sub>ELS</sub> are superimposed.</figcaption></figure>
# F Supervised Machine Learning Experiments

We describe here supervised learning experiments: they confirm that SEA₀ performs well in small dimensions, and performs better in high dimensions when combined with OMP or ELS. They also give evidence that SEA can perform very well in the presence of error/noise and when no perfect sparse vector fits the data.

## F.1 Context

In a supervised learning setting, the rows of matrix $A \in \mathbb{R}^{m \times n}$ (often denoted by $X$) are the $n$-dimensional feature vectors associated with the $m$ training examples, while the related labels are in vector $y \in \mathbb{R}^m$. In the training phase, a sparse vector $x$ (often denoted $\beta$ or $w$) is optimized to fit $y \approx Ax$ using an appropriate loss function. In this context, support recovery is called model selection.

Based on the experimental setup of [2], we compare the training loss for different levels of sparsity, for all the algorithms, on linear regression and logistic regression tasks. We use the preprocessed public datasets<fnref n="10" /> provided by [2], following the same preprocessing pipeline: we augment $A$ with an extra column equal to 1 to allow a bias and normalize the columns of $A$.

We present results for regression problems in Appendix F.2 and for classification problems in Appendix F.3.

## F.2 Regression Datasets

As we are working with real datasets without ground truth, we use the $l_2$ regression loss $l_2\_loss(x) = \frac{1}{2}\|Ax - y\|_2^2$ for $x \in \mathbb{R}^n$ for regression problems.

As shown in Figure 31, SEA₀, SEAOMP and SEELS are at the same level as ELS on a regression dataset with *n* small as in *comp-activ-harder*. For the higher dimensional regression dataset as *year* (see Figure 32), SEA₀ performs poorly as *k* increases, but SEELS can improve ELS performances and outperforms the other algorithms.

<figure><img src="image_35.png" /><figcaption>Figure 31: Performance on regression dataset *comp-activ-harder* (*m* = 8191 examples, *n* = 12 features).</figcaption></figure>

In a low-dimensional problem (*n* is small) as *cal_housing* dataset (*m* = 20639 examples, *n* = 8 features) in Figure 33, we see that SEAOMP and SEELS perform better than ELS, and SEA₀ outperform them for a sparsity *k* ∈ [5, 8]. It is worth mentioning that HTP obtains good performances for this dataset.

The same experiment is reported on Figure 34, but for the dataset *slice* (*m* = 53500 examples, *n* = 384 features). This is an intermediate-dimensional problem. Figure 34 shows that SEA₀ obtains slightly worse results than SEELS, SEAOMP and ELS. The non-decreasing curve of HTP comes from its support estimation technique. Since the coherence of the *slice* dataset is 1, HTP selects highly correlated features and fails to correct this mistake.

<footnote n="10">¹⁰https://drive.google.com/file/d/1RDu2d46qGLI77AzliBQleSsB5WwF83TF/view</footnote>
# F Supervised Machine Learning Experiments

We describe here supervised learning experiments: they confirm that SEA₀ performs well in small dimensions, and performs better in high dimensions when combined with OMP or ELS. They also give evidence that SEA can perform very well in the presence of error/noise and when no perfect sparse vector fits the data.

## F.1 Context

In a supervised learning setting, the rows of matrix $A \in \mathbb{R}^{m \times n}$ (often denoted by $X$) are the $n$-dimensional feature vectors associated with the $m$ training examples, while the related labels are in vector $y \in \mathbb{R}^m$. In the training phase, a sparse vector $x$ (often denoted $\beta$ or $w$) is optimized to fit $y \approx Ax$ using an appropriate loss function. In this context, support recovery is called model selection.

Based on the experimental setup of [2], we compare the training loss for different levels of sparsity, for all the algorithms, on linear regression and logistic regression tasks. We use the preprocessed public datasets<fnref n="10" /> provided by [2], following the same preprocessing pipeline: we augment $A$ with an extra column equal to 1 to allow a bias and normalize the columns of $A$.

We present results for regression problems in Appendix F.2 and for classification problems in Appendix F.3.

## F.2 Regression Datasets

As we are working with real datasets without ground truth, we use the $l_2$ regression loss $l_2\_loss(x) = \frac{1}{2}\|Ax - y\|_2^2$ for $x \in \mathbb{R}^n$ for regression problems.

As shown in Figure 31, SEA₀, SEAOMP and SEELS are at the same level as ELS on a regression dataset with *n* small as in *comp-activ-harder*. For the higher dimensional regression dataset as *year* (see Figure 32), SEA₀ performs poorly as *k* increases, but SEELS can improve ELS performances and outperforms the other algorithms.

<figure><img src="image_34.png" /><figcaption>Figure 31: Performance on regression dataset *comp-activ-harder* (*m* = 8191 examples, *n* = 12 features).</figcaption></figure>

In a low-dimensional problem (*n* is small) as *cal_housing* dataset (*m* = 20639 examples, *n* = 8 features) in Figure 33, we see that SEAOMP and SEELS perform better than ELS, and SEA₀ outperform them for a sparsity *k* ∈ [5, 8]. It is worth mentioning that HTP obtains good performances for this dataset.

The same experiment is reported on Figure 34, but for the dataset *slice* (*m* = 53500 examples, *n* = 384 features). This is an intermediate-dimensional problem. Figure 34 shows that SEA₀ obtains slightly worse results than SEELS, SEAOMP and ELS. The non-decreasing curve of HTP comes from its support estimation technique. Since the coherence of the *slice* dataset is 1, HTP selects highly correlated features and fails to correct this mistake.

<footnote n="10">¹⁰https://drive.google.com/file/d/1RDu2d46qGLI77AzliBQleSsB5WwF83TF/view</footnote>
<figure><img src="image_36.png" /><figcaption>Figure 32: Performance on regression dataset year (m = 463715 examples, n = 90 features).</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>Figure 33: Performance on the regression dataset cal_housing (m = 20639 examples, n = 8 features).</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>Figure 34: Performance on the regression dataset slice (m = 53500 examples, n = 384 features).</figcaption></figure>
<figure><img src="image_35.png" /><figcaption>Figure 32: Performance on regression dataset year (m = 463715 examples, n = 90 features).</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>Figure 33: Performance on the regression dataset cal_housing (m = 20639 examples, n = 8 features).</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>Figure 34: Performance on the regression dataset slice (m = 53500 examples, n = 384 features).</figcaption></figure>
## F.3 Classification Datasets

In these experiments, we consider the logistic regression loss defined by

$$ \log\text{loss}(x) = \sum_{i=1}^{m} (-y_i \log(\sigma((Ax)_i)) - (1 - y_i) \log(1 - \sigma((Ax)_i))), $$

where $\sigma(t) = \frac{1}{1+e^{-t}}$ is the sigmoid function.

We need to adapt SEA to this new loss. In Algorithm 1, line 7 is replaced by $x^t = \underset{\substack{x \in \mathbb{R}^n \\ \text{supp}(x) \subseteq S^t}}{\text{argmin}} \log\text{loss}(x)$ and line 8 is replaced by $\mathcal{X}^{t+1} = \mathcal{X}^t - \eta \nabla \log\text{loss}(x^t)$. Similar adaptations are performed on the other algorithms.

The loss $\log\text{loss}(x)$, for the letter dataset ($m = 20000$ examples, $n = 16$ features), for all $k \in [1, 12]$ and for all algorithms is depicted in Figure 35. We depict the same curves obtained for the ijcnn1 dataset ($m = 24995$ examples, $n = 22$ features) in Figure 36. These two last figures show that $\text{SEA}_{\text{OMP}}$ and $\text{SEA}_{\text{ELS}}$ achieve similar performances to ELS.

<figure><img src="image_39.png" /><figcaption>Figure 35: Performance on the classification dataset letter ($m = 20000$ examples, $n = 16$ features).</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>Figure 36: Performance on the classification dataset ijcnn1 ($m = 24995$ examples, $n = 22$ features).</figcaption></figure>
## F.3 Classification Datasets

In these experiments, we consider the logistic regression loss defined by

$$ \log\text{loss}(x) = \sum_{i=1}^{m} (-y_i \log(\sigma((Ax)_i)) - (1 - y_i) \log(1 - \sigma((Ax)_i))), $$

where $\sigma(t) = \frac{1}{1+e^{-t}}$ is the sigmoid function.

We need to adapt SEA to this new loss. In Algorithm 1, line 7 is replaced by $x^t = \underset{\substack{x \in \mathbb{R}^n \\ \text{supp}(x) \subseteq S^t}}{\operatorname{argmin}} \log\text{loss}(x)$ and line 8 is replaced by $\mathcal{X}^{t+1} = \mathcal{X}^t - \eta \nabla \log\text{loss}(x^t)$. Similar adaptations are performed on the other algorithms.

The loss $\log\text{loss}(x)$, for the letter dataset ($m = 20000$ examples, $n = 16$ features), for all $k \in [1, 12]$ and for all algorithms is depicted in Figure 35. We depict the same curves obtained for the ijcnn1 dataset ($m = 24995$ examples, $n = 22$ features) in Figure 36. These two last figures show that $\text{SEA}_{\text{OMP}}$ and $\text{SEA}_{\text{ELS}}$ achieve similar performances to ELS.

<figure><img src="image_38.png" /><figcaption>Figure 35: Performance on the classification dataset letter ($m = 20000$ examples, $n = 16$ features).</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>Figure 36: Performance on the classification dataset ijcnn1 ($m = 24995$ examples, $n = 22$ features).</figcaption></figure>