\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 review 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 like to thank the AE for handling our manuscript in such a 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 have been modified in order to accommodate the suggestions 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 limited to that of equation $(66)$, and the result $(67)$ has been stated as a corollary;
			\item the derivation of the lower bound has been clarified.
		\end{itemize}
		\item the detailed version of Figure 3 has been added to the manuscript as per the suggestion from Reviewer~2.
	\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 have provided an interesting perspective of our work as well as helped us improve the quality of the manuscript. Although we agree with the fact that plots provide some insights in the complexity of the method, we believe that the derived theoretical description of the complexity of the method is a stronger result, and provides a more insightful contribution detached of any implementation {tricks} or code optimization. Therefore, we decided to not include the mentioned plots in the final version of the manuscript.}
%========================================================================================================================================	
	\newReviewer
	\emph{
	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 in the ideas behind our work. We really appreciate the thorough proof reading 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 Theorem 2 has been limited to the one of $(66)$, 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}
	\setcounter{equation}{21}
	\begin{theorem}
	\label{th:epSub}
	Let $\bs\Sigma$ be a non-diagonal covariance matrix, with minimum eigenvalue $\lambda_{\min}\{\bs\Sigma\}\neq 0$, maximum eigenvalue $\lambda_{\max}\{\bs\Sigma\}$, condition number $\kappa\coloneq\lambda_{\max}\{\bs\Sigma\}/\lambda_{\min}\{\bs\Sigma\}$, that admits a decomposition $\bs\Sigma = a\textbf{I} + \textbf{S}$ where $a$ is chosen as $a = \beta\lambda_{\min}$ with $\beta\in(0,1)$ to guarantee the positive definiteness of $\bm S$. Then the signal-to-noise ratio set function $s(\mathcal{A})$ is $\epsilon$-approximately submodular with
