\section{Deriving an optimal sampling strategy}
\label{sec:optimal_drawing}

The purpose of this section is to employ the results in Section~\ref{sec:main_results} to derive optimal sampling strategies within the framework of block-\replace{type}{structured} sampling and isolated measurements from a finite-dimensional isometry illustrated in Section~\ref{subsec:sampling}.
\replace{}{Indeed, the bounds on $m$ just presented in Section \ref{sec:main_results} have the remarkable feature to be the first ones in CS with generalized structured sampling, depending only on one quantity, namely either $\Theta$ or $\Lambda$. This is the key to derive theoretical optimal sampling strategies: minimizing such bounds on $m$ with respect to the sampling distribution, leads to the first theoretical closed form for the sampling probabilities when using structured blocks of measurements.}
 All the proofs are presented in Appendix \ref{app:proof_proba}. 


\label{subsec:opt_proba}


The case of block-structured sampling strategy was introduced in \cite{boyer2017compressed} and adapted to parallel acquisition in \cite{chun2017compressed}, where variable density sampling with structured acquisition was considered. However, based on the analysis proposed in these works, minimizing the bound on the number of measurements with respect to $\pi$ is not trivial and no closed form for $\pi$ could be analytically given in general. In the following, Propositions \ref{prop_opt_drawing_proba} and \ref{prop_opt_drawing_proba_lambda} are the first theoretical results  in CS on an optimal way to perform structured acquisition while taking into account partially coherent transforms and structured sparsity.


We start by deriving optimal sampling strategies from Theorems \ref{thm:noiseless} and \ref{thm:noisy} in the finite setting described in 	Section \ref{subsec:sampling}~\ref{block_finite_setting}.

\begin{prop}
\label{prop_opt_drawing_proba}
In a finite setting where we sample blocks in a partitioned isometry as in Section~\ref{subsec:sampling}~\ref{block_finite_setting}, Equation \eqref{eq:bos_sensing_matrix}, the drawing probability minimizing $\Theta(S,\pi)$ is the following:
\begin{align}
\label{eq:opt_drawing_proba}
\forall k \in \{1,\hdots , M \}, \quad \pi_k = \pi_k^\Theta =  \frac{\| D_k^* D_{k,S} \|_{\infty \to \infty}}{\sum_{\ell=1}^M \| D_\ell^* D_{\ell,S} \|_{\infty \to \infty}}.
\end{align}
With such a choice for $\pi$, the required number $m$ of blocks of measurements in Theorems \ref{thm:noiseless} and \ref{thm:noisy} can be then rewritten as follows:
\begin{align}
m \geq c \cdot \sum_{\ell=1}^M \| D_\ell^* D_{\ell,S} \|_{\infty \to \infty} \cdot  \ln^2(6n/\varepsilon),
\end{align}
for a suitable universal constant $c >0$. These conditions ensure noiseless recovery via \eqref{pb:BP}, or stable and robust recovery via \eqref{pb:qBP}, with probability at least $1-\varepsilon$.
\end{prop} 

At the price of the extra assumption, as \eqref{cond:killthetheta} or \eqref{cond:killthethetalog} on $\Lambda{(S,\pi)}$ and $\Gamma{(\pi)}$ in Theorems \ref{thm:killthetheta} or \ref{thm:killthetalog}, one could choose a drawing probability minimizing $\Lambda{(S,\pi)}$ instead of $\Theta{(S,\pi)}$. This is the purpose of the following results, corresponding to the case of block-structured and isolated measurements, respectively. For the sake of simplicity, we just illustrate the derivation from Theorem~\ref{thm:killthetalog}.


