\section{Examples and Illustrations}\label{sec:examples}

This section provides specific examples and illustrations of the upper bounds on the sampling rate distortion function $\rho(\alpha)$ given in Theorems \ref{thm:suf-gml}, \ref{thm:sufMC}, and \ref{thm:convex}.


\subsection{Bounds for a Gaussian Source}
To begin, we consider the setting where $F$ is the distribution of a zero-mean Gaussian random variable with variance $\sigma^2$. It is clear to see that the power of the source $\mathcal{X}(\Omega,F)$ is given by $P(\Omega,F) = \Omega\sigma^2$, and it can be shown (see Appendix D of \cite{RG-Lower-Bounds}) that the power corresponding to the $\beta$-truncated distribution $F_\beta$ is given by
\begin{align}\label{eq:PGaussian}
P(\Omega,F_\beta) =\left[1 -  (t_\beta / \beta) (2/\pi)^{1/2} \exp (-t_\beta^2/2) \right]  \Omega\, \sigma_F^2 
\end{align}
where 
$t_\beta =   Q^{-1}(\frac{1-\beta}{2})$ and $Q(\cdot)^{-1}$ denotes the functional inverse of $Q(x) = \int_x^\infty (2 \pi)^{-1/2} \exp(-x^2/2)dx$. 

Since the Gaussian distribution has decay rate $L=1$, we know that the power $P(\Omega,F_\beta)$ scales like $\beta^2$ for small $\beta$. Applying a Taylor expansion to the to \eqref{eq:PGaussian} gives the more precise characterization
\begin{align*}
\lim_{\beta \rw 0}\frac{1}{\beta^2} P(\Omega,F_\beta) = \frac{\pi}{6}\Omega.
\end{align*}


To illustrate our bounds on the sampling rate distortion function of this source, we first consider the special case where the sampling matrix is required to have i.i.d. elements. In Figure \ref{fig:f2}(a)-(b), the upper bounds on $\rho(\alpha)$ given in Theorems \ref{thm:suf-gml} and \ref{thm:sufMC} are shown as a function of $\alpha$ for two different SNRs. Since these bounds correspond to an i.i.d. Gaussian sampling matrix, they represent valid upper bounds for i.i.d. sampling matrices. Also shown is a lower bound (see \cite[Theorem 4]{RG-Lower-Bounds}) which applies universally to any estimator and i.i.d. sampling matrix. 

In the low SNR setting (Figure \ref{fig:f2}(a)) the best bound corresponds to the thresholding estimator, and in the high SNR setting (Figure \ref{fig:f2}(b)) the best bound corresponds to the nearest subspace estimator. Since our analysis of the thresholding estimator is exact (at least for the case of a Gaussian sampling matrix), these results indicate that the nearest subspace estimator is significantly better than the thresholding estimator at high SNR. However, since the upper bound on the nearest subspace estimator is not necessarily tight, it is not possible to say which estimator is better at low SNR. It is interesting to observe that in both cases, the bounds show that $\rho(\alpha)$ is relatively flat for nonzero distortions $\alpha$, but tend to infinity rapidly as $\alpha \rw 0$. This behavior shows why it is important to consider approximate recovery of the sparsity pattern. 

Next, we address what happens if there are no constraints on the sampling matrix (other than the normalization imposed by \eqref{eq:mtrx-scale}). In Figure \ref{fig:f3}(a)-(b), convex versions of the upper bound on $\rho(\alpha)$ given in Theorems \ref{thm:suf-gml} and \ref{thm:sufMC} corresponding to the rate-sharing strategy given in Theorem \ref{thm:convex} are shown as a function of $\alpha$ for two different SNRs. Also shown is a lower bound (see \cite[Theorem 3]{RG-Lower-Bounds}) which applies universally to any estimator and sampling matrix.

The basic behavior of the bounds in Figure \ref{fig:f3} is similar to that of the bounds for i.i.d. sampling matrices in Figure \ref{fig:f2}. For the upper bounds, the main difference between the two settings occurs at relatively large distortions. For the lower bounds, the difference is most prominent at high SNR. It is particularly interesting to note that for large distortions, the high SNR nearest subspace bound in Figure \ref{fig:f3}(b) is less than the corresponding lower bound in Figure \ref{fig:f2}(b). This behavior addresses the question as to whether or not i.i.d. sampling matrices are optimal in the asymptotic setting and shows that in certain cases such matrices are suboptimal.  

\begin{figure*}[htbp]
\centering
\psfrag{x1}[B]{\small Distortion $\alpha$}
\psfrag{y1}[]{\small Sampling Rate $\rho$} 
\psfrag{t3}[B]{(a) Gaussian Source, SNR = 0 dB}
\psfrag{t4}[B]{(b) Gaussian Source, SNR = 40 dB}
\psfrag{t1}[B]{(c) Bounded Source, SNR = 0 dB}
\psfrag{t2}[B]{(d) Bounded Source, SNR = 40 dB}