%	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)^2\lambda_{\min}^2\{\bs\Sigma\}}+ \frac{\nu\kappa^2}{(1-\beta)^2}\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},{(1-\beta)^{-1}\lambda_{\min}^{-1}\{\bs{\Sigma}\}}\}$.
	\end{theorem}	
	\begin{proof}
	See Appendix~A
	\end{proof}
	\begin{coro}
	For the limiting case, $a \rightarrow 0$ or equivalently $\beta \rightarrow 0$, Theorem~\ref{th:epSub} reduces to
	\begin{equation}\label{eq:coEpSub}
		\epsilon \leq 4C_{1}\kappa^2\lambda_{\min}^{-1}\{\bs\Sigma\}.
	\end{equation}
	\end{coro}
	\begin{proof}
	Follows from Theorem~\ref{th:epSub} (See Appendix~A).
	\end{proof}
	}
	}
	The modified proof is included in the manuscript as:
	\newExtract{
	\setcounter{equation}{46}
	\begin{proof}First, consider the SNR set function that is defined as [cf.~$(20)$]%[cf.~\eqref{eq:snrExt}]
\begin{equation}
s(\sset{A}) = \bs{\theta}_\sset{A}^T\bs{\Sigma}^{-1}_\sset{A}\bs{\theta}_\sset{A}.
\end{equation}
Combining the above expression and the decomposition $\bs\Sigma = a\bm I + \bm S$, the signal-to-noise ratio can be rewritten as~$[17]$
%s(\textbf{w}) = \bs{\theta}^{T}\textbf{S}^{-1}\bs{\theta} - \bs{\theta}^{T}\textbf{S}^{-1}\big[\textbf{S}^{-1} + a^{-1}\text{diag}(\textbf{w})\big]^{-1}\textbf{S}^{-1}\bs{\theta}.
\begin{align}
s(\sset{A}) &= \bs{\theta}_\sset{A}^T\bs{\Sigma}^{-1}_\sset{A}\bs{\theta}_\sset{A} \\
				&= \bs{\theta}^{T}\textbf{S}^{-1}\bs{\theta} - \bs{\theta}^{T}\textbf{S}^{-1}\big[\textbf{S}^{-1} + a^{-1}\text{diag}(\bm 1_{\sset{A}})\big]^{-1}\textbf{S}^{-1}\bs{\theta}, \\
				&= \bs{\theta}^{T}\bm{S}^{-1}\bs{\theta} + h(\mathcal{A}), \label{eq:thEqSinv}
\end{align}
%\begin{equation}
%s(\sset{A}) = \bs{\theta}^{T}\textbf{S}^{-1}\bs{\theta} - \bs{\theta}^{T}\textbf{S}^{-1}\big[\textbf{S}^{-1} + a^{-1}\text{diag}(\bm 1_{\sset{A}})\big]^{-1}\textbf{S}^{-1}\bs{\theta},
%\label{eq:snrExt}
%\end{equation}
where the non-zero entries of the vector $\bm 1_{\sset{A}}$ are given by the set $\sset{A}$
%\begin{equation}
%s(\mathcal{A}) := \bs{\theta}^{T}\bm{S}^{-1}\bs{\theta} + h(\mathcal{A}),
%\end{equation}
and $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 $ C_1=\Vert\bs{\theta}\Vert_2^2$, and $\tilde{s}(\mathcal{A})$ is the SNR set function with $\bs\theta$ being substituted by $\tilde{\bs\theta} = \bs\theta/\Vert\bs\theta\Vert_{2}$, i.e., the SNR set function is computed only considering the direction of the vector $\bs\theta$.

%For completing the proof, we need to show the following:
{\color{blue}
Now, let us assume that there exists a $\epsilon'\in\mathbb{R}_+$ such that
\begin{equation}
%-\epsilon'C_1 \leq C_1\tilde{s}(\mathcal{A})- C_1\hat{s}(\mathcal{A}) \leq \epsilon'C_1,
-\epsilon' \leq \tilde{s}(\mathcal{A})- \hat{s}(\mathcal{A}) \leq \epsilon',
\label{eq:dbineqFull}
\end{equation}
for any $\mathcal{A}\subseteq\mathcal{V}$ and some modular set function $\hat{s}(\mathcal{A})$. Using~\eqref{eq:dbineqFull}, we can obtain the following expression
\begin{equation}\label{eq:deltaExpSub}
\delta(\mathcal{A}\cup\{i\}) - \delta(\mathcal{A}) - \delta(\mathcal{A}\cup\{i,j\}) + \delta(\mathcal{A}\cup\{j\}) \geq -4\epsilon',% = -\epsilon,
%\tilde{s}(\mathcal{A}\cup\{i\}) - \hat{s}(\mathcal{A}\cup\{i\}) - \hat{s}(\mathcal{A}) - \hat{s}(\mathcal{A}\cup\{i,j\}) + \hat{s}(\mathcal{A}\cup\{j\}) \geq 0,
\end{equation}
where we have defined $\delta(\mathcal{A}) = \tilde{s}(\mathcal{A})- \hat{s}(\mathcal{A})$. Due to the modularity of $\hat{s}(\mathcal{A})$, i.e.,
\begin{equation}\label{eq:subsexp}
\hat{s}(\mathcal{A}\cup\{i\}) - \hat{s}(\mathcal{A}) - \hat{s}(\mathcal{A}\cup\{i,j\}) + \hat{s}(\mathcal{A}\cup\{j\}) = 0,
\end{equation}
and using expressions~\eqref{eq:deltaExpSub} and~\eqref{eq:subsexp}, we can show that
\begin{equation}
%C_1\bigg(\tilde{s}(\mathcal{A}\cup\{i\}) - \tilde{s}(\mathcal{A}) - \tilde{s}(\mathcal{A}\cup\{i,j\}) + \tilde{s}(\mathcal{A}\cup\{j\})\bigg) \geq -4\epsilon'C_1% = -\epsilon,
\tilde{s}(\mathcal{A}\cup\{i\}) - \tilde{s}(\mathcal{A}) - \tilde{s}(\mathcal{A}\cup\{i,j\}) + \tilde{s}(\mathcal{A}\cup\{j\}) \geq -4\epsilon'.% = -\epsilon,
\end{equation}
From this it is clear that the set function $\tilde{s}(\mathcal{A})$ is $\epsilon$-submodular with an $\epsilon\leq 4\epsilon' $ (or equivalently, $s(\mathcal{A})$ is $\epsilon$-submodular with an $\epsilon\leq 4\epsilon' C_1$). Therefore, for completing the proof we require to establish the bound in~\eqref{eq:dbineqFull} for the specific $\epsilon'$ given in~\eqref{eq:thEpSub}. In the following, we devote ourselves to this task.}

For 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} [cf.~\eqref{eq:subsexp}] set function and it 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}, a scaled identity matrix has been introduced instead of the inverse of $\bm{S}$ [cf.~\eqref{eq:thEqSinv}]~%[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 prove~\eqref{eq:dbineqFull}, we equivalently will establish the following inequalities
\begin{equation}
-\epsilon' \leq \tilde{h}(\mathcal{A}) - \hat{h}(\mathcal{A}) \leq \epsilon',
\label{eq:dbineq}
\end{equation}
where we have defined $\tilde{h}(\mathcal{A}) = C_1^{-1}h(\mathcal{A})$. To obtain these inequalities, 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, we need to show that
\begin{equation}\label{eq:doubleIneq}
\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}})=\bs{\Phi}_{\mathcal{A}}^{T}\bs{\Phi}_{\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}\bs{\Phi}_{\mathcal{A}}^{T}\bs{\Phi}_{\mathcal{A}}\bigg) - \bm{S} + \bm{S}\bs{\Phi}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bs{\Phi}_{\mathcal{A}}\bm{S}\bs{\Phi}_{\mathcal{A}}^{T} \bigg)^{-1}\bs{\Phi}_{\mathcal{A}}\bm{S}.
\label{eq:delta}
\end{equation}
Hence~\eqref{eq:doubleIneq} becomes,
\begin{equation}
-\epsilon'\bm{I} \preceq \bm{S}^{-1}\bs{\Delta}\bm{S}^{-1}\preceq \epsilon'\bm{I}.
\end{equation}
{\color{blue}
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 it 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}\bs{\Phi}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bs{\Phi}_{\mathcal{A}}\bm{S}\bs{\Phi}_{\mathcal{A}}^{T} \bigg)^{-1}\bs{\Phi}_{\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\}\bm I \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{align*}
\bs{\Delta} &\preceq a\bm{I} + \sigma_{\max}\bigg\{\bm{S}\bs{\Phi}_{\mathcal{A}}^{T}\bigg(a\bm{I} + \bs{\Phi}_{\mathcal{A}}\bm{S}\bs{\Phi}_{\mathcal{A}}^{T} \bigg)^{-1}\bs{\Phi}_{\mathcal{A}}\bm{S}\bigg\}\bm{I}\\
&\preceq a\bm{I} + \lambda_{\min}^{-1}\bigg\{a\bm{I} + \bs{\Phi}_{\mathcal{A}}\bm{S}\bs{\Phi}_{\mathcal{A}}^{T}\bigg\}\sigma_{\max}^{2}\bigg\{\bs{\Phi}_{\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 + \nu\lambda_{\max}^2\{\bm S\})\bm I,
\end{align*}
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},(1-\beta)^{-1}\lambda_{\min}^{-1}\{\bs{\Sigma}\}\}$. Here, the minimum of these two quantities is considered to simplify the expression of the limiting case, i.e., $a\rightarrow 0$. 

