\section{Main results}
\label{sec:main_results}

In this section, we derive recovery guarantees for  \eqref{pb:BP} and \eqref{pb:qBP} under a random sign assumption on the signal . They \replace{lead to lower bounds}{reveal sufficient conditions} on the required number of measurements, provided that one can evaluate $\Theta$, $\Lambda$, and $\Gamma$ defined in Section~\ref{sec:assumptions}.


\paragraph{Overview of the main results} 
Throughout the section, our benchmark will be an oracle-type inequality discussed in Section~\ref{sec:oracle}, namely 
\begin{equation}
\label{eq:oracle_simple}
m \gtrsim \Lambda(S,F) \cdot \ln(|S|/\varepsilon),
\end{equation}
which is proved to be sufficient for the robust recovery of an $S$-sparse via oracle-least squares with probability at least $1-\varepsilon$ in Proposition~\ref{prop:oracle}. We will refer to \eqref{eq:oracle_simple} as an \emph{oracle-type} inequality. Notice that  the oracle-least squares estimator requires an \emph{a priori} knowledge of $S$ to recover the signal, whereas the \eqref{pb:BP} and \eqref{pb:qBP} programs do not. 

In Sections~\ref{sec:noiseless} and \ref{sec:robustness} we make a first step towards oracle-type inequalities for CS. In particular, we show that 
\begin{equation}
\label{eq:Theta_bound_simple}
m \gtrsim \Theta(S,F) \cdot \ln^2(n/\varepsilon),
\end{equation}
is sufficient for the exact recovery from noiseless measurements (Theorem~\ref{thm:noiseless}) or robust recovery from noisy measurements (Theorem~\ref{thm:noisy}) of a signal supported on $S$ with probability at least $1-\varepsilon$. Note that, besides the additional logarithmic factor, \eqref{eq:Theta_bound_simple} is not necessarily an oracle-type inequality, in view of \eqref{eq:lambda_theta}. 

\replace{We provide oracle-type inequalities for CS in Section~\ref{sec:oracle-type}}{We progressively improve bounds on $m$ for CS recovery via \eqref{pb:BP} and \eqref{pb:qBP}}  in Section~\ref{sec:oracle-type}, presenting three results \replace{in this direction}{towards oracle-type inequalities}. Theorem~\ref{thm:oracle_theta} \replace{provides}{requires} \replace{an inequality for CS}{a bound} of the form 
$$
m \gtrsim \max_{j \in S^c}\Lambda(S \cup \{j\},F) \cdot \ln^2(n/\varepsilon),
$$ 
which is of oracle type up to enlarging the support by one element.
Theorems~\ref{thm:killthetheta} and \ref{thm:killthetalog} achieve oracle-type \replace{inequalities}{requirements on $m$} at the price of an extra assumption involving $\Lambda(S,F)$ and $\Gamma(F)$. They  only differ by a logarithmic factor. In particular, in Theorem~\ref{thm:killthetheta} robust recovery from noisy measurements (or exact recovery from noiseless measurement) is guaranteed with probability $1-\varepsilon$ if
$$
m \gtrsim \Lambda(S,F) \cdot \ln^2(n/\varepsilon),
$$
and provided that $\Lambda(S,F) \gtrsim \Gamma(F)$. Theorem~\ref{thm:killthetalog} achieves the same recovery guarantees if
$$
m \gtrsim \Lambda(S,F) \cdot \ln(n/\varepsilon), 
$$
and under the extra assumption $\Lambda(S,F) \gtrsim \Gamma(F) \ln(n/\varepsilon)$. These extra assumptions do not turn out to be restrictive in practice (see Section~\ref{sec:appli}). \replace{}{Finally, we note that the assumptions of Theorem~\ref{thm:oracle_theta}, \ref{thm:killthetheta}, and \ref{thm:killthetalog} are sufficient to guarantee stable and robust recovery from noisy measurements for both \eqref{pb:qBP} and the oracle least-squares estimator (see Remark~\ref{rem:stability}).}


