\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
	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{ada}
	
	\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}(aI + \Phi S \Phi) = [a + \lambda_min(\Phi S \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}(aI + \Phi S \Phi) <= min(1/a, [(1-\beta)\lambda_min(\Sigma)]^{-1}) = min(1/a, [\lambda_min(S)]^{-1})$, since $a = \beta \lambda_min(\Sigma)$ so that $(1-\beta)\lambda_min(\Sigma) = \lambda_min(\Sigma) - a = \lambda_min(S)$. I'd ask that the authors recheck their proof to make sure it holds and if so, give more details on these steps. 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 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.}
	
	\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 parameter are fixed, the greedy search has linear complexity. For sensor selection applications, this is the common case, e.g., fixed number of available sensors. However, we understand your concern from the theoretical complexity perspective. Depending on the size of the input notations such as $\mathcal{O}(mn)$ might imply different things, e.g., matrix multiplication is considered \emph{linear} as the input is of size $\mathcal{O}(mn)$, while for string lookups $\mathcal{O}(mn)$ implies $\mathcal{O}(m^2)$. In the case of Mirzasoleiman et al. I would argue that their query complexity $\mathcal{O}(M\log1/\epsilon)$, in worst case is also polynomial.}
%========================================================================================================================================	
	\end{document}