\begin{prop}
\label{prop_opt_drawing_proba_lambda}
In a finite setting where we sample blocks in a partitioned isometry as in Section \ref{subsec:sampling} \ref{block_finite_setting}, Equation \eqref{eq:bos_sensing_matrix}, 
assume that $|S|\leq n/2$ and that
\begin{equation}
\label{eq:extra_hyp_1}
1\geq c_1 \cdot \max_{1\leq k \leq M} \frac{\|D_k \|_{1\rightarrow 2}^2}{\| D_{k,S}^* D_{k,S} \|_{2\rightarrow 2}} \ln(3 n/\varepsilon),
\end{equation}
for $c_1$ a universal constant.
Then the optimal drawing probability minimizing $\Lambda(S,\pi)$ is 
\begin{align}
\label{eq:opt_drawing_proba_lambda}
\forall k \in \{1,\hdots , M \}, \quad \pi_k =  \pi_k^\Lambda = \frac{\| D_{k,S}^* D_{k,S} \|_{2 \to 2}}{\sum_{\ell=1}^M \| D_{\ell,S}^* D_{\ell,S} \|_{2 \to 2}}.
\end{align}
With such a choice for $\pi$, the required number $m$ of blocks of measurements in Theorem \ref{thm:killthetalog} can be then rewritten as follows:
\begin{align}
m \geq c_{2} \cdot \sum_{\ell=1}^M \| D_{\ell,S}^* D_{\ell,S} \|_{2 \to 2} \cdot  \ln(6n/\varepsilon),
\end{align}
for a suitable universal constant $c_2 >0$. These conditions ensure noiseless recovery via \eqref{pb:BP}, or stable and robust recovery via \eqref{pb:qBP}, with probability at least $1-\varepsilon$.
\end{prop} 


In the following, we specialize the previous result to the case of isolated measurements subsampled from an isometry, described in Section \ref{subsec:sampling} \ref{iso_finite_setting}.

\begin{prop}
\label{prop_opt_proba_iso}
In a finite setting where we sample isolated measurements as in Section~\ref{subsec:sampling}~\ref{iso_finite_setting}, Equation \eqref{eq:bos_iso_sensing_matrix}, the drawing probability minimizing $\Theta(S,\pi)$ is the following:
\begin{align}
\label{eq:opt_drawing_proba_iso}
\forall k \in \{1,\hdots , n \}, \quad \pi_k =  \pi_k^\Theta = \frac{\| \replacemath{a}{d}_k \|_\infty \| \replacemath{a}{d}_{k,S} \|_1}{\sum_{\ell=1}^n \| \replacemath{a}{d}_\ell \|_\infty \| \replacemath{a}{d}_{\ell,S} \|_1}.
\end{align}
With such a choice for $\pi$, the required number $m$ of measurements in Theorems \ref{thm:noiseless} and \ref{thm:noisy} can be then rewritten as follows:
\begin{align}
\label{eq:m_bound_iso}
m \geq c \cdot \sum_{\ell=1}^n \| \replacemath{a}{d}_\ell \|_\infty \| \replacemath{a}{d}_{\ell,S} \|_1 \cdot  \ln^2(6n/\varepsilon),
\end{align}
for a suitable universal constant $c >0$. These conditions ensure noiseless recovery via \eqref{pb:BP}, or stable and robust recovery via \eqref{pb:qBP}, with probability at least $1-\varepsilon$.
\end{prop}


Let us put the previous result into context. Variable density strategies were introduced to deal with partially coherent transforms  (such as in the case of MRI) \cite{krahmer2014stable,chauffert2014variable,puy2011variable}. The idea is to sample the more coherent atoms $(\replacemath{a}{d}_k)_{k}$ {with higher probability} by setting for all $k\in \{1,\hdots , n\}$
\begin{equation}
\label{eq:variabledensity}
\pi_k = \frac{\|\replacemath{a}{d}_k \|_\infty^2}{\sum_{\ell=1}^n \| \replacemath{a}{d}_\ell\|_\infty^2},
\end{equation}
meaning that we tend to sample more where the sampling transform is coherent.
With such a choice, one can ensure robust recovery with probability $1-\varepsilon$ with a number of measurements of the order
\begin{equation*}
m \gtrsim s \cdot \sum_{\ell=1}^n \| \replacemath{a}{d}_\ell\|_\infty^2 \cdot \ln \left( n / \varepsilon \right).
\end{equation*}
For instance in the case of MRI, $\sum_{\ell=1}^n \| \replacemath{a}{d}_\ell\|_\infty^2 = O(\ln(n))$, making bounds on $m$ more realistic than those based on the global coherence $n \max_k \|\replacemath{a}{d}_k\|_\infty^2 = O(n \ln(n))$. The sampling strategy defined by \eqref{eq:opt_drawing_proba_iso} refines \eqref{eq:variabledensity} since it takes into account a more accurate notion of local coherence, involving both the coherence of the individual atoms $(\replacemath{a}{d}_k)_k$ and its interaction with prior information about the support of the signal. In this way, the sampling strategy can be optimized to recover signals with structured sparsity, as discussed in Sections~\ref{sec:applications_mri_iso} and \ref{sec:application_MRI} for the case of sparsity in levels. Moreover, the explicit dependence of the sampling probability on the support in \eqref{eq:opt_drawing_proba_iso} enables us to devise iterative adaptive sampling strategies (see Section~\ref{sec:adaptive}).