\subsection{Preliminary: an oracle inequality}
\label{sec:oracle}

In this section, we derive a lower bound on the number of measurements sufficient to obtain robust recovery using an oracle least-squares estimator.


\begin{prop} 
\label{prop:oracle}
Let \replace{$x\in \Cbb^n$}{$x\in \Rbb^n$ or $\Cbb^n$} be a vector  supported on a set $S$ of size $s$ and suppose we are given noisy measurements $y = Ax + \epsilon$, with $\|\epsilon\|_2 \leq \eta$. Then, there exist universal constants $c_0,C_0 >0$ such that, for every $0 < \varepsilon < 1$ and provided
\begin{align}
\label{eq:bound_meas_oracle}
m \geq c_0 \cdot \Lambda(S,F) \cdot \ln \left( \frac{2s}{\varepsilon} \right),
\end{align} 
the following holds with probability at least $1-\varepsilon$:  the matrix $A_S$ has full column rank and the oracle-least squares estimator $x^\star \in\Cbb^n$ of the system $ y = A z$, defined by
\begin{equation}
\label{eq:oracle_ls_estimator}
x^\star_S = (A_S)^\dagger y, \quad x_{S^c}^\star = 0.
\end{equation} 
satisfies the error estimate
\begin{align}
\label{eq:oracle_robustness}
\| x - x^\star \|_2 \leq C_0 \eta.
\end{align} 
Possible values for the constants are $C_0 = \sqrt{2}$ and $c_0=32/3$.
\end{prop}
\begin{proof}
Recalling the definition \eqref{eq:oracle_ls_estimator} of $x^\star$ and the fact that both $x$ and $x^\star$ are supported on $S$, one has
\begin{align*}
\| x^\star - x \|_2   
&=   \| (A_S)^\dagger y - x_{S} \|_2 
= \| (A_S)^\dagger (Ax+\epsilon) - x_{S} \|_2  
= \| (A_S)^\dagger \epsilon + (A_S)^\dagger A_{S^c} x_{S^c} \|_2 \\
& \leq \| A_S^\dagger \|_{2\to 2} \| \epsilon\|_2 + \| (A_S^* A_S)^{-1} \|_{2\to 2} \| A_S^* A_{S^c} \|_{1\to 2} \| x_{S^c} \|_1 
\\
&\leq \frac{1}{\sigma_{\min}(A_S)}  \| \epsilon \|_2 +  \| (A_S^* A_S)^{-1} \|_{2\to 2} \| A_S^* A_{S^c} \|_{1\to 2} \| x_{S^c} \|_1 .
\end{align*}
If $\|A_S^* A_S - P_S \|_{2\to 2} \leq \delta$, then $\sigma_{\min}(A_S) \geq \sqrt{1-\delta}$ and $\| (A_S^* A_S)^{-1} \|_{2\to 2}\leq \frac{1}{1-\delta}$. Using Lemma \ref{lem:localIsometry_ext}, if 
$$
m \geq \frac{1+2 \delta/3}{\delta^2/2} \cdot \Lambda (S,F) \cdot \ln \left( \frac{2s}{\varepsilon} \right),
$$   
then $\| A_S^* A_S -P_S \|_{2\to 2} \leq \delta$. Considering that $\| x_{S^c} \|_1 =0$ and fixing $\delta=1/2$ leads to the desired result with the specified constants. 


\end{proof}

\begin{remark} \normalfont
In the following, we are going to derive ``oracle-type" estimate for signal recovery via \eqref{pb:BP} and \eqref{pb:qBP}. In this paper, ``oracle-type" estimates will refer to the bound on the number of measurements, i.e.\ bounds of the form \eqref{eq:bound_meas_oracle}. They will not concern the robustness bound obtained in \eqref{eq:oracle_robustness}, \replace{that}{which} we will \replace{comment}{discuss} later.
\end{remark}


