\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{\lmin}{\lambda_{\min}}
\newtheorem{mydef}{\bm{Definition}}
\usepackage[cmintegrals]{newtxmath}

\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 the derivation in Theorem 2 has been clarified and the following minor addition has been made
		\begin{itemize}
			\item the suggestion for the derivation of Reviewer 1 has been added
		\end{itemize}
		\item Eq. $(53-55)$ have been modified to use a general set $\mathcal{B}$ instead of sets differing in a single element as recommended by Reviewer $1$.
		\item the claims with respect to the complexity of the greedy algorithm have been made more precise
	\end{itemize}
%========================================================================================================================================	
	\newReviewer
	I once again thank the authors and editors for taking the time to address my concerns. There are minor points still outstanding, but the major issue is that there are still typos in the proof. Though I don't believe they would change the result much, I cannot recommend this paper for publication unless the proof of Theorem 2, the main theoretical result of the paper, is correct.\\
	
	\noindent\newResponse{We want to thank you for your comments in the previous rounds. They provided helped us improve the quality of the manuscript. We really appreciate the thorough proof reading that the reviewer performed over the different versions of our manuscript, particularly with respect to Theorem $2$, as it has improved the quality, clarity and correctness of the paper.}
	
	\newComment{I refer here to the sequence of inequalities after (63). I believe the min in the third inequality does not hold. I believe the right sequence they are looking for is $\lambda_{min}^{-1}(a\bm I + \bm\Phi \bm S \bm\Phi) = [a + \lambda_{min}(\bm \Phi \bm S \bm\Phi)]^{-1} <= [a + \lambda_{min}(S)]^{-1}$. If the authors use a different bound or approximation, it should be made clear in the text. Currently, the result reads $\lambda_{min}^{-1}(a\bm I + \bm\Phi \bm S \bm\Phi) <= \min(1/a, [(1-\beta)\lambda_{min}(\bm\Sigma)]^{-1}) = \min(1/a, [\lambda_{min}(\bm S)]^{-1})$, since $a = \beta \lambda_{min}(\bm \Sigma)$ so that $(1-\beta)\lambda_{min}(\bm \Sigma) = \lambda_{min}(\bm\Sigma) - a = \lambda_{min}(\bm S)$. I'd ask that the authors recheck their proof to make sure it holds and if so, give more details on these steps. 
	
	\hspace{1ex} Another thing is that (54) does not match the definition of epsilon-approximate submodularity given in Definition 2, since it involves only sets whose cardinalities differ by at most 1. I think that changing (53)-(55) to a generic $\mathcal{B}$ as in Definition 2 would not alter the result, but it would make the proof correct.}
	\newResponse{We thank again the reviewer for its concerns with respect to the quality of our results. After your comment, we include here the rationale behind the inequalities in the manuscript: 
	\begin{eqnarray}
		\lambda_{\min}^{-1}\{a\bm I + \bm\Phi_{\mathcal{A}}\bm S\bm\Phi_{\mathcal{A}}^{T}\} &\leq& \min\{\lambda_{\min}^{-1}\{a\bm I\}, \lambda_{\min}^{-1}\{\bm\Phi_{\mathcal{A}}\bm S\bm\Phi_\mathcal{A}^{T}\}\}\\
		&\leq& \min\{ 1/a, \lambda_{\min}^{-1}\{\bm S\} \} \\
		&=& \min\{  1/a, (1-\beta)^{-1}\lambda_{\min}^{-1}\{\bm\Sigma\} \}\label{eq:bndS},
	\end{eqnarray}
	where $(1)$ follows from the composition of PD matrices, $(2)$ uses the interlacing theorem for submatrices of PD matrices, and $(3)$ restates the result in terms of the parameters $a$ and $\beta$.
	
	As the reviewer pointed out, an alternative route to obtain the inequalities is through its suggestion. That is, we can follow the chain
	\begin{eqnarray}
		\lambda_{\min}^{-1}\{a\bm I + \bm\Phi_{\mathcal{A}}\bm S\bm\Phi_{\mathcal{A}}^T\} &\leq& \lambda_{\min}^{-1}\{a\bm I + \bm S\}\\
		&=& \lambda_{\min}^{-1}\{ \bm\Sigma \}\label{eq:bndE},
	\end{eqnarray}
	which in turns leads to a similar bound. Here, we notice that the bound using~\eqref{eq:bndE} might be tighter than using~\eqref{eq:bndS}. However, as pointed out by the reviewer in previous rounds, using~\eqref{eq:bndE} does not include the parameters $a$, and $\beta$ as explicitly as using~\eqref{eq:bndS}. As a result, during the previous revision of the manuscript we decided to use the bound obtained with~\eqref{eq:bndS}. Nonetheless, as the bound resulting from using~\eqref{eq:bndE} results in a \emph{tighter} bound, we have decided to update our manuscript with the reviewer suggestion. This change does not affect our result. Furthermore, observing the corollary, when $\beta\rightarrow 0$, we notice that the bound in $(67)$ does not change when~\eqref{eq:bndE} is used. 
	\newExtract{ {\color{blue}
	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*}
\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} +
\lambda_{\min}^{-1}\{a\bm I + \bm S\}\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$. 
where the submultiplicativity and subadditivity of singular values, and the interlacing theorem for submatrices of PD matrices are used in the second and third inequality, respectively, and we have defined $\nu = \lambda_{\min}^{-1}\{\bs\Sigma\}$.}
	}	
	With respect to the reviewer comment of the expressions in equations $(53-55)$ we have modified the equations $(53-55)$ to match the expressions used in Def. $1$ and Def. $2$ that makes use of a general set $\mathcal{B}$. Here are the changes made in the manuscript:
	\newExtract{
	\color{blue}
	Using $(52)$ and considering $\mathcal{A}\subseteq\mathcal{B}\subseteq\mathcal{V}$ and $i\not\in\mathcal{B}$, we can obtain the following expression
\begin{equation}\label{eq:deltaExpSub}\tag{53}
\delta(\mathcal{A}\cup\{i\}) - \delta(\mathcal{A}) - \delta(\mathcal{B}\cup\{i\}) + \delta(\mathcal{B}) \geq -4\epsilon',% = -\epsilon,
%\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}\tag{54}
\hat{s}(\mathcal{A}\cup\{i\}) - \hat{s}(\mathcal{A}) - \hat{s}(\mathcal{B}\cup\{i\}) + \hat{s}(\mathcal{B}) = 0,
%\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}\tag{55}
%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{B}\cup\{i\}) + \tilde{s}(\mathcal{B}) \geq -4\epsilon'.% = -\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}
	}
	}