\subfigure{\label{galen}
\epsfig{file=figures-upper-bounds/rho_alpha_G_SNR_00.eps, width = 0.44\textwidth}

}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_G_SNR_40.eps, width = 0.44\textwidth}
}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_B_SNR_00.eps, width = 0.44\textwidth}
}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_B_SNR_40.eps, width = 0.44\textwidth}
}
\caption{Bounds of sampling rate distortion function $\rho(\alpha)$ for sampling matrices with i.i.d. elements. The upper bounds correspond to Theorems \ref{thm:suf-gml} and \ref{thm:sufMC}. The lower bound corresponds to Theorem 4 in \cite{RG-Lower-Bounds}. Plots (a)-(b) correspond to a zero-mean Gaussian source. Plots (c)-(d) correspond to the  general bounded source $\mathcal{X}(\Omega,\mathcal{F}(\eta,\gamma))$ with $\eta = 0.2$. In all cases $\Omega = 10^{-4}$.  \label{fig:f2}} 
\end{figure*}

\begin{figure*}[htbp]
\centering
\psfrag{x1}[B]{\small Distortion $\alpha$}
\psfrag{y1}[]{\small Sampling Rate $\rho$} 
\psfrag{t7}[B]{(a) Gaussian Source, SNR = 0 dB}
\psfrag{t8}[B]{(b) Gaussian Source, SNR = 40 dB}
\psfrag{t5}[B]{(c) Bounded Source, SNR = 0 dB}
\psfrag{t6}[B]{(d) Bounded Source, SNR = 40 dB}

\psfrag{Lower Bound}[lb]{\small Lower Bound}
\psfrag{(Theorem 1)}[lT]{\small (Proposition \ref{thm:nec1})}
\psfrag{(Theorem 2)}[lT]{\small (Propositions \ref{thm:nec-G} \&  \ref{thm:nec2})}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_U_G_SNR_00.eps, width = 0.44\textwidth}

}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_U_G_SNR_40.eps, width = 0.44\textwidth}
}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_U_B_SNR_00.eps, width = 0.44\textwidth}
}
\subfigure{
\epsfig{file=figures-upper-bounds/rho_alpha_U_B_SNR_40.eps, width = 0.44\textwidth}
}
\caption{Bounds of sampling rate distortion function $\rho(\alpha)$ for optimal sampling matrices. The upper bounds correspond to the convex versions of Theorems \ref{thm:suf-gml} and \ref{thm:sufMC} that are attained using the rate-sharing sampling matrices described Theorem \ref{thm:convex}. The lower bound corresponds to Theorem 3 in \cite{RG-Lower-Bounds}. Plots (a)-(b) correspond to a zero-mean Gaussian source. Plots (c)-(d) correspond to the  general bounded source $\mathcal{X}(\Omega,\mathcal{F}(\eta,\gamma))$ with $\eta = 0.2$. In all cases $\Omega = 10^{-4}$.  \label{fig:f3}} 
\end{figure*}


\subsection{Bounds for a General Source}

We now show how our upper bounds, which are stated in terms of a single distribution function $F$, can be extended to more general sources characterized by a set of distributions $\mathcal{F}$. In particular, we consider the source $\mathcal{X}(\Omega,\mathcal{F}(\eta,\gamma))$ where, for any parameters $\eta \in [0,1]$ and $\gamma \in (0,\infty)$, we define $\mathcal{F}(\eta,\gamma) \subset \mathcal{F}_0$ to be the set of all distributions with power $\gamma$ and a lower bound $\sqrt{\eta \gamma}$ on the magnitude of any realization. This source, which we refer to as the {\em bounded} source,  assumes very little about the actual nonzero values and corresponds to assumptions commonly used in literature for exact recovery \cite{MeinBuhl06, ZhaoYu_JMLR06, aeron-2007,aeron-2008, Reeves_masters, RG08, Wainwright_SharpThresholds_IEEE09, Wainwright_InfoLimits_IEEE09,  akcakaya_IEEE10, FLetcher_IEEE09, Wang_IEEE10, RG-Lower-Bounds}. 