\replace{}{Proposition~\ref{prop:oracle} implies robust recovery of sparse vectors when measurements are corrupted with bounded noise. In fact, it is also possible to prove the stability of the oracle least-squares estimator with respect to the standard sparsity model by considering a condition on $m$ slightly stronger than \eqref{eq:bound_meas_oracle}. For the sake of readability, in the following results we will bypass this additional technical difficulty by focusing only robust sparse recovery. For a more extended discussion on stability, we refer to Remark~\ref{rem:stability}.}


\subsection{Noiseless recovery}
\label{sec:noiseless}


Our main result for the success of \eqref{pb:BP} with an abstract block-structured framework presented in Section \ref{subsec:sampling} is the following. 
\begin{thm}
\label{thm:noiseless}
Let $x\in \Rbb^n$ or $\Cbb^n$ be a vector supported on $S$, such that $\sgn(x_S)$ forms a Rademacher or Steinhaus sequence. Let $A$ be the random sensing matrix defined in \eqref{eq:sensing_matrix} associated with parameter $\Theta(S,F)$. Suppose we are given the data $y=Ax$. Then, given $0<\varepsilon < 1$ and provided
$$
m \geq c_1 \cdot  \Theta (S,F) \cdot \ln^2\left( \frac{6n}{\varepsilon} \right),
$$ 
for $c_1$ a numerical constant (for instance $c_1=\replacemath{51}{82}$), the vector $x$ is the unique minimizer of the basis pursuit program \eqref{pb:BP} with probability at least $1-\varepsilon$.
\end{thm}

The proof is given in Appendix \ref{proof:noiseless}.

\begin{remark} \normalfont
In standard CS, the number of measurements usually depends on the degree of sparsity $s$ (such that $|S|\leq s$) on the one hand and on the sampling coherence on the other hand. Here, the quantity $\Theta(S,F)$ is encapsulating both information. This way, the use of coherent transforms is not prohibited anymore as soon as the support structure is adapted to it. Note that in the case of isolated measurements 	{described in Section~\ref{subsec:sampling}-(ii)}, the quantity $\Theta(S,F)$ can be bounded from above as follows, leading to the standard CS-type estimate:
$$
\Theta(S,F) \leq s\cdot \sup_{a\sim F} \| a \|_\infty^2.
$$
However, we observe that this upper bound is too crude in general, except under the following assumptions:
\begin{itemize}
\item  there is no structure in the signal sparsity, meaning that the only prior on $S$ is that $|S|=s$;
\item the sensing matrix $A$ is totally incoherent, meaning  that all the entries of $A$ have the same magnitude, $\forall (i,j),  |A_{ij}| = \| A \|_{1\to \infty} =1$ (this for instance the case of subsampled Fourier matrix). 
\end{itemize}
\end{remark}

\begin{remark} \normalfont
The bound on the number of measurements in Theorem \ref{thm:noiseless} depends only on one quantity, namely $\Theta(S,F)$, {which, in turn,} depends on the signal support and on the way of drawing blocks. On the contrary, in \cite{boyer2017compressed,chun2017compressed}, the authors derived similar results with a bound on $m$ depending on the maximum between two quantities (one of them corresponding to $\Theta(S,F)$ in this paper). However, the authors \cite{boyer2017compressed,chun2017compressed} have not considered the random sign assumption. The latter was useful to obtain a closed-form expression for the ``coherence" $\Theta(S,F)$. We will see that this is \replace{a}{} key to design optimal drawing strategies in Section \ref{sec:optimal_drawing}.
\end{remark}


\subsection{Robustness}
\label{sec:robustness}