{\color{blue}
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 I + \nu\lambda_{\max}^2\{\bm S\}\bm I.
\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 than 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)^{2}\lambda_{\min}^2\{\bs\Sigma\}}\bm{I} + \frac{\nu\kappa^2}{(1-\beta)^2}\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 number of the matrix $\bs \Sigma$, proving the result of the theorem.
%
%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$ or equivalently $\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., maximization of the minimum eigenvalue and log determinant (which promotes a 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 its benefits. Moreover, it is true that although we focus on sparse sensing, in many instances reducing the number of sensors too much might not lead to systems meeting minimum requirements, e.g., operational SNR. In this regard, looking at Fig. 3, for a nominal system with a requirement of $SNR \geq 20dB$ only using Greedy SNR will lead to a solution containing a high number of sensors, while using the proposed surrogate leads to a solution that involves less sensors. We want to emphasize that even though throughout the manuscript we focus on the cardinality constraint formulation (P-CC) [cf. (11)], the proposed methods are also suitable for performance constraint (P-DC) formulations [cf. (12)]. Therefore, in cases that a fixed SNR is required, using the proposed surrogate provides clear advantages over Greedy SNR. The following comment about this observation has been added in the manuscript:
	\newExtract{\color{blue} We want to emphasize that even though throughout the manuscript we focus on the cardinality constraint formulation (P-CC) [cf.~$(11)$], the proposed methods are also suitable for performance constraint (P-DC) formulations [cf.~$(12)$]. In many instances reducing the number of sensors too much might not lead to systems meeting minimum requirements, e.g., operational SNR. In this regard, observing Fig. 3, for a nominal system with a requirement of $SNR \geq 20dB$ (i.e., the performance constraint in~$(11)$) only using Greedy SNR will lead to a solution containing a high number of sensors, while using the proposed surrogate leads to a solution that involves less sensors. Therefore, despite that for low values of $K$, there is no notable difference between both algorithms, in cases that a fixed SNR is required, using the proposed surrogate provides a clear advantage with respect to Greedy SNR.}
	}
	\begin{figure}
		\centering
	\includegraphics[width=0.5\textwidth]{imageDetailed.eps}
	\end{figure}
	%-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-++-+-+
	\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 a small $\epsilon$ implies that the set function is in an \emph{overall} sense near submodular (with respect to all possible subsets). However, only one pair of odd behaving subsets is required 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 problems (where it is possible to compute it), might not be extrapolated properly to large problem 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 on $\epsilon$ is aimed to provide a description of the behaviour of the constant, rather than to provide a definite statement. In this answer, we include a figure that shows the average behaviour of $\epsilon$ for a series 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})$. From this plot, it can be seen that the $\epsilon$ constant is indeed monotone increasing with respect to the condition number of the matrices, as concluded from the bound. However, beyond the monotonicity of the $\epsilon$ constant with respect to $\kappa$, no further conclusions can be drawn from the plot. Therefore, we decided not to include these kind of plots in the manuscript.  Finally, we would like to emphasize that in our work, our main intention for deriving this bound was to clarify for which instances greedy might perform well.
	\begin{figure}
	\centering
	\includegraphics[width=0.6\textwidth]{reviewImage}
	\caption{Average behaviour of $\epsilon$ constant as a function of condition number, $\kappa$, of $\bs\Sigma$}
	\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{In this respect, we want to emphasize that $K$ and $M$ are independent of each other. That is, when the number of selected sensors is increased the method scales linearly in $K$, as $M$ is kept fixed. Similarly, for a fixed number of desired sensors $K$, for different number of available sensors the method scales linearly in $M$. Therefore, as each of this quantities are independent of each other, our original statement is valid.}
	%	\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 in the previous round. Through them we were able to generalize our work and increase considerably the quality of the manuscript.}
\end{document}