\documentclass{article}
\usepackage[margin=1in]{geometry}
\usepackage{color}
\usepackage{bm}
\usepackage{amsthm}
\usepackage{assoccnt}
\usepackage{amsmath}
\usepackage[cmintegrals]{newtxmath}

\addtolength{\topmargin}{-.575in}
\newcounter{comment}
\newcounter{reviewer}
\usepackage{graphicx,psfrag}

\newtheorem{theorem}{\textbf{Theorem}}
\newtheorem{coro}{\textbf{Corollary}}
\newcommand{\bs}[1]{\boldsymbol{#1}}
\newcommand{\rev}{\backslash}
\newcommand{\sset}[1]{\mathcal{#1}}
\newcommand{\btheta}{\boldsymbol{\theta}}
\newcommand{\bSigma}{\boldsymbol{\Sigma}}

\newcommand{\newReviewer}{\setcounter{comment}{0}\refstepcounter{reviewer}\subsection*{Comments from Reviewer~\thereviewer}}
\newcommand{\newResponse}[1]{\textbf{Response: }#1}
\renewenvironment{boxed}
	{
		\begin{center}
		\refstepcounter{comment}
		\begin{em}
    		\begin{tabular}{|p{\textwidth}|}
    		\hline\\
		\textbf{Comment~\thecomment}:
    	}
    	{ 
    		\\\\\hline
    		\end{tabular}
		\end{em} 
    		\end{center}
    	}
\newcommand{\newComment}[1]{\begin{boxed}#1\end{boxed}}
\newcommand{\cblue}[1]{{\color{blue}#1}}
\newcommand{\newExtract}[1]{\begin{quote}[...] #1 [...]\end{quote}}

\title{Response to Reviewer Comments}
\author{Mario Coutino, Sundeep P. Chepuri, and Geert Leus}
\begin{document}

	\maketitle
	
	First of all, we would like to thank the reviewers for their thorough and critical view of our work, and in particular for providing useful suggestions aimed to increase the quality of the work and improve its clarity. In addition, we would to thank the AE for handling our manuscript in such timely and effective manner. Major changes in the manuscript have been \cblue{highlighted}. Following the suggestions of the reviewers and the comments of the AE we have made the following changes to the manuscript:
	\begin{itemize}
		\item Theorem 2 and its proof has been modified in order to accommodate the suggestion of Reviewer 2. That is:
		\begin{itemize}
			\item the norm of $\bm\theta$ has been included in the derivation 
			\item the result of Theorem 2 has been changed for that of equation $(54)$, and the result $(55)$ has been stated as a corollary
			\item the derivation for the lower bound has been clarified.
		\end{itemize}
		\item the detailed version of Figure 3 has been added to the manuscript
	\end{itemize}
%========================================================================================================================================	
	\newReviewer
	
	\newComment{Thank you for submitting the revised version, I enjoyed reading this paper and believe it is of interest to the community. While I think adding the plots you have generated in response to my comment Q4 to the paper may be useful for some readers I leave it up to you to decide if you wish to do so.}
	\newResponse{We are glad to know that the reviewer enjoyed reading our manuscript. We are thankful for your comments in the previous round, as they provided an interesting perspective of our work. 	In addition, thanks to them we were able to generate a higher quality version of our manuscript.}
%========================================================================================================================================	
	\newReviewer
	The authors have addressed most of my issues. In particular, I appreciate their improving the text after (30) to avoid another reader having the same misunderstanding as me about 	s(A). However, there are still important issues remaining in the current version.\\
	
	\noindent\newResponse{We want to thank the reviewer for the comments provided in the previous round. Thanks to the suggestions of the reviewer we were able to clarify further our intentions within the manuscript, and provide better insights on the ideas behind our work. We really appreciate the thorough revision that the reviewer performed over the different versions of our manuscript, as it has improved the overall readability of the paper.}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\newComment{Although the new statement of Theorem 2 makes it considerably clearer, the proof provided does not seem to match the result. First, the proof assume $\|\theta\| = 	1$. Also, (22) does not depend on a or $\beta$, whereas the result in the proof does [see (54)]. If the result given only holds for the limiting case, then the theorem cannot claim that it holds for all $\beta \in (0,1)$. Especially since the paper will suggest the use of $\beta = 0.5$. Moreover, the proof only derives the upper bound in (52). Still, the lower bound is necessary to obtain the epsilon-Submodularity relation. It is critical that the statement and proof of Theorem 2 be reviewed so they match.}
	\newResponse{Thanks for pointing out these inconsistencies. Taking into account the reviewer comments we have made the following modifications to correct our oversights: $(i)$ we have modified the proof to incorporate the norm of $\bm\theta$ in the derivation; $(ii)$ the result in the Theorem 2 has been changed to the one of $(54)$, and the current result has been provided as a collorary;  $(iii)$ the lower bound, which was omitted due to an oversight is added. The modified theorem and corollary included in the manuscript are shown here:
	\newExtract{
	\setcounter{theorem}{1}
	\begin{theorem}
	\label{th:epSub}
	For a non-diagonal covariance matrix $\bs\Sigma$, with condition number $\kappa\coloneq\lambda_{\max}/\lambda_{\min}$, minimum eigenvalue $\lambda_{\min}$, maximum 	eigenvalue $\lambda_{\max}$, and admitting a decomposition $\bs\Sigma = a\textbf{I} + \textbf{S}$ where $a$ is chosen as $a = \beta\lambda_{\min}$ with $\beta\in(0,1)$. Such values of $a$ guarantees the positive definiteness of $\bm S$. Then the signal-to-noise ratio set function $s(\mathcal{A})$ is $\epsilon$-approximately submodular with
	\begin{equation}
	\epsilon \leq 4C_{1}\Bigg(\frac{a}{(1-\beta)\lambda_{\min}^2\{\bs\Sigma\}}+ \frac{\nu\kappa^2}{1-\beta}\Bigg),
	\label{eq:thEpSub}
	\end{equation}
	where $C_{1} = \Vert\bs{\theta}\Vert^2_2$, with $\bs{\theta}$ being the mean vector, and $\nu = \min\{a^{-1};\frac{1}{(1-\beta)\lambda_{\min}\{\bs{\Sigma}\}}\}$.
	\end{theorem}	
	\begin{coro}
	For the limiting case, $a \rightarrow 0 \implies \beta \rightarrow 0$, Theorem~\ref{th:epSub} reduces to
	\begin{equation}
		\epsilon \leq 4C_{1}\kappa^2\lambda_{\min}^{-1}.
	\end{equation}
	\end{coro}
	}
	}
	The modified proof is included in the manuscript as:
	\newExtract{
	\begin{proof}First, consider the SNR set function that is defined as [cf.~$(25)$]%[cf.~\eqref{eq:snrExt}]
\begin{equation}
s(\mathcal{A}) := \bs{\theta}^{T}\bm{S}^{-1}\bs{\theta} + h(\mathcal{A}),
\end{equation}
where $h(\mathcal{A}):= -\bs{\theta}^{T}\bm{S}^{-1}\bigg[\bm{S}^{-1}+a^{-1}\text{diag}(\bm{1}_{\mathcal{A}})\bigg]^{-1}\bm{S}^{-1}\bs{\theta}$. For the sake of simplicity, we will rewrite the SNR as follows
\begin{equation}
s(\mathcal{A}) := C_1\tilde{s}(\mathcal{A}),
\end{equation}
where we have defined $\Vert\bs{\theta}\Vert_2^2 = C_1$, and $\tilde{s}(\mathcal{A})$ is the SNR set function with $\bm\theta$ being substitute by $\tilde{\bm\theta} = \bm\theta/\Vert\bm\theta\Vert_{2}$, i.e., the SNR set function is computed only considering the direction of the vector $\bm\theta$ by assuming a unit norm vector.

For completing the proof, we need to show the following:
\begin{equation}
-\epsilon'C_1 \leq C_1\tilde{s}(\mathcal{A})- C_1\hat{s}(\mathcal{A}) \leq \epsilon'C_1,
\label{eq:dbineqFull}
\end{equation}
for some submodular set function $\hat{s}(\mathcal{A})$. In this proof, we select the following auxiliary set function:
\begin{equation}
\hat{s}(\mathcal{A}) = \tilde{\bs{\theta}}^{T}\bm{S}^{-1}\tilde{\bs{\theta}} + \hat{h}(\mathcal{A}),
\end{equation}
where $\hat{h}(\mathcal{A})$ is chosen to be a \emph{modular} set function and is given by
\begin{equation}
\hat{h}(\mathcal{A}) = -\tilde{\bs{\theta}}^{T}\bm{S}^{-1}\bigg(a^{-1}\bm{I} + a^{-1}\text{diag}(\bm{1}_{\mathcal{A}})\bigg)^{-1}\bm{S}^{-1}\tilde{\bs{\theta}}.
\label{eq:modSNR}
\end{equation}
In~\eqref{eq:modSNR}, an identity matrix has been introduced instead the inverse of $\bm{S}$ [cf.~$(25)$]~%[cf.~\eqref{eq:snrExt}] 
to construct a modular set function. Here, it should be noticed that other set functions besides~\eqref{eq:modSNR} could have been used for finding an upper bound on the $\epsilon$ constant. Depending on this choice, different bounds might be obtained.

To provide the epsilon constant for~\eqref{eq:dbineqFull}, we equivalently can establish the following inequalities
\begin{equation}
-\epsilon' \leq \tilde{h}(\mathcal{A}) - \hat{h}(\mathcal{A}) \leq \epsilon',
\label{eq:dbineq}
\end{equation}
that for an specific $\epsilon'\in\mathbb{R}_{+}$ provides the relation in $(22)$. Here, we have defined $\tilde{h}(\mathcal{A}) = C_1^{-1}h(\mathcal{A})$. %~\eqref{eq:thEpSub}.

To obtain the previous inequalities, instead of bounding the expressions in \eqref{eq:dbineq}, we can bound the difference of the positive definite (PD) matrices that are part of the quadratic forms in the set functions in~\eqref{eq:dbineq}. That is,
\begin{equation*}
\begin{array}{ll}
-\epsilon'\bm{I} &\preceq \bm{S}^{-1}\bigg[a^{-1}\bm{I}+a^{-1}\text{diag}(\bm{1}_{\mathcal{A}})\bigg]^{-1}\bm{S}^{-1} \\
&\qquad - \bm{S}^{-1}\bigg[\bm{S}^{-1} + a^{-1}\text{diag}(\bm{1}_{\mathcal{A}})\bigg]^{-1}\bm{S}^{-1}\preceq \epsilon'\bm{I}.
\end{array}
\end{equation*}

Considering $\text{diag}(\bm{1}_{\mathcal{A}})=\bm{E}_{\mathcal{A}}^{T}\bm{E}_{\mathcal{A}}$, we can apply the matrix inversion lemma to expand the difference of the matrices in between brackets above as
\begin{equation}
\bs{\Delta} := a\bigg(\bm{I}-\frac{1}{2}\bm{E}_{\mathcal{A}}^{T}\bm{E}_{\mathcal{A}}\bigg) - \bm{S} + \bm{S}\bm{E}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bm{E}_{\mathcal{A}}\bm{SE}_{\mathcal{A}}^{T} \bigg)^{-1}\bm{E}_{\mathcal{A}}\bm{S}.
\label{eq:delta}
\end{equation}
Hence,
\begin{equation}
-\epsilon'\bm{I} \preceq \bm{S}^{-1}\bs{\Delta}\bm{S}^{-1}\preceq \epsilon'\bm{I}.
\end{equation}
As all terms in~\eqref{eq:delta} are PD matrices, we upper bound the matrix in~\eqref{eq:delta} by removing the negative terms in~\eqref{eq:delta}, and lower bound by removing all the positive terms. That is,
\begin{equation}
-\bigg(\frac{a}{2}\bm{I} + \bm{S}\bigg) \preceq \bs{\Delta} \preceq a\bm{I} + \bm{S}\bm{E}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bm{E}_{\mathcal{A}}\bm{SE}_{\mathcal{A}}^{T} \bigg)^{-1}\bm{E}_{\mathcal{A}}\bm{S}.
\end{equation}
From the definition of $\bm{S}$ and $a$, we can notice that a possible lower bound for the expression above is given by
\begin{equation}
-\lambda_{\max}\{\bs\Sigma\} \preceq \bs\Delta.
\end{equation}
For the upper bound, we notice that by the maximum singular value of the second matrix, the following inequality holds
\begin{eqnarray*}
\bs{\Delta} &\preceq a\bm{I} + \sigma_{\max}\bigg\{\bm{S}\bm{E}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bm{E}_{\mathcal{A}}\bm{SE}_{\mathcal{A}}^{T} \bigg)^{-1}\bm{E}_{\mathcal{A}}\bm{S}\bigg\}\bm{I}\\
&\preceq a\bm{I} + \lambda_{\min}^{-1}\bigg\{a\bm{I} + \bm{E}_{\mathcal{A}}\bm{SE}_{\mathcal{A}}^{T}\bigg\}\sigma_{\max}^{2}\bigg\{\bm{E}_{\mathcal{A}}\bm{S}\bigg\}\bm{I}\\
&\preceq a\bm{I} +
\min\{a^{-1};\frac{1}{(1-\beta)\lambda_{\min}\{\bs\Sigma\}}\}\lambda_{\max}^{2}\{\bm{S}\}\bm{I},\\
&\preceq a\bm I + \nu\lambda_{\max}^2\{\bm S\}\bm I
\end{eqnarray*}
where the submultiplicativity and subadditivity of singular values is used in the second and third inequality, respectively, and we have defined $\nu = \min\{a^{-1};\frac{1}{(1-\beta)\lambda_{\min}\{\bs{\Sigma}\}}\}$. Here, the minimum of these two quantities is considered for the limiting case, i.e., $a\rightarrow 0$. 

Considering that 
\begin{equation}
\lambda_{\max}\{\bs\Sigma\} \leq a + \nu\lambda_{\max}^2\{\bm S\},
\end{equation}
we can bound the matrix in~\eqref{eq:delta} by both sides as follows
\begin{equation}
	-(a\bm I + \nu\lambda_{\max}^2\{\bm S\}\bm I) \preceq \bs\Delta \preceq a\bm + \nu\lambda_{\max}^2\{\bm S\}\bm,
\end{equation}
hence we solely continue deriving the upper bound for the expression above as the obtained $\epsilon$ will hold for both lower and upper bound.
 
Now, considering that the eigenvalues of $\bs{\Sigma}$ are larger to those of $\bm{S}$ by definition, $\bm S^{-1} \preceq \lambda_{\min}^{-1}\{\bm S\}\bm I$, and recalling that $a = \beta\lambda_{\min}\{\bs{\Sigma}\}$ we obtain
\begin{eqnarray}
\bm S^{-1}\bs{\Delta}\bm{S}^{-1} \preceq \frac{a}{(1-\beta)\lambda_{\min}^2\{\bs\Sigma\}}\bm{I} + \frac{\nu\kappa^2}{1-\beta}\bm I
%\preceq \bigg(a + \frac{\kappa}{\beta}\lambda_{\max}\{\bs{\Sigma}\}\bigg)\bm{I}
= \epsilon'\bm{I},
\label{eq:lstchain}
\end{eqnarray}
where $\kappa$ is the condition of the matrix $\bs \Sigma$.

Finally, the expression for $\epsilon'$ in~\eqref{eq:lstchain} can now be used to bound the expression in~\eqref{eq:dbineqFull}. By using the fact that $\hat{h}$ is a modular function we can write the following inequalities
\begin{equation*}
\begin{split}
&C_1\tilde h(\sset{A}\cup\{i\}) - C_1\tilde h({\sset{A}}) - C_1\tilde h({\sset{A}\cup\{i,j\}}) + C_1\tilde h({\sset{A}\cup\{j\}})\\
&\leq C_1\hat{h}({\sset{A}\cup\{i\}}) - \epsilon'C_1 - C_1\hat{h}({\sset{A}}) -\epsilon'C_1 - C_1\hat{h}({\sset{A}\cup\{i,j\}}) -\epsilon'C_1 +\\
& \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;C_1\hat{h}({\sset{A}\cup\{j\}}) -\epsilon'C_1 = -4\epsilon'C_1,
\end{split}
\end{equation*}
proving the result of the theorem. 

For the limiting case, $a \rightarrow 0 \implies \beta \rightarrow 0$, we obtain:
\begin{equation}
\epsilon' = \frac{\kappa^2}{\lambda_{\min}\{\bs\Sigma\}},
\label{eq:lstchain2}
\end{equation}
which shows a relation with the typical experiment design metrics, i.e., maximisation of minimum eigenvalue and log determinant (promotes good matrix condition).
\end{proof}
	}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\newComment{I do think that the detailed figure should be included in Fig. 3. What is more, since $K << M$ is the situation of interest in practice (and in this work, for that matter, given the "sparse" in the title), there seems to be no advantage in using the submodular surrogate over greedy SNR, at least in the example presented. Would there be a better example where the submodular surrogate clearly outperforms greedy SNR in the cases of interest? If not, what is the advantage of this surrogate objective?}
	\newResponse{Thanks for pointing this out, following your suggestion in the current version of the manuscript we have added the detailed figure related to Fig.3. While we do agree that for $K \leq 0.25M$ the submodular surrogate does not show any clear benefit over greedy SNR, we stress that in this example for the range $K \geq 0.25M$, the surrogate demonstrates it benefits. Moreover, it is true that we focus on sparse sensing, but it many instances just reducing elements will not lead to systems meeting minimum requirements, e.g., operational SNR. In this regard, looking at Fig.3, for a nominal system with requirement $SNR \geq 20dB$ only using greedy SNR will lead to a solution containing a higher number of sensors, while using the proposed surrogate leads to a solution that involves less sensors. We want to emphasis that even though through the manuscript we focus on the cardinality constraint formulation (P-CC) [cf.(11)], the proposed methods are also suitable to performance constraint (P-DC) formulations [cf.(12)]. Therefore, in cases that a fixed SNR is required, using the proposed surrogate provides clear advantages than SNR greedy.}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\newComment{I understand the value of Theorem 2 in explaining when greedy SNR minimization may be a good approach. However, as a guarantee, it is only valid if the bound on 	epsilon is small compared to $f^\star/K$. Otherwise, it gives no performance guarantee. It would be good to see numerical values of $\epsilon$ (perhaps as a function of $\kappa$ and other parameters) to make sure that the result is informative.}
	
	\newResponse{The reviewer is right in the fact that an small $\epsilon$ implies that the set function is in a \emph{overall} sense near submodular (with respect all possible subsets). However, it is only necessary a pair of subset that behaves in an odd way to obtain an $\epsilon$ constant large compared to $f^\star/K$. In addition, any intuition that can be drawn from observing this constant for small instances problems (where it is possible to compute), might not be extrapolated properly to large instances. It would not be proper to make any claim on the behaviour of $\epsilon$ by testing simple computationally feasible examples. As a result, the provided bound in $\epsilon$ is aimed to provide a description of the behaviour of the constant, rather to provide a definite statement about it. Here, we include a figure that show the average behaviour of $\epsilon$ for a serie of Monte Carlo simulations for PD matrices with different condition numbers. The reported value, $r_\kappa$, is defined as the ratio between $\epsilon$ and $f(\mathcal{V})$. Our intention of deriving this bound was to clarify in which instances greedy might perform well, however this is not the only characterization of the possible. This fact is mention in the manuscript to make the reader aware of such situation.
	\begin{figure}
	\centering
	\includegraphics[width=0.6\textwidth]{reviewImage}
	\caption{Average behaviour of $\epsilon$ constant as a function of condition number of $\bs\Sigma$ ($\kappa$)}
	\end{figure}}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\newComment{``number of function evaluations required by the method scales linearly in the number of selected sensors": this should read "polynomially". $K$ is a fraction of $M$, say $rM$. Therefore, greedy requires $\mathcal{O}(rM^2)$ cost function evaluations.}
		
	\newResponse{Thanks for your comment. Indeed, perhaps our statement may be misleading. By saying that the number of function evaluation scales linearly we meant $\mathcal{O}(KM)$, which is equivalent to the statement provided by the reviewer, i.e., $\mathcal{O}(rM^2)$. We have incorporate your suggestion to the manuscript in the following form:}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\newExtract{number of function evaluations required by the method scales \cblue{polynomially} in the number of \cblue{available} sensors,}
	Here we changed selected sensors ($K$) to ``available" sensors ($M$) to be consistent with the suggestion of the reviewer.
%========================================================================================================================================
	\newReviewer

	\newComment{Although the authors did not implement all of my recommended revisions, I am happy with the extension to the case of unequal means and unequal variances, hence I recommend the paper for publication.}
	
	\newResponse{Thanks for the valuable suggestions of the previous round, through them we were able to generalize our work and increased considerably the quality of the manuscript. We are thankful for that.}
\end{document}