Theoretical guarantees can \replace{be also}{also be} obtained when the observation vector $y$ is corrupted by noise.
\begin{thm}
\label{thm:noisy}
Let \replace{$x\in \Cbb^n$}{$x\in \Rbb^n$ or $\Cbb^n$} be a vector supported on $S$, such that $\sgn(x_S)$ forms a Rademacher or Steinhaus sequence and $|S|=s$. Let $A$ be the random sensing matrix defined in \eqref{eq:sensing_matrix} with parameter $\Theta(S,F)$. Suppose that the data $y$ is given such that $y=Ax+\epsilon$ with $\|\epsilon\|_2\leq \eta$ for some given $\eta>0$.  Then, given $0<\varepsilon < 1$ and provided
$$
m \geq c_1 \cdot  \Theta (S,F) \cdot \ln^2\left( \frac{6n}{\varepsilon} \right),
$$ 
for $c_1$ a numerical constant (for instance $c_1=\replacemath{780}{889}$), a minimizer $x^\sharp$ of \eqref{pb:qBP} satisfies
\begin{align}
\label{eq:noisy_rec}
\|x-x^\sharp\|_2 \leq  (C_1 + C_2\sqrt{s})\eta,
\end{align}
{with probability at least $1-\varepsilon$, where} $C_1,C_2$ are numerical constants.
\end{thm}


The proof of Theorem~\ref{thm:noisy} is given in Appendix \ref{proof:noisy}.

\begin{remark}
\label{rmrk:finer_error_bound}
\normalfont
The proof of Theorem~\ref{thm:noisy} reveals a more precise recovery guarantee, which \replace{takes}{} accounts for the stability with respect to the standard sparsity model. Namely, it is possible to generalize the theorem to the case \replace{$x \in \Cbb^n$}{$x \in \Rbb^n$ or $\Cbb^n$} where $S$ is \replace{the}{a} set of \replace{}{indices corresponding to the} $s$ large\replace{}{st} absolute entries of $x$ \replace{}{(or, more in general, any subset of $s$ indices)}. Under the same conditions as in Theorem~\ref{thm:noisy}, then, with high probability, one has
\begin{align}
\label{eq:noisy_stable_rec}
\|x-x^\sharp\|_2 \leq (C_1 + C_2\sqrt{s})\eta +  C_3 \|x-x_S\|_1.
\end{align}


This matches the bound derived in the standard setting of CS, see for instance \cite[Theorem 12.22]{foucart2013mathematical}, which may seem a bit disappointing. However, to our knowledge, this is the first result of stability and robustness derived in the case of the random sign assumption. 
\end{remark}


\noindent\textbf{How much are we off the oracle estimate of Proposition \ref{prop:oracle}?} Regarding the  number of measurements {$m$}, the \replace{bounds}{conditions} required by Theorems \ref{thm:noiseless} and \ref{thm:noisy} depend on $\Theta (S, F)$, instead of $\Lambda (S, F)$ as in Proposition \ref{prop:oracle}. Therefore, by \eqref{eq:lambda_theta}, we only obtained an upper bound to the oracle estimate.

Regarding the error bound \eqref{eq:noisy_rec}, one can notice that the noise level $\eta$ is amplified by an additional factor $\sqrt{s}$, when compared to \eqref{eq:oracle_robustness}. Nonuniform approaches {are known to} suffer from this extra $\sqrt{s}${-factor} in the robustness bound, see for instance  \cite[Theorem 12.22]{foucart2013mathematical}, although this may be an artifact of the proof strategies employed so far. To the best our knowledge, the only better bound of the form $c \cdot \eta$ for $c$ some constant has been obtained in \cite[Proposition 2.6]{tropp2015convex}. However, such a bound can be obtained so far only for Gaussian measurements since they are based on the control of the minimum conic singular value of the sensing matrix. \replace{To control}{Controlling} the statistical dimension of \replace{}{the} descent cone for structured measurements still remains an open question. That is why in the sequel we will leave aside the question of improving the robustness bound of a $\sqrt{s}$-factor and we will focus on deriving oracle-type bounds in terms of number of measurements.
{"config": "arxiv", "file": "1806.03789/src/main_random_signs.tex"}