Still in the case of isolated measurements, one can improve the previous proposition by deriving sampling strategies derived from oracle-type bounds on the number of measurements. 
The following result applies Theorem~\ref{thm:killthetalog} to the setting illustrated in Section~\ref{subsec:sampling}~\ref{iso_finite_setting}.

\begin{prop}
\label{prop_opt_drawing_proba_iso_lambda}
In a finite setting where we sample isolated measurements as in Section \ref{subsec:sampling} \ref{iso_finite_setting}, Equation \eqref{eq:bos_iso_sensing_matrix}, 
assume that {$|S|\leq n/2$ and that}
\begin{align}
\label{cond_to_kill_log_iso}
1\geq c_1 \cdot \max_{1\leq k \leq n} \frac{\|\replacemath{a}{d}_k \|_{\infty}^2}{\| \replacemath{a}{d}_{k,S} \|_{2}^2} \ln(3 n/\varepsilon),
\end{align}
for $c_1$ a universal constant.
Then the optimal drawing probability minimizing $\Lambda(S,\pi)$ is 
\begin{align}
\label{eq:opt_drawing_proba_lambda_iso}
\forall k \in \{1,\hdots , n \}, \quad \pi_k  =  \pi_k^\Lambda  = \frac{\| \replacemath{a}{d}_{k,S} \|_{2}^2}{\sum_{\ell=1}^n \| \replacemath{a}{d}_{\ell,S} \|_{2}^2}.
\end{align}
The required number $m$ of measurements in Theorem \ref{thm:killthetalog} can be then rewritten as follows:
\begin{align}
m \geq c_{2} \cdot \sum_{\ell=1}^n \| \replacemath{a}{d}_{\ell,S} \|_{2}^2 \cdot  \ln(6n/\varepsilon),
\end{align}
{for a suitable universal constant $c_2 >0$.} These conditions ensure noiseless recovery via \eqref{pb:BP}, or stable and robust recovery via \eqref{pb:qBP}, with probability at least $1-\varepsilon$.
\end{prop} 

Finally, one could resort to Theorem~\ref{thm:oracle_theta} in order to remove condition \eqref{cond_to_kill_log_iso}, at the price of overestimating the support size by one element and of an extra log factor.


\begin{prop}
\label{prop:drawing_proba_lambda_ext}
Let $x\in \Cbb^n$ be a vector supported on $S$, such that $|S|=s$ and $\sgn(x_S)$ forms a Rademacher or Steinhaus sequence. 
Let $A$ be the random sensing matrix defined in \eqref{eq:sensing_matrix} with parameter $\Lambda(S,F)$. If {$0 < \varepsilon < 1$ and}
$$
m \geq c_1 \cdot \max_{j \in S^c} \Lambda (S \cup \{j\},F)  \cdot \ln^{2}\left( \frac{6n}{\varepsilon} \right),
$$ 
with $c_1>0$ a numerical constant, then, with probability at least $1-\varepsilon$, noiseless recovery via \eqref{pb:BP} or stable and robust recovery via \eqref{pb:qBP} is ensured. 
The probability $\pi$ minimizing the previous bound on $m$ reads:
\begin{align}
\label{eq:opt_drawing_proba_lambda_iso_tilde}
\forall k \in \{1,\hdots , n \}, \quad \pi_k = \pi_k^{\tilde{\Lambda}} = \frac{\displaystyle\max_{j \in S^c}\| \replacemath{a}{d}_{k,S \cup \{j\}} \|_{2}^2}{\displaystyle\sum_{\ell=1}^n \max_{j \in S^c}\| \replacemath{a}{d}_{\ell,S \cup \{j\}} \|_{2}^2}.
\end{align}
With such a choice, the required number $m$ of measurements can be rewritten as follows:
$$
m \geq c_1 \cdot \sum_{\ell=1}^n \max_{j \in S^c}\| \replacemath{a}{d}_{\ell,S \cup \{j\}} \|_2^2 \cdot  \ln^{2}\left( \frac{6n}{\varepsilon} \right).
$$ 
\end{prop}
{"config": "arxiv", "file": "1806.03789/src/optimal_drawing_strategy.tex"}