%in the previous version we employed the \emph{disminishing return} definition for submodular/modular functions. This definition is equivalent to the definition that uses sets that differs in a single element [cf. Submodular functions and Optimization -Fujishige]. However, considering the reviewer comment, we decided to add this alternative definition in Def. $(1)$ and Def. $(2)$ for the sake of clarity and to avoid any misunderstandings.
%	\newExtract{{\color{blue}
%	\textbf{Definition $\bm 1$. (Submodularity)} Let $\mathcal{V}=\{1,2,\ldots,M\}$ refer to a ground set, then the set function $f:2^{\vert\mathcal{V}\vert}\rightarrow\mathbb{R}$ is said to be submodular, if for every $\mathcal{A}\subseteq\mathcal{B}\subseteq\mathcal{V}$ and $v\in\mathcal{V}\setminus\mathcal{B}$ it holds that
%\begin{equation}
%f(\mathcal{A}\cup\{v\}) - f(\mathcal{A}) \geq f(\mathcal{B}\cup\{v\}) - f(\mathcal{B}),
%\label{eq:subDef}
%\end{equation}
%or equivalently, for every $\mathcal{A}\in\mathcal{V}$ and $v_1,v_2\in\mathcal{V}\setminus\mathcal{A}$ it holds that 
%\begin{equation}
%f(\mathcal{A}\cup\{v_1\}) - f(\mathcal{A}) \geq f(\mathcal{A}\cup\{v_1,v_2\}) - f(\mathcal{A}\cup\{v_2\}).
%\label{eq:subDef3}
%\end{equation}
%	}
%	}
%	
%	\newExtract{ {\color{blue}
%	\textbf{Definition $\bm 2.\;\;\bm{(}\bs{\epsilon}$-Submodularity)} A set function $f:2^{\vert\sset{V}\vert}\rightarrow\mathbb{R}$ defined on the subsets of a ground set $\sset{V}$, is approximately submodular with constant $\epsilon> 0$ or $\epsilon$-submodular, if for all sets $\sset{A}\subseteq\sset{B}\subseteq{V}$, and $v\in\sset{V}\rev\sset{B}$ it holds that
%\begin{equation}
%f(\sset{A}\cup\{v\}) - f(\sset{A}) \geq f(\sset{B}\cup\{v\}) - f(\sset{B}) - \epsilon,
%\end{equation}
%or equivalently, for every $\mathcal{A}\in\mathcal{V}$ and $v_1,v_2\in\mathcal{V}\setminus\mathcal{A}$ it holds that 
%\begin{equation}
%f(\mathcal{A}\cup\{v_1\}) - f(\mathcal{A}) \geq f(\mathcal{A}\cup\{v_1,v_2\}) - f(\mathcal{A}\cup\{v_2\}) - \epsilon.
%\label{eq:subDef2}
%\end{equation}
%	}
%	}
%	}
	\newComment{The authors have a point that for fixed M or K, greedy search has linear complexity in the non-fixed parameter. However, both parameters are inputs to the algorithm and should be considered as such. The complexity is therefore polynomial. Claiming greedy search to be of linear complexity is incorrect. Check, for instance, [Sipser, Introduction to the theory of computation]. In fact, there has been work on constructing a linear time greedy algorithm, e.g., [Mirzasoleiman et al. Lazier than lazy greedy], but it involves randomization. Naturally, these are all query complexity results.}
	\newResponse{Thanks for pointing out this situation. Complexity notation for more than one input variable is always problematic. Due to this, we made the statement that when one of these two parameters is fixed, the greedy search has linear complexity. For sensor selection applications, this is the common case, e.g., fixed number of available sensors. We, under no circumstances, claim that it is a \emph{linear complexity algorithm} for $M$ and $K$ as this is clearly not true. Therefore, we consider that stating that: \emph{``greedy search scales linearly on the available set for fixed $K$"} or \emph{``greedy search scales linearly on the number of selected sensors for fixed $M$"} is not incorrect as long as we are precise in the statement (in these cases, it is always assumed that the other parameter is fixed). 
	However, in order to consider the reviewer comment we made our claims even more precise by using the following statements in the manuscript:
	\newExtract{
	 \color{blue} it accepts a near-optimal maximization using a greedy algorithm that despite its general polynomial complexity, scales linearly in the number of available sensors through its recursive description when the number of selected sensors is fixed
	}
	\newExtract{
	\color{blue} are more attractive as for a fixed $K$ the number of function evaluations required by the method scales linearly in the number of available sensors. Therefore, the complexity only depends on the efficient evaluation of the cost function.
	}
	\newExtract{
		\color{blue} the proposed method, for a fixed $K$, scales linearly with respect to the number of available sensors.
	}
	We understand your concern from the theoretical complexity perspective. Depending on the size of the input, notations such as $\mathcal{O}(MK)$ might imply different things, e.g., matrix multiplication is considered \emph{linear} as the input is of size $\mathcal{O}(MK)$, while for string lookups $\mathcal{O}(MK)$ implies $\mathcal{O}(\max\{M,K\}^2)$ (the inputs are two strings which possible maximum length). For the case of Mirzasoleiman et al., it can be argued that the query complexity $\mathcal{O}(M\log1/\epsilon)$, in worst case, is also polynomial (with a very low exponent) and not linear. However, it is commonly accepted that $\epsilon$ is not related to the input and treated similar to a fixedparameters in fixed-parameter tractable (FPT) problems. In certain sense, the sampling strategy introduced in Mirzasoleiman et al creates another dependency ($\log1/\epsilon$), which might be artificially related with $K$ or $M$, but that is expected to be smaller than $K$ for practical cases. This leads to the main motivation of Mirzasoleiman et al. which is the reduction of the dependency in $K$. This behaviour is obtained by degrading the near-optimality guarantees of the algorithm.
	
	}%========================================================================================================================================	
	\end{document}