To apply the bounds given in Theorems \ref{thm:suf-gml} and \ref{thm:sufMC} we use the simple fact that, for any set of distributions $\mathcal{F}$ and fixed estimator $\hat{\bs}$, the operational sampling rate distortion function of the source $\mathcal{X}(\Omega,\mathcal{F})$ is equal to the supremum over $F \in \mathcal{F}$ of the operational sampling rate distortion of the source $\mathcal{X}(\Omega,F)$. In other words, we may uniformly bound the source $\mathcal{X}(\Omega,\mathcal{F})$ by considering the worst case distribution $F \in \mathcal{F}$. We remark that this useful property, which is true for any fixed estimator $\hat{\bs}$, is not necessarily true for the fundamental sampling rate distortion function since the optimal estimator for a  source $\mathcal{X}(\Omega,F)$ depends on the distribution $F$. 

To bound the operational sampling rate distortion function corresponding to the nearest subspace estimator, we observe that for any distribution $F$, a lower bound on the power $P(\Omega,F_\beta)$ of the $\beta$-truncated distribution $F_\beta$ provides an upper bound on the right hand side of  \eqref{eq:GMLbound}. Using the fact that $ \inf_{F \in \mathcal{F}(\eta,\gamma)}P(\Omega,F_\beta)= \beta  \Omega  \eta  \gamma$, gives the following upper bound
\begin{align}\label{eq:NSBub}
\rho^{\text{\normalfont NS-UB}}(\alpha) = 
\Omega + \max_{\alpha \le \beta \le 1} \frac{\Omega H(\beta) + (1\!-\!\Omega) H(\frac{\Omega\beta}{1-\Omega})}{\mathcal{L} \big(1+ \beta  \Omega  \eta  \gamma \big)}.
\end{align}

To bound the operational sampling rate distortion function corresponding to the thresholding estimator, we use Corollary \ref{cor:thmsufMC} and the fact that
\begin{align*}
\sup_{F \in \mathcal{F}(\eta,\gamma)} \frac{1+P(\Omega,F)}{P(\Omega, F_{\alpha/2})}  =  \frac{1 + \Omega \gamma}{\eta \gamma\Omega }
\end{align*}
to obtain the upper bound
\begin{align}\label{eq:THBub}
\rho^{\text{\normalfont TH-UB}}(\alpha) &\le  \Omega\frac{1 + \Omega \gamma}{\eta \gamma\Omega }\!\left[ Q^{-1}\!({\textstyle\frac{\alpha}{2}}) + Q^{-1}({\textstyle \frac{\alpha \Omega}{2(1-\Omega)}})\right]^2\!\!.
\end{align}

In Figure \ref{fig:f2}(c)-(d), the upper bounds \eqref{eq:NSBub} and \eqref{eq:THBub} are shown  as a function of the the distortion $\alpha$ for two different SNRs. Also shown is a lower bound designed specifically for the bounded source $\mathcal{X}(\Omega,\mathcal{F}(\eta,\gamma))$ and i.i.d. sampling matrices (see \cite[Section VI-C]{RG-Lower-Bounds}). In Figure~\ref{fig:example1}, the same bounds are shown as a function of the SNR for fixed $\alpha$. In Figure \ref{fig:f3} (c)-(d), convex versions of the upper bounds \eqref{eq:NSBub} and \eqref{eq:THBub} corresponding to the rate-sharing strategy given in Theorem \ref{thm:convex} are shown as a function of $\alpha$ for various SNRs. Also shown is a lower bound (see \cite[Theorem 3]{RG-Lower-Bounds}) which applies universally to any estimator and sampling matrix.

Our bounds for the bounded source have many similarities with the bounds for the Gaussian source. In both cases, the nearest subspace estimator bound is stronger at high SNR and the thresholding bounds is stronger at low SNR. Also, in both cases, the bounds are relatively flat for a range of $\alpha$, but increase rapidly as $\alpha$ tends to zero. The main difference between bounded source and Gaussian source, however, is the point at which this change in behavior occurs. For example, in Figures \ref{fig:f3}(a)-(b) the bounds increase rapidly for all $\alpha$ less than $0.05$. In the corresponding plots for the bounded source, Figure \ref{fig:f3}(c)-(d), this same behavior occurs, but only for $\alpha$ much less than $0.01$.

The reason that small distortions are easier to obtain for the bounded source than for the Gaussian source is that the difficulty of recovery for $\alpha \approx 0$ is dominated by the size of the smallest nonzero values. For the bounded source, these values are bounded away from zero whereas for the Gaussian source the values may be arbitrarily small. This property of a source is precisely what the decay rate $L$ given Definition \ref{def:L} is designed to capture. For example, using the fact that the Gaussian distribution has decay rate $L=1$ and every distribution $F \in \mathcal{F}(\eta,\gamma)$ has decay rate $L=0$, the precise rate at which $\rho(\alpha)$ increases as $\alpha \rw 0$ can be determined using Proposition \ref{thm:scaling-alpha}.
{"config": "arxiv", "file": "1006.3128/sections/examples.tex"}