text:
\begin{document}

\maketitle

\begin{abstract}
We present a nonparametric method for selecting informative
features in high-dimensional clustering problems.
We start with a screening step that uses a test for multimodality.
Then we apply kernel density estimation and mode clustering to the selected features.
The output of the method consists of a list of relevant features, and cluster assignments.
We provide explicit bounds on the error rate of the resulting clustering.
In addition, we provide the first error bounds on mode based clustering.
\end{abstract}

\section{Introduction}

There are many methods
for feature selection in
high-dimensional classification
and regression.
These methods require
assumptions such as
sparsity and incoherence.
Some methods (Fan and Lv 2008) also assume
that relevant variables
are detectable through marginal correlations.
Given these assumptions,
one can prove guarantees for the performance
of the method.

A similar theory for feature selection in clustering is lacking.
There exist a number of methods
but they do not come with precise assumptions and guarantees.
In this paper we propose a method
involving two steps:
\begin{enum}
\item A screening step to eliminate uninformative features.
\item A clustering step based on estimating the modes
of the density of the relevant features.
The clusters are the basins of attraction of the modes (defined later).
\end{enum}

The screening step uses
a multimodality test such as
the dip test from
Hartigan and Hartigan (1985) or
the excess-mass test in Chan and Hall (2010).
We test the marginal distribution of each feature
to see if it is multimodal.
If not, that feature is declared to be uninformative.
The clustering is then based on mode estimation
using the informative features.

{\em Contributions.}
We present a method for variable selection in clustering,
and an analysis of the method.
Of independent interest, we provide the first risk bounds
on the clustering error of mode-based clustering.

{\em Related Work.}
Witten-Tibshirani (2010)
propose a penalized version of $k$-means clustering,
Raftery-Dean (2006) use a mixture model with a BIC penalty,
Pan-Shen (2007)
use a mixture model with a sparsity penalty
and
Guo-Levina-Michailidis (2010)
use a pairwise fusion penalty.
None of these papers provide theoretical guarantees.
Sun-Wang-Fang (2012)
propose a $k$-means method with a penalty on the cluster means.
They do provide some consistency guarantees
but only assuming that the number of clusters $k$ is known.
Their notion of non-relevant features is different than ours;
specifically, a non-relevant feature has cluster center equal to 0.
Furthermore, their guarantees are of a different nature in that
they show consistency of the regularized k-means objective (which is NP-hard),
and not the
iterative algorithm.

{\em Notation:}
We let $p$ denote a density function,
$g$ its gradient and $H$ its Hessian.
A point $x$ is a {\em local mode} of $p$ if
$||g(x)||=0$, where throughout the paper $\|\cdot\|$ denotes
the euclidean norm, and all the eigenvalues
of $H(x)$ are negative.
In general, the eigenvalues of
a symmetric matrix $A$ are denoted by
$\lambda_1\geq \lambda_2\geq \cdots$.
We write $a_n \preceq b_n$ to mean that there is some $C>0$
such that $a_n \leq C b_n$ for all large $n$. $C,c$ will denote different constants.
We use $B(x,\epsilon)$ to denote a closed ball of radius
$\epsilon$ centered at $x$.

\section{Mode Clustering}

Here we give a brief review of mode clustering, also called mean-shift clustering;
more details can be found in Cheng (1995), Comaniciu and Meer (2002),
Arias-Castro, Mason, Pelletier (2014) and Chacon (2012).

Let $X_1,\ldots, X_n \in \mathbb{R}^d$
be random vectors
drawn from a distribution $P$
with density $p$.
We write
$X_i = (X_i(1),\ldots, X_i(d))^T$
to denote the $d$ features of observation $X_i$.
We assume that $p$ has a finite set of modes
${\cal M}=\{m_1,\ldots, m_k\}$.
The population clustering associated with $p$ is
${\cal C} = \{ {\cal C}_1,\ldots, {\cal C}_k\}$
where ${\cal C}_j$ is the basin of attraction
of $m_j$.
That is, $x\in {\cal C}_j$ if the gradient ascent curve, or flow,
starting at $x$ ends at $m_j$.
More precisely, the {\em flow}
starting at $x$ is the path
$\pi_x: \mathbb{R}\to \mathbb{R}^d$
satisfying $\pi_x(0) =x$ and
$\pi_x'(t) = \nabla p(\pi_x(t))$.
Then $x\in {\cal C}_j$ iff
$\lim_{t\to\infty}\pi_x(t)=m_j$.
Let $m(x)\in {\cal M}$ denote the mode to which $x$ is assigned.
Thus $m: \mathbb{R}^d \to {\cal M}$.
Define the clustering function
$c:\mathbb{R}^d \times \mathbb{R}^d\to \{0,1\}$ by
$$
c(x,y) =
\begin{cases}
1 & {\rm if\ } m(x) = m(y)\\
0 & {\rm if\ } m(x) \neq m(y).
\end{cases}
$$
Thus, $c(x,y)=1$ if and only if $x$ and $y$ are in the same cluster.

Now let $\hat p$ be an estimate of the density $p$
with corresponding estimated modes
$\hat{\cal M}= \{\hat m_1,\ldots, \hat m_\ell\}$,
mode assignment function $\hat m$,
and basins
$\hat{\cal C} = \{ \hat {\cal C}_1,\ldots, \hat {\cal C}_\ell\}$.
(The modes and cluster assignments can be found numerically
using the mean shift algorithm; see Cheng (1995) and
Comaniciu and Meer (2002).)
This defines a sample cluster function $\hat c$.
The clustering loss is defined to be
\begin{equation}
L = \frac{1}{\binom{n}{2}}\sum_{j < k} I \Bigl( \hat c(X_j,X_k)\neq c(X_j,X_k)\Bigr).
\end{equation}
A second loss function is the Hausdorff distance
$H(\hat{\cal M},{\cal M})$
where
$$
H(C,D) = \inf \{\epsilon: C \subset D\oplus \epsilon\ {\rm and}\
D \subset C\oplus \epsilon\}
$$
and
$A\oplus\epsilon =\cup_{x\in A}B(x,\epsilon)$.

\section{The Method}

Now we describe the steps of our algorithm.

\rule{6in}{1mm}

\noindent
\begin{enumerate}
\item
(Screening)
Let $p_j$ be the marginal density of the $j^{\rm th}$ feature.
Let $k_j$ be the number of modes of $p_j$.
We test
$$
H_0: k_j \leq 1 \ \ \ \ \ {\rm versus}\ \ \ H_1: k_j >1.
$$
The test is given in Figure \ref{fig::test}.
Let $R = \{j:\ H_0\ {\rm was\ rejected}\}$ and let
$r =|R|$.
\item
(Mode Clustering)
Let
$Y_i = (X_i(a):\ a\in R)$
be the relevant coordinates of $X_i$.
Estimate the density of $Y$
with the kernel density estimator
$$
\hat p_h(y) = \frac{1}{n}\sum_{i=1}^n \frac{1}{h^r}
K\left(\frac{||Y_i-y||}{h}\right)
$$
with bandwidth $h$.
Let $\hat {\cal M}$ be the modes
corresponding
to $\hat p_h$
with corresponding basins
$\hat{\cal C} = \{ \hat {\cal C}_1,\ldots, \hat {\cal C}_\ell\}$
and cluster function
$\hat c$.
\item Output
$\hat {\cal M}$, $R$,
$\hat m(Y_1),\ldots, \hat m(Y_n)$ and $\hat c$.
\end{enumerate}

\rule{6in}{1mm}

\begin{figure}
\centering
\fbox{\parbox{5.3in}{
\begin{center}
{\sf Test For Multi-Modality}
\end{center}
\begin{enumerate}
\item Fix $0 < \alpha < 1$. Let $\tilde\alpha = \alpha /(nd)$.
\item For each $1\leq j \leq d$,
compute $T_j = {\rm Dip}(F_{nj})$ where
$F_{nj}$ is the empirical distribution function of the $j^{\rm th}$ feature
and ${\rm Dip}(F)$ is defined in (\ref{eq::dip}).
\item Reject the null hypothesis that feature $j$ is not multimodal if
$T_j > c_{n,\tilde\alpha}$ where
$c_{n,\tilde\alpha}$ is the critical value for the dip test.
\end{enumerate}
}}
\caption{The multimodality test for the screening step.}
\label{fig::test}
\end{figure}

\subsection{The Multimodality Test}

Any test of multimodality may be used.
Here we describe the {\em dip test}
(Hartigan and Hartigan, 1985).
Let
$Z_1,\ldots, Z_n \in [0,1]$
be a sample from a distribution $F$.
We want to test
``$H_0: F$ is unimodal''
versus
``$H_1: F$ is not unimodal.''
Let ${\cal U}$ be the set of unimodal
distributions.
Hartigan and Hartigan (1985) define
\begin{equation}\label{eq::dip}
{\rm Dip}(F) = \inf_{G\in {\cal U}}\sup_x | F(x) - G(x)|.
\end{equation}
If $F$ has a density $p$ we also write
${\rm Dip}(F)$ as
${\rm Dip}(p)$.
Let $F_n$ be the empirical distribution function.
The dip statistic is
$T_n = {\rm Dip}(F_n)$.
The dip test rejects $H_0$ if
$T_n > c_{n,\alpha}$
where the critical value
$c_{n,\alpha}$ is
chosen so that, under $H_0$,
$\mathbb{P}(T_n > c_{n,\alpha}) \leq \alpha$.\footnote{
Specifically,
$c_{n,\alpha}$ can be defined by
$\sup_{G\in {\cal U}} P_G(T_n > c_{n,\alpha}) = \alpha$.
In practice,
$c_{n,\alpha}$ can be defined by
$P_U(T_n > c_{n,\alpha}) = \alpha$ where
$U$ is Unif(0,1).
Hartigan and Hartigan (1985) suggest that this suffices asymptotically.}

Since we are conducting multiple tests,
we cannot test at a fixed error rate $\alpha$.
Instead, we replace $\alpha$ with
$\tilde\alpha = \alpha/(nd)$.
That is, we test each marginal and
we reject $H_0$ if
$T_n > c_{n,\tilde\alpha}$.
By the union bound,
the chance of at least one false rejection of $H_0$ is at most
$d\tilde\alpha = \alpha/n$.

There are more refined tests such as the excess mass test
given in Chan and Hall (2010),
building on work by Muller and Sawitzki (1991).
For simplicity, we use the dip test in this paper;
a fast implementation of the test is available in R.

\subsection{Bandwidth Selection}

Bandwidth selection for kernel density estimation is an enormous topic.
A full investigation of bandwidth selection in mode clustering
is beyond the scope of this paper but here we provide some
general guidance.
We may want to choose a bandwidth that gives accurate
estimates of the gradient of the density.
Based on Wand, Duong, and Chacon (2011) this suggests
$h_n = S \left(\frac{4}{r+4}\right)^{1/(6+r)} n^{-1/(6+r)}$
where $S$ is the average of the sample standard deviations along each coordinate.
On the other hand,
in the low noise case (well-separated clusters)
we may want to choose an $h>0$
that does not go to 0 as $n$ increases.
Inspired by similar ideas used in RKHS methods
(Sriperumbudur et al. 2009)
one possibility is to take $h$ to be the 0.05 quantile
of the values $||Y_i - Y_j||$.
Finally, we note that Einbeck (2011)
has a heuristic method for choosing $h$ for mode clustering.

\section{Theory}

\subsection{Assumptions}

We make the following assumptions:

\noindent
{\bf (A1) (Smoothness)} $p$ has three bounded, continuous derivatives.
Thus, $p\in C^3$.
Also, $p$ is supported on a compact set
which we take to be a subset of
$[0,1]^d$.

\noindent
{\bf (A2) (Modes)} $p(y)$ has finitely many modes
${\cal M} = \{m_1,\ldots, m_k\}$
where $y\in\mathbb{R}^s$ is the subset of $x$ defined in (A3).
Furthermore, $p$ is a Morse function, i.e.
the Hessian at each critical point is non-degenerate.
Also, there exists $a>0$ such that
$\min_{j\neq \ell}||m_j - m_\ell|| \geq a$.
Finally,
there exits $0 < b < B < \infty$
and $\gamma>0$
such that,
\begin{equation}
-B \leq  \min_j \lambda_{s}(H(y)) \leq
\max_j \lambda_{1}(H(y)) \leq -b
\end{equation}
for all $y\in B(m_j,\gamma)$ and
$1 \leq j \leq k$.

\noindent
{\bf (A3) (Sparsity)} The true cluster function $c$
depends only on a subset of features
$S\subset\{1,\ldots, d\}$ of size $s$.
Let $y=(x(i):\ i\in s)$ denote the relevant features.

\noindent
{\bf (A4) (Marginal Signature)}
If $j\in S$, then the marginal density $p_j$
is multimodal.
In particular,
\begin{equation}
\min_{j\in S}{\rm Dip}(p_j) > \sqrt{ \frac{2c_n\log(2nd)}{n}}
\end{equation}
where $c_n$ is any slowly increasing function of $n$
(such as $\log n$ or $\log \log n$)
and
\begin{equation}
{\rm Dip}(p) = \inf_{q\in {\cal U}}\sup_x |F_p(x) - F_q(x)|
\end{equation}
where $F_p(x) = \int_{-\infty}^x p(u) du$
and ${\cal U}$ is the set of unimodal distributions.

\noindent
{\bf (A5) (Cluster Boundary Condition)}
Define the {\em cluster margin}
\begin{equation}\label{eq::boundary}
\Omega_\delta = \Biggl(\bigcup_{j=1}^k (\partial {\cal C}_j)\Biggr)\oplus \delta
\end{equation}
where
$\partial {\cal C}_j$ is the boundary of ${\cal C}_j$
and $A\oplus \delta = \bigcup_{y\in A}B(y,\delta)$.
We assume that there exists $c>0$ and $\beta\geq 1$ such that,
 for all small $\delta>0$,
$P(\Omega_\delta)\leq c \delta^\beta.$

\subsection{Discussion of the Assumptions}

Assumption (A1) is a standard smoothness assumption.
Assumption (A2) is needed to make sure that
the modes are well-defined and estimable.
Similar assumptions appear in
Arias-Castro, Mason, Pelletier (2014)
and Romano (1988), for example.
Assumption (A3) is needed in the high-dimensional setting
just as in high-dimensional regression.

Assumption (A4) is the most restrictive assumption.
The assumption is violated when clusters are very close together
and are not well-aligned with the axes.
To elucidate this assumption, consider Figure \ref{fig::marginal1}.
The left plots show a violation of (A4).
The middle and right plots show cases where the assumption holds.
It may be possible to relax (A4) but, as far as we know,
every variable selection method for clustering in high dimensions
makes a similar assumption
(although it is not always made explicit).

Assumption (A5) is satisfied with $\beta=1$
for any bounded density with cluster
boundaries are not space-filling curves.
The case $\beta >1$ corresponds to well-separated clusters.
This implies that there is not too much mass at the cluster boundaries.
This can be thought of as a cluster version of
Tsybakov's low noise assumption in classification
(Audibert and Tsybakov, 2007).
In particular,
the very well-separated case, where
there is no mass
right on the cluster boundaries,
corresponds to $\beta = \infty$.

\begin{figure}
\begin{center}
\includegraphics[scale=.3]{Marginal}
\end{center}
\caption{\em
Three examples, each showing two clusters and two features $X(1)$ and $X(2)$.
The top plots show the clusters.
The bottom plots show the marginal density of $X(1)$.
Left: The marginal fails to reveal any clustering structure.
This example violates the marginal signature assumption.
Middle:
The marginal is multimodal and hence correctly identifies $X(1)$ as a relevant feature.
This example satisfies the marginal signature assumption.
Right:
In this case, $X(1)$ is relevant but $X(2)$ is not.
Despite the fact that the clusters are close together,
the marginal is multimodal and hence correctly identifies $X(1)$ as a relevant feature.
This example satisfies the marginal signature assumption.}
\label{fig::marginal1}
\end{figure}

\subsection{Main Result}

\begin{theorem}
\label{thm::main}
Assume (A1)-(A5).
Then
$\mathbb{P}(R=S) > 1 - 2/n$.
Furthermore, we have the following:
\begin{enumerate}
\item
Let
$\eta_j = \sup_x||\hat p_h^{(j)}(x) - p^{(j)}(x)||$
where $p^{(j)}$ denotes the $j^{th}$ derivative of the density.
The cluster loss is bounded by
\begin{equation}
\mathbb{E}[L]  \leq
e^{-nc h^{s+4}} +
\left(\frac{C_1}{\log\left(\frac{C_2}{\eta_1}\right)}\right)^\beta + \frac{2}{n}
\end{equation}
where
$\eta_1 \preceq h^2 + \sqrt{\frac{\log n}{n h^{s+2}}}$.
Choosing $h_n \asymp n^{-b}$ for
$0 < b < 1/(4+s)$, we have
\begin{equation}
\mathbb{E}[L] \preceq
e^{-c n^{\omega}} +
\left(\frac{1}{\log n}\right)^\beta
\end{equation}
where $\omega = 1 - b(s+4) > 0$ and $\beta$ is a constant.
\item
(Low noise and fixed bandwidth.)
Suppose
that
$\beta \succeq \frac{2 v \log n}{\log\log (1/h^2)}.$
If $0 < h < Ca$ then
$\mathbb{E}[L]\preceq n^{-v} + c_1 e^{-n c}.$
\item Except on a set of probability at most $O(e^{-nc h^s})$,
$$
H(\hat{\cal M},{\cal M}) \preceq \sqrt{ h^2 + \sqrt{\frac{\log n}{n h^s}}}.
$$
Hence, if $h>0$ is fixed but small, the for any $K$ and large enough $n$,
$H(\hat{\cal M},{\cal M}) < \min_{j\neq k}||m_j-m_k||/K$.
If $h\asymp n^{-1/(4+s)}$, then
$H(\hat{\cal M},{\cal M}) = O( (\log n)^{1/2}/n^{\frac{1}{4+s}})$.
\end{enumerate}
\end{theorem}

The first result shows that
the clustering error depends on the number of relevant variables $s$
and on the boundary exponent $\beta$.
The second result shows that in the low noise (large $\beta$) case,
we can use a small but non-vanishing bandwidth.
In that case, the clustering error for all pairs of points
not near the boundary is exponentially small and
the fraction of points near the boundary decreases as a polynomial in $n$.
The third result shows that
the Hausdorff distance between the estimated modes and true modes
is small relative to the mode separation
with high probability even if $h$ does not tend to 0.
When $h$ does tend to 0,
the Hausdorff distance shrinks at rate
$O( (\log n)^{1/2}/n^{\frac{1}{4+s}})$.

\section{Proofs}
\vspace{-0.1in}
\subsection{Screening}

\begin{lemma}
[False Negative Rate of the dip test.]
Let $T_n$ be the dip statistic.
Let $\delta = {\rm Dip}(p)$.
Suppose that $\sqrt{n}\delta \to \infty$.
Then
$\mathbb{P}(T_n \leq c_{n,\alpha}) < 2 e^{- n\delta^2/2}$.
\end{lemma}

\begin{proof}
It follows from Theorem 3 of Hartigan and Hartigan (1985)
that $c_{n,\alpha} \sim C/\sqrt{n}$ for some $C>0$.
Since $\sqrt{n}\delta \to \infty$,
we have that the event $\{T_n \leq c_{n,\alpha}\}$
implies the event
$\{T_n \leq \delta/2\}$.
Let $F_0$ be the member of ${\cal U}$ closest to $F$ and let
$\hat F_0$ be the member of ${\cal U}$ closest to $F_n$.
Then
$T_n \leq \delta/2$ implies that
$$
\delta < \sup_x |F(x) - F_0(x)| \leq
\sup_x |F(x) - \hat F_0(x)| \leq
\sup_x |F(x) - F_n| +
\sup_x |F_n - \hat F_0(x)|  \leq
\sup_x |F(x) - F_n| + \frac{\delta}{2}
$$
and so
$\sup_x |F(x) - F_n| > \delta/2$.
In summary,
the event
$\{T_n \leq c_{n,\alpha}\}$ implies the event
$\{\sup_x |F(x) - F_n| > \delta/2\}$.
According to the Dvoretsky-Kiefer-Wolfowitz theorem,
$\mathbb{P}( \sup_x |F(x) - F_n| > \epsilon)\leq 2 e^{-2n\epsilon^2}.$
Hence,
$\mathbb{P}(T_n \leq c_{n,\alpha}) \leq
\mathbb{P}( \sup_x |F(x) - F_n| > \delta/2)\leq 2 e^{-n \delta^2/2}.$
\end{proof}

\begin{lemma}
[False negative rate: Multiple Testing Version.]
Recall that $\tilde\alpha = \alpha/(nd)$.
Let $T_n$ be the dip statistic.
Let $\delta = {\rm Dip}(p)$.
Suppose that $\sqrt{n/\log(nd)}\delta \to \infty$.
Then
$\mathbb{P}(T_n \leq c_{n,\tilde\alpha}) < 2 e^{- n\delta^2/2}$.
\end{lemma}

{\bf Proof Outline.}
As noted in the proof of the previous lemma,
it follows from Theorem 3 of Hartigan and Hartigan (1985)
that for fixed $\alpha$,
$c_{n,\alpha} \sim C/\sqrt{n}$ for some $C>0$.
The proof uses that fact that
$\sup_{0\leq x\leq 1} |\sqrt{n}(F_n(x) - x) - B(x)|\to 0$
in probability,
where $B$ is a Brownian bridge.
A simple extension, using the properties of a Brownian bridge,
shows that
$c_{n,\tilde\alpha} \sim \sqrt{\log (nd)/n}$.
The rest of the proof is then the same as the previous proof. $\Box$

\begin{lemma}
[Screening Property]
Recall that $R$ is the set of $j$ not rejected by the dip test.
Assume that
$$
\min_{j\in S}{\rm Dip}(p_j) > \sqrt{ \frac{2c_n }{n} \log(2nd)}.
$$
Then, for $n$ large enough,
$\mathbb{P}(R=S) > 1 - \frac{2}{n}.$
\end{lemma}

\begin{proof}
By the union bound and the previous lemma,
the probability of omitting any $j\in S$ is at most
$2s e^{-n\delta^2/2} < 1/n$ where
$\delta = \min_{j\in S}{\rm Dip}(p_j)$.
On the other hand,
probability of including any feature $j\in S^c$
is at most $\tilde\alpha = d\alpha/(nd) = \alpha/n < 1/n$.
\end{proof}

\subsection{Mode and Cluster Stability}

Now we need some properties of density modes.
Recall that $p\in C^3$, has $k$ modes
$m_1,\ldots, m_k$ separated by $a>0$
and by (A2),
the Hessian $H(m)$ at each mode $m$
has eigenvalues
in $[-B, -b]$ for some
$0 < b < B < \infty$.
Let
$\kappa_j = \sup_x ||p^{(j)}||$.
Since $p\in C^3$,
$\kappa_j$ is finite for
$j=0,1,2,3$.
Let $\tilde p\in C^3$ be another density.
Let
$\eta_j = \sup_x ||p^{(j)} - \tilde p^{(j)}||.$
Later, $\tilde p$ will be taken to be an estimate of $p$.
For now, it is just another density that is close to $p$.
We want to show that $\tilde p$ has similar clusters to $p$.

{\bf (A6)
Assume that
$\eta_0 < a^2/8$,
$\eta_0 < 9/(128 \kappa_3)$ and
$\eta_2 < b/2$.}

\begin{lemma}
\label{lemma::prop1}
Assume (A1) - (A6).
Then
$\tilde p$ has exactly $k$ modes
$\tilde m_1,\ldots, \tilde m_k$.
After an appropriate relabeling of the indices, we have
$\max_{1\leq j\leq k} ||m_j - \tilde m_j|| \leq  \sqrt{8\eta_0}.$
\end{lemma}

The proof is in the supplementary material.

\begin{lemma}
\label{lemma::rightmode}
Suppose that $m(x) = m_j$.
Let
$\delta = \frac{C_1}{\log\left(\frac{C_2}{\eta_1}\right)}.$
Let
$d(x) = \inf\Biggl\{||x-y||:\ y\in \bigcup_j \partial C_j\Biggr\}$
be the distance of $x$ from the cluster boundaries.
If $\sqrt{\eta_0} < C_3 a$
and if
$d(x) > \delta$,
then
$\tilde m(x) = \tilde m_j$.
\end{lemma}

\begin{proof}
There are two cases:
$x\in B(m_j,\sqrt{\epsilon})$ and
$x\notin B(m_j,\sqrt{\epsilon})$.
The more difficult case is the latter;
we omit the first case.
As $x$ is not on the boundary
and not in
$B(x,\sqrt{\epsilon})$, we have that
$||g(x)|| \neq 0$
and in particular,
$||g(x) || \geq \frac{C_4}{\log\left(\frac{C_2}{\eta_1}\right)}.$
Fix a small $\epsilon >0$.
There exists $t_\epsilon$,
depending on $x$, such that
$\pi_x(t_\epsilon)\in B(m_j,C_2\sqrt{\epsilon})$.
From Lemma \ref{lemma::boundary} below, we have
$$
t_\epsilon \leq
\frac{C_5}{||g(x_0)||} +
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b}.
$$
From this, it follows that
$\epsilon + 2\eta_0 +  \frac{\kappa_1}{\sqrt{d}\kappa_2}\eta_1 e^{\sqrt{d}\kappa_2 t_\epsilon} < C_6$
for $C_6 < \infty$.
This equation implies,
from the proof of Theorem 2 of Arias-Castro et al,
that
$||\lim_{t\to\infty}\tilde\pi_x(t) - m_j||\leq C_4 \sqrt{\eta_0}$.
Since $C_4 \sqrt{\eta_0} < a$, when $\eta_0$ is small enough
we conclude that
$\lim_{t\to\infty}\tilde\pi_x(t) = \tilde m_j$.
\end{proof}

\begin{lemma}
\label{lemma::boundary}
Consider the flow $\pi$ starting at a point $x_0$
and ending at a mode $m$.
For some $C_6>0$,
$$
t_\epsilon \leq
\frac{C_6}{||g(x_0)||} +
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b}.
$$
\end{lemma}

The proof is in the supplementary material.

The next lemma shows that if $x$ and $y$ are in the same cluster
and not too close to a cluster boundary,
then $x$ and $y$ are also in the same cluster relative to $\tilde p$.

\begin{lemma}
\label{lemma::prop2}
Suppose that (A1)-(A6) holds and that
$\sqrt{\eta_0} < C_4 a$.
Suppose that
$x,y \in {\cal C}_j$ and hence
$m(x) = m(y)=m_j$ and
$c(x,y) =1$.
Furthermore,
suppose that
$x,y \notin \Omega_\delta$.
(Recall that $\Omega_\delta$ is defined in (\ref{eq::boundary}).)
Then
$\tilde m(x) = \tilde m(y) = \tilde m_j$ and so
$\tilde c(x,y) =1$.
\end{lemma}

\begin{proof}
Since $x,y \notin \Omega_\delta$,
from the definition of $\delta$
and
from Lemma
\ref{lemma::rightmode}
it follows
that
$\lim_{t\to\infty}\tilde \pi_x(t) = \tilde m_j$
and
$\lim_{t\to\infty}\tilde \pi_y(t) = \tilde m_j$.
\end{proof}

Next we show that if $x$ and $y$ are in different clusters
and not too close to a cluster boundary,
then $x$ and $y$ are in different clusters under $\tilde p$.
The proof is basically the same as the last proof and so is omitted.

\begin{lemma}
\label{lemma::prop3}
Assume that same conditions as in the previous lemma.
Suppose that
$m(x) = m_j$,
$m(y) = m_s$ with $s\neq j$.
Hence, $c(x,y) =0$.
Furthermore,
suppose that
$x,y \notin \Omega_\delta$.
Then
$\tilde m(x) = \tilde m_j$,
$\tilde m(x) = \tilde m_s$,
and
$\tilde c(x,y) =0$.
\end{lemma}

\subsection{Proof of Main Theorem}

We have already shown that $R=S$
except on a set of probability at most $2/n$.
Assume in the remainder of the proof that $R=S$.

Now
$\mathbb{E}[L] = (\binom{n}{2})^{-1}\sum_{j<k} \mathbb{E}[I_{jk}]$
where
$I_{jk}= I \Bigl( \hat c(X_j,X_k)\neq c(X_j,X_k)\Bigr).$
Let
$\delta = C_1/\log(C_2/\eta_1)$.
Then
$$
\mathbb{E}[I_{jk}] \leq
\mathbb{E}[I_{jk} I( (X_j,X_k)\in \Omega_\delta^c)] + \mathbb{P} ((X_j,X_k)\notin \Omega_\delta^c).
$$
Consider
$(X_j,X_k)\in \Omega_\delta^c$;
then
$I_{jk}=0$ if
$\hat p_h$ satisfies (A6) and the condition of Lemma
\ref{lemma::rightmode}.
In other words,
$I_{jk}=0$ if,
$\sqrt{\eta_0} < C_8 a$ and
$\eta_2 < b/2$ where
$\eta_0 = \sup_x||\hat p_h(x) - p(x)||$ and
$\eta_2 = \sup_x||\hat p_h^{(2)}(x) - p^{(2)}(x)||$.
Let $p_h$ be the mean of $\hat p_h$.
Then
$\eta_0 \leq  \sup_x|| p_h(x) - p(x)|| + \sup_x|| \hat p_h(x) - p_h(x)||$.
The first term is $O(h^2)$ which is less than
$C_8^2a^2/2$ for small $h$.
By standard concentration of measure results,
$$
\mathbb{P}(\sup_x|| \hat p_h(x) - p_h(x)|| > \epsilon) \preceq
e^{-nc h^s \epsilon^2}
$$
where $c>0$ is a constant whose value may change in different expressions.
So
$$
\mathbb{P}(\sqrt{\eta_0} > C_8 a)\leq
\mathbb{P}(\sup_x|| \hat p_h(x) - p_h(x)|| > C_8^2 a^2/2) \leq
e^{-nc h^s}.
$$
A similar analysis for $\eta_2$ yields
$\mathbb{P}(\sqrt{\eta_0} > b/2) \leq
e^{-nc h^{s+4} b^2/4}.$
Therefore,
$\mathbb{E}[I_{jk} I( (X_j,X_k)\in \Omega_\delta^c)] \preceq e^{-nc h^{s+4}}.$
Now
$\mathbb{P} ((X_j,X_k)\notin \Omega_\delta^c) \preceq
P(\Omega_\delta) \preceq \delta^\beta.$
With high probability,
$$
\eta_1 =
O\left( h^2 + \sqrt{\frac{\log n}{n h^{s+2}}}\right).
$$
Hence, if $h=n^{-b}$,
$\delta^\beta \preceq (1/\log n)^\beta$.

The second statement follows from the first
by inserting a small fixed $h>0$ and
noting that
the fraction of points
near the boundary is
$\theta_n = O_P(\delta^\beta) = O_P(1/n^v)$
due to the condition on $\beta$.

For the third statement,
note that once $\eta_0$ is small enough,
the previous results imply that
${\cal M}$ and
$\hat{\cal M}$
have the same cardinality.
In this case, the Hausdorff distance is, after relabelling the indices,
$H(\hat{\cal M},{\cal M}) = \max_j ||\hat m_j - m_j||$.
Once $\eta_0$ is small enough,
Lemma \ref{lemma::prop1} implies
$\max_j ||\hat m_j - m_j|| \leq \sqrt{8 \eta_0}$.
The result follows from the bounds on $\eta_0$ above.
$\Box$

\section{Example}
\vspace{-0.1in}
\begin{figure}
\begin{center}
\begin{tabular}{ccc}
\includegraphics[scale=.2]{Aplot_screen_alt_rate} &
\includegraphics[scale=.2]{Aplot_screen_overallerror} &
\includegraphics[scale=.2]{Bplot_msr}\vspace{-0.1in}
\end{tabular}
\end{center}
\caption{Left: false negative rate as a function of $\alpha$.
Middle: overall screening error rate.
Right: Final clustering based on relevant features.}\vspace{-0.1in}
\label{fig::example}
\end{figure}

In this section we give a brief
example of the proposed method.
First, we show the type II error (false negative rate)
of the dip test as a function of $\alpha$.  We use a version of the test implemented in the R package
{\em diptest}.
We take
$P=\frac{1}{2}\mathcal{N}(0,1)+\frac{1}{2}\mathcal{N}(4,1)$.  For a
range of values for $n$, we draw $n$ samples from the mixture $10000$
times.
The left plot in Figure \ref{fig::example} shows the fraction of
times the dip test failed to detect multimodality at the specified
values for $\alpha$.  The increase in the sample size required for a
certain power appears to be at most logarithmic in $1/\alpha$.

We show the overall error rate of the support estimation procedure
in the middle plot in Figure \ref{fig::example} for the following multivariate
distribution.  For given values of $d$ and $s$, we use the Gaussian
mixture
$\frac{1}{2}\mathcal{N}(0,I)+\frac{1}{2}\mathcal{N}(4\mu_{s,d},I)$,
where $\mu_{s,d}\in\mathbb{R}^d$ contains $s$ ones followed by $d-s$
zeroes, so that the true support is $S=\{1,\ldots,s\}$.
The plot shows the fraction of times the estimated
support $\widehat{S}$ did {\em not} exactly recover $S$ in $50$
replications of the experiment for each combination of parameters.  We
set $\alpha=0.1$ (and $\widetilde{\alpha}=\alpha/(nd)$).  All the
errors were due to incorrectly removing one of the multimodal
dimensions -- in other words, in every single instance it was the case
that $\widehat{S}\subseteq S$.
This is not surprising since the dip test can be conservative.

Finally, we apply the full method to a $d=20$ dimensional data set
distributed in the first two dimensions according to the Gaussian
mixture
$$
\frac{2}{8}\mathcal{N}\left(\left(\begin{array}{c}0\\0\end{array}\right),
\left(\begin{array}{cc}0.3&0.3\\0.3&2\end{array}\right)\right) +
\frac{3}{8}\mathcal{N}\left(\left(\begin{array}{c}3\\0\end{array}\right),
\left(\begin{array}{cc}0.6&-0.4\\-0.4&1\end{array}\right)\right) +
\frac{3}{8}\mathcal{N}\left(\left(\begin{array}{c}0\\5\end{array}\right),
\left(\begin{array}{cc}0.45&0.45\\0.45&1.6\end{array}\right)\right),
$$
and according to independent standard Gaussians in the remaining
$d-s=18$ dimensions.  We sample $n=1000$ points, and correctly
recover the multimodal features using $\alpha=0.1$.  The results of
the subsequent mean shift clustering using $h=0.06$ are shown in
Figure \ref{fig::example}, along with contours of the true density.

\section{Conclusion}
\vspace{-0.1in}
We have proposed a new method for
feature selection in high-dimensinal clustering problems.
We have given bounds on the error rate
in terms of clustering loss and Hausdorff distance.
In future work, we will address the following issues:
\begin{enum}
\item The marginal signature assumption (A4) is quite strong.
We do not know of any feature selection method for clustering
that can succeed without some assumption like this.
Either relaxing the assumption or proving that it is necessary
is a top priority.
\item The bounds on clustering loss can probably be improved.
This involves a careful study of the properties of the flow near cluster boundaries.
\item We conjecture that the Hausdorff bound is minimax.
We think this can be proved using techniques like those in
Romano (1988).
\end{enum}

\section*{Acknowledgements}
This research is supported in part by NSF awards IIS-1116458 and CAREER IIS-1252412.

\subsubsection*{References}

\small{
[1] Arias-Castro, Mason, Pelletier (2013).
On the estimation of the gradient lines of a density
and the consistency of the mean-shift algorithm.
Manuscript.

[2] Audibert, Jean-Yves, and Alexandre B. Tsybakov. (2007).
Fast learning rates for plug-in classifiers.
{\em The Annals of Statistics}, 35, 608-633.

[3] Chacon, J. (2012).
Clusters and water flows: a novel approach to modal clustering through Morse theory.
arxiv:1212.1384.

[4] Chan, Yao-ban, and Peter Hall. (2010).
Using evidence of mixed populations to select variables for clustering very high-dimensional data.
{\em Journal of the American Statistical Association}, 105, 798-809.

[5] Cheng, Yizong. (1995).
Mean shift, mode seeking, and clustering.
{\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
17, 790-799.

[6] Comaniciu, Dorin, and Peter Meer. (2002).
Mean shift: A robust approach toward feature space analysis.
{\em IEEE Transactions onPattern Analysis and Machine Intelligence}, 24, 603-619.

[7] Einbeck, Jochen. (2011).
Bandwidth selection for mean-shift based unsupervised learning techniques: a unified approach via self-coverage.
Journal of pattern recognition research. 6, 175-192.

[8] Fan, Jianqing, and Jinchi Lv. (2008).
Sure independence screening for ultrahigh dimensional feature space.
{\em Journal of the Royal Statistical Society: Series B}, 70, 849-911.

[9] Guo, Jian, et al. (2010).
Pairwise Variable Selection for
High-Dimensional Model-Based Clustering.
{\em Biometrics}, 66, 793-804.

[10] Hartigan, John A., and P. M. Hartigan. (1985).
The dip test of unimodality.
{\em The Annals of Statistics}, 13, 70-84.

[11] Muller, Dietrich Werner, and Gunther Sawitzki. (1991).
Excess mass estimates and tests for multimodality.
{\em Journal of the American Statistical Association},  86, 738-746.

[12] Pan, W. and Shen, X. (2007).
Penalized model-based clustering with application to variable selection.
{\em The Journal of Machine Learning Research}, 8, 1145-1164.

[13] Raftery, Adrian E., and Nema Dean. (2006).
Variable selection for model-based clustering.
{\em Journal of the American Statistical Association}, 101, 168-178.

[14] Romano, J. (1988).
On weak convergence and optimality of kernel density estimates of the mode.
{\em The Annals of Statistics} 16, 629-647.

[15] Sriperumbudur, Bharath K., et al. (2009).
Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions. NIPS.

[16] Sun, W., Wang, J. and Fang, Y. (2012).
Regularized k-means clustering of high-dimensional data and its asymptotic consistency.
{\em Electronic Journal of Statistics}, 6, 148-167.

[17] Wand, M. P., Duong, T. and Chacon, J. (2011).
Asymptotics for general multivariate kernel density derivative estimators.
{\em Statistica Sinica}, 21, 807-840.

[18] Witten, Daniela M., and Robert Tibshirani. (2010).
A framework for feature selection in clustering.
{\em Journal of the American Statistical Association},  105, 713-726.

\newpage

\begin{center}
{\bf Appendix}
\end{center}

{\bf Proof of Lemma \ref{lemma::prop1}.}
Let $g$ and $H$ be the gradient and Hessian of $p$ and let
$\tilde g$ and $\tilde H$ be the gradient and Hessian of $\tilde p$.
Let $m$ be a mode of $p$ and let
$B = B(m,\epsilon)$ be a closed ball around $m$ where $\epsilon = \sqrt{8\eta_0}$.
The ball excludes any other mode of $p$ since
$\sqrt{8\eta_0} < a$.
Expanding $p$ at $x\in B$ we have
\begin{equation}\label{eq::Taylor}
p(x) = p(m) + \frac{1}{2} (x-m)^T H(m) (x-m) + R(x)
\end{equation}
where
$|R(x)| \leq \kappa_3 ||x-m||^3/6$.

Since $\tilde p$ is bounded and continuous,
it has at least one maximizer $\tilde m$ over $B$.
We now show that $\tilde m$ must be in the interior of $B$.
Let $0 < \alpha < \beta < 1$ and
write
$B = A_0 \bigcup A_1 \bigcup A_2$ where
$A_0 = \{x:\ ||x-m|| \leq \alpha\epsilon\}$,
$A_1 = \{x:\ \alpha\epsilon < ||x-m|| \leq \beta\epsilon\}$,
$A_2 = \{x:\ \beta\epsilon < ||x-m|| \leq \epsilon\}$.
For any $x\in A_0$, by (\ref{eq::Taylor}),
$$
\tilde p(x) \geq
p(x) -\eta_0 \geq
-\frac{B}{2}\alpha^2 \epsilon^2 - \frac{\kappa_3 \alpha^3\epsilon^3}{6} - \eta_0.
$$
For any $x\in A_2$,
$$
\tilde p(x) \leq
p(x) +\eta_0 \leq
-\frac{b}{2}\beta^2 \epsilon^2 + \frac{\kappa_3 \beta^3\epsilon^3}{6} + \eta_0.
$$
Then if
\begin{equation}\label{eq::alphabeta}
\frac{\epsilon^2}{2}[b \beta^2 - B \alpha^2] -
\frac{\kappa_3 \epsilon^3 (\alpha^3 + \beta^3)}{6} > 2\eta_0
\end{equation}
we will be able to conclude that
$$
\inf_{x\in A_0}\tilde p(x) > \sup_{x\in A_2}\tilde p(x).
$$
Choose $\alpha$ and $\beta$ to satisfy
$(\alpha/\beta) = \sqrt{b/B}$ and
$\kappa_3 \epsilon(\alpha^3+\beta^3)/6 < 1/4$.
It follows that
(\ref{eq::alphabeta}) holds
and so
$\inf_{x\in A_0}\tilde p(x) > \sup_{x\in A_2}\tilde p(x)$.
Hence,
any maximizer of $\tilde p$ in $B$
is in $A_0$ and hence is interior to $B$.
It follows that
$\tilde g(\tilde m) = (0,\ldots, 0)^T$.
Also,
$$
\lambda_1(\tilde H(\tilde m)) \leq
\lambda_1(H(\tilde m)) \leq - b + \eta_2 < - b/2
$$
since $\eta_2 < b/2$.
Hence,
$\tilde p$
has a local mode $\tilde m$ in the interior of $B$ with zero gradient and
negative definite Hessian.

Now we show that
$\tilde m$ is unique.
Suppose $\tilde p$ has two modes
$x$ and $y$ in the interior of $B$.
Recall that the exact Taylor expansion of a vector-valued function $f$ is
$f(a+t) = f(a)+ t^T \int_0^1 D f(a+ut)du$.
So,
$$
(0,\ldots, 0)^T =
\tilde g(x) - \tilde g(y)=
(y-x)^T\int_0^1 \tilde H(x + u(y-x)) du.
$$
Multiple both sides by $y-x$ and conclude that
\begin{align*}
0 &=
\int_0^1 (y-x)^T \tilde H(x + u(y-x)) (y-x) du \leq
||y-x||\sup_u \lambda_1(\tilde H(x + u(y-x)))\\
& \leq
||y-x||\sup_u [\lambda_1(H(x + u(y-x))) + \eta_2]\\
& \leq
||y-x||\ [- b + \eta_2] < - \frac{ b ||y-x||}{2}
\end{align*}
which is a contradiction.

Now we show that
$\tilde p$ has no other modes.
Let
$B_j = B(m,\epsilon_j)$
and suppose that
$\tilde p$ has a local mode at
$x\in \left(\bigcup_{j=1}^k B(x_j,\epsilon)\right)^c$.
By a symmetric argument to the one above,
$p$ also must have a local mode
in $B(x,\epsilon)$.
This contradicts the fact that
$m_1,\ldots, m_k$ are the unique modes of $p$. $\Box$

\vspace{1cm}

{\bf Proof Outline for Lemma \ref{lemma::boundary}.}
By assumption, $p(x)$ can be approximated by a quadratic
in a neighborhood of $m$.
Specifically,
we have that
$p(x) = p(m) - (1/2) (x-m)^T H (x-m) + R$
where $H = H(m)$ and
$|R| \leq ||x-m||^3 \kappa_3/6$.
There exists $c_1$ such that,
if
$||x-m|| \leq c_1$
then
$||x-m||^3 \kappa_3/6$ is much smaller than
$B ||x-m||^2/2$ and hence
the quadratic approximation
$p(x) \approx p(m) - (1/2) (x-m)^T H (x-m)$
is accurate.

Case 1: $||x_0-m|| \leq c_1$.
In this case, the proof of Lemma 5 of Arias-Castro et al shows that
$\pi(t) - m = e^{tH}(x_0-m) + \xi$
where
$\xi = O(||x-m||^3 \kappa_3/6)$ and so
$\pi(t) - m \approx e^{tH}(x_0-m)$.
In particular,
$\pi(t_\epsilon) - m \approx e^{t_\epsilon H}(x_0-m)$ and thus
$$
\sqrt{\epsilon} \approx ||e^{t_\epsilon H}||\ ||x_0-m|| \leq e^{-b t_\epsilon} ||x_0-m||
$$
so that
$e^{-b t_\epsilon} \geq \frac{\sqrt{\epsilon}}{||x_0-m||}$
and so
$$
t_\epsilon \leq
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b} \leq
\frac{C_6}{||g(x_0)||} +
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b}.
$$

Case 2: $||x_0-m|| > c_1$.
In this case, the starting point $x_0$
is not in the quadratic zone.
There exists $t_1<\infty$
(not depending on $\epsilon$)
such that
$||\pi(t_1)-m||\leq c_1$.
Let us first bound $t_1$.
Since
$\pi'(t) = g(\pi(t))$
we have
$\pi(t) = \int_0^t g(\pi(s)) ds + x_0$ and thus
$\pi(t_1) - x_0 = \int_0^{t_1} g(\pi(s)) ds.$
Now
$g(x) = g(x_0) + H_s(x-x_0)$
where $H_s$
is the Hessian evaluated at some point between $x_0$ and $\pi(s)$.
Thus,
$\pi(t_1) - x_0 = t_1 g(x_0) +
\int_0^{t_1} H_s(x(s)-x_0) ds$
and therefore
$t_1 g(x_0) =
\pi(t_1) - x_0 - \int_0^{t_1} H_s(\pi(s)-x_0) ds.$
It follows that
$$
t_1 ||g(x_0)|| \leq
||\pi(t_1) - x_0|| + \int_0^{t_1} ||H(\pi(s)-x_0)|| ds \leq
||m - x_0|| + \int_0^{t_1} ||H(\pi(s)-x_0)|| ds
$$
and
$$
t_1 \leq \frac{||m - x_0|| + \int_0^{t_1} ||H(\pi(s)-x_0)|| ds }{||g(x_0)||} \equiv
\frac{C_6}{||g(x_0)||}.
$$
Now consider the flow $\tilde \pi$ starting at $x_1$.
This is the same as the original flow except starting at $x_1$ rather than $x_0$.
There exists $\tilde t_\epsilon$ on this flow such that
$t_\epsilon = t_1 + \tilde t_\epsilon$.
Applying case 1,
$$
\tilde t_\epsilon \leq
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_1-m||}{b} \leq
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b}.
$$
Thus,
$$
t_\epsilon =
t_1 + \tilde t_\epsilon \leq
\frac{C_6}{||g(x_0)||} +
\frac{\frac{1}{2}\log(1/\epsilon) + \log ||x_0-m||}{b}.\ \ \ \Box
$$

\end{document}


TITLE: Is a function globally Lipschitz continuous and $\mathcal{C}^1$ if and only if it is $\mathcal{C}^1$ and its total derivative is bounded?
QUESTION [6 upvotes]: Is $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ globally Lipschitz continuous, i.e. there exists an $L>0$ such that
$\frac{|f(x)-f(y)|}{|x-y|}\leq L$ for all $x,y\in\mathbb{R}^n$,
and $\mathcal{C}^1$ if and only if $f$ is $\mathcal{C}^1$ and its total derivative is bounded?
Based on intuition alone, I'm strongly inclined to believe that the answer is yes. However I'm having trouble coming up with a proof (probably because my grasp of multivariable calculus is far from great). Could someone give one if the statement is true, or provide a counter example if it is false?
Thanks.

REPLY [7 votes]: If $f$ is $\mathscr{C}^1$, then $f(x) - f(y) = \int_0^1 Df(y + t(x-y)).(x-y) dt$, by the fundamental theorem of calculus.
Hence, $$\begin{aligned} \| f(x) - f(y) \| &\le& &\int_0^1 \|Df(y+t(x-y)).(x-y) \| dt& \\ &\le& &\left( \int_0^1 \| Df( y + t(x-y) )\| dt \right) \| x-y \|& \le \sup_{z \in \mathbb{R}^n} \, \|Df(z) \| \; \| x-y \| \end{aligned}$$
If $\sup_{z \in \mathbb{R}^n} \, \| Df(z) \| = C$ is finite, we get $\| f(x) - f(y) \| \le C \|x - y \|$ for all $x,y$.
Reciprocally, suppose that your function is $\mathscr{C}^1$ and that it's globally Lipschitz, with constant $C$.
Then, for all $x \in \mathbb{R}^n$, and all $h \in \mathbb{R}^n$, we know that $$Df(x).h = \lim_{t \to 0} \frac{f(x+th) - f(x)}{t}$$
But, by assumption, $\| f(x +th) - f(x) \| \le C \|th \| = C  |t| \|h\|$, and we finally get  $\|Df(x).h \| \le C \|h \|$ for all $h$, which by definition implies $\| Df(x) \| \le C$. Hence the total derivative is bounded all over $\mathbb{R}^n$.
All of this works also on an open set of $\mathbb{R}^n$, instead of the whole space.
Remark also that you don't need to assume $f$ to be $\mathscr{C}^1$, but only differentiable. The second part of my proof works as well, and for the first part, instead of applying fundamental theorem of calculus, you can use the mean value theorem.


TITLE: Anomaly in Curl Computation
QUESTION [0 upvotes]: Suppose computing the 3D curl of a vector field involves finding this determinant:
$$
\mathrm{det} \begin{bmatrix}
\mathbf{\hat{i}} & \frac{\partial}{\partial x}   & 7y^3z^2 \\
\mathbf{\hat{j}} & \frac{\partial}{\partial y}  & xyz \\
\mathbf{\hat{k}} & \frac{\partial}{\partial z}  & -3x-z
\end{bmatrix}
$$
Using cofactor expansion, we should be able to break this into the subdeterminants obtained by excluding any row or column of our choice.  However, if we choose the right column, the determinant will incorrectly appear as $(7y^3z^2 - xyz + (-3x - z))\mathbf{0} = \mathbf{0}$, the zero vector.
This is because the unit vectors have nothing but constant entries, thus their partial derivatives will always equal $\mathbf{0}$.  Choosing the left column is the sane route, while choosing the middle column appears to work, but choosing the right column leads to a different result.  How is this consistent with the typical rules of determinants?

REPLY [1 votes]: If you're going to use this method, you have to be careful to preserve the order of the terms at all times, because the "multiplication" is not commutative in this context! You must have a unit vector, followed by a partial derivative, followed by one of the polynomials in the right column. The partial derivative applies only to the polynomial, not to the unit vector. The unit vector just comes along for the ride. In particular, the following is incorrect:

This is because the unit vectors have nothing but constant entries, thus their partial derivatives will always equal the 0 vector.

Let's say we exclude the right column, as you did. Then, for the $7x^2y^2$ term, the correct computation is:
$$j \frac{\partial}{\partial z} 7x^2y^2 - k \frac{\partial}{\partial y} 7x^2y^2$$
which equals $-k (14x^2y)$.
Now repeat for the other two factors in the third column.


text:
\begin{document}
	\subsection{Proof of Theorem \ref{thm:SSA-rank-condition}}
	\label{sec:proof:thm-relaxed-rank-is-enough}
	\begin{proof}
		Consider a Subset Select algorithm $ ALG $ that satisfies the theorem conditions. We use the notations $ \algS, C$ and $ M $ as in the theorem statement.
		We now define an algorithm $ ALG' $ for the QGT problem.
		Given a problem instance $ (A,y,k) $, $ ALG' $ returns the outcome of  Recover-From-Submatrix (see Algorithm \ref{alg:recover-D-from-S}) on the problem instance $ (A,y,k) $ together with $ S:=\algS $ (the outcome of $ ALG $ on this problem instance).
		\begin{algorithm}[!htbp]
			\caption{Recover-From-Submatrix}
			\label{alg:recover-D-from-S}
			\begin{algorithmic}
				\STATE \textbf{Input:} QGT problem instance $ (A,y,k) $ and a subset $ S = \left\{s_1, s_2, \ldots, s_{|S|}\right\} $
				\begin{enumerate}
					\item Using Gaussian elimination, compute the {reduced-row-echelon\footnotemark} form of the system of linear equations $ \left(A|_S\right)z'=y $ and denote it by $ Bz'= v $
					\item Denote by $ F \subseteq [n] $ the indices of all {free-variables\footnotemark}
					in $ Bz'=v $
					\item For every subset $ P \subseteq F $ do: \label{alg:line:for-loop}
					\begin{enumerate}
						\item Check if the (unique) solution of following is binary:
						\label{alg:line:consistent-check}
						\begin{equation*}
						\begin{split}
						Bz'=v \\
						z'_i=1 &  \text{  }\forall i \in P \\
						z'_i=0 &  \text{  }\forall i \in F \setminus P \\
						\end{split}
						\end{equation*}
						\item If $ z' \in \{0,1\}^{|S|} $ and of Hamming weight $ k $, return $ \algS := \{s_i : z'_i = 1\} $
					\end{enumerate}
				\end{enumerate}
			\end{algorithmic}
		\end{algorithm}
			\addtocounter{footnote}{-1}
	\footnotetext{
		A matrix is in \emph{reduced row echelon} form if: all rows consisting of only zeroes are at the bottom; the leading coefficient of a nonzero row equals $ 1 $ and is strictly to the right of the leading coefficient of the row above it; the column containing this leading $ 1 $ coefficient has zeros in all its other entries.
	}
	\addtocounter{footnote}{+1}
	\footnotetext{
		The columns that don't correspond to any row with a leading $ 1 $ coefficient are \emph{free variables}.
	}

		In the following we will show that $ ALG' $ is an algorithm for the QGT problem which fulfill the theorem statement.
		Recall that $ \Mqgt $ is the information theoretic threshold defined in the beginning of Section \ref{sec:introduction} and assume that $ m>\max(M,M_{QGT}) $.
		For a QGT problem instance $ (A,y,k) $, we will show that if \whp $ \D\subseteq \algS $ and $ \rankof{A|_{\algS}} > |\algS|-C\log n $ then \whp $ ALG' $ recovers $ \D $ in polynomial-time.

		By the definition of $ M_{QGT} $, \whp there exists a unique solution $ z \in \{0,1\}^n $ of Hamming weight $ k $ for the system of linear equations $ Az = y $.
		Namely, if such a vector $ z $ is a solution for $ Az = y $, then \whp it equals $ x $.
		When Algorithm \ref{alg:recover-D-from-S} does not fail, it outputs a subset $ S \subseteq [n] $.
		Observe that $ S $ is such that $ \one_{S} \in \{0,1\}^n $ is a solution of Hamming weight $ k $ for this system of linear equations.
		Therefore, if the algorithm returns a solution then it is \whp correct.
		Assume that $ \D \subseteq \algS $, then there is a binary solution to the system of linear equations $ Bz'=v $ of Hamming weight $ k $.
		Note that the algorithm goes over all possibly binary solutions of $ Bz' = y $.
		Therefore, if \whp $ \D \subseteq \algS $ and $ \rankof{A|_\algS}>|\algS|-C\log n $, then the algorithm $ ALG' $ recovers $ \D $ \whp.

		We are left to show that the algorithm returns a solution within the required time complexity.
		Recall that Gaussian elimination algorithm time complexity is $ O(m^3) $.
		Because the rank of $ A|_S $ is not smaller than $ |S| - C\log n $ there are at most $ C\log n $ free variables in $ Bz' = v $, i.e., $ |F| \leq C \log n $.
		Hence, the exhaustive search (in line \ref{alg:line:for-loop}) goes over $ 2^{|F|}\le n^C $ different systems of linear equations.
		Because the matrix $ B $ is of a row-echelon form with $ m $ equations and at most $ C\log n $ free variables, it takes to check the condition at line \ref{alg:line:consistent-check} only $ O(m\log n) $ operations. Hence, we get the required time complexity.
	\end{proof}

	\begin{remark}
		We can replace $ {O}(m^3 +n^c m \log n) $ with $ \tilde{O}(n^c T(m)) $, where $ T(m) $ is the computational complexity of solving a system of linear equations with m linear equations and m unknowns.
	\end{remark}

	\subsection{Proof of Lemma \ref{SSA:lem:conditions}}
	\label{sec:proof:lem-conditions}
	\begin{proof}
		Fix $ \D $. We will prove separately, that if either of the conditions stated in Lemma \ref{SSA:lem:conditions} holds, the submatrix $ A|_\algS $ has rank of at most $ |\algS| - C \log n $.

		\emph{Condition 1}.
		Suppose that the first condition holds.
		Recall that by the definition of the Subset Select problem we have that $ |\algS| \le m $ and consider a non-defective items subset $ S \subseteq \notD $ of cardinality $ \min (k, m-k) $.
		Denote by $ L_{S} $ the event that the columns of $ \D \cup S $ in the test matrix are linearly dependent (i.e., the event that $ \rankof {A|_{\D\cup S}} < |S\cup \D| $).
		By \cite{tikhomirov2018singularity}, the probability of a random Bernoulli matrix $ B\in\{0,1\}^{m\times m} $ to be singular is bounded above by $ (\nhalf + o(1))^m $.
		Therefore and because $ |S\cup\D|\le m $, we have that:
		\begin{equation}\label{SSA:lem-proof:eq:L_S-bound}
			\Pr[L_S] = \Pr[\rankof{A|_{S\cup \D}<|S\cup \D|}] \le \left (\nhalf+o(1)\right )^{-m}.
		\end{equation}
		By using a union bound, the probability that one of the bad events in $ \{L_S \;|\; S \subseteq \notD \;, |S|= \min (k, m-k)  \} $ did occur is bounded by
		\begin{equation*}
			\Pr \left[\bigvee_S L_S \right]
			\le {n-k \choose \min (k, m-k)} \left (\nhalf+o(1)\right )^{-m}.
		\end{equation*}
		By the definition of $ \hat{M}_{QGT} $, there exists some $ \epsilon_n  \rightarrow 0$ such that for $ m \geq  (1+\epsilon_n)\hat{M}_{QGT}$ we have
		\begin{equation}
			\label{SSA:lem-proof:eq:union-L_S-bound}
			\Pr \left[\bigvee_S L_S \right]
			\le o(1).
		\end{equation}
		Hence, for every subset $ S $ with $ \D \subseteq S $ and $ |S| \le 2k $, we have that \whp $ {\rankof{A|_{S}}} = |S| $.

		By the Condition 1 assumption $ ALG $ solves \whp the Subset-Select problem for $ m>M \ge (1+\epsilon_n)\hat{M}_{QGT}  $ and its outcome $ \algS $ is of cardinality at most $ 2k $.
		Therefore, we conclude that the theorem statement holds for  Condition 1 with $ C=0 $.

		\emph{Condition 2}. Assume that the second condition holds.
			In the following we show that for $ 1 \le t  \le m-k$ the probability that $ A|_{\algS} $ is of rank less than $ m -t $ is bounded above by $ {n \choose t}2^{-t^2} +o(1)$. By assigning $ t=\log n $ the proof will follow.

			Denote by $ B $ the bad event $ \rankof{A|_{\algS}} < m -t $
			and, for this proof only, we use the notation $ A_S $ to describe the following set of vectors
			$$ A_S := \{A_i | i\in S\}, $$
			where $ A_i $ is the $ i $th column.
			It is then that $ \langle A_S \rangle $ is the vector space spanned by the columns of $ S $ in the test matrix $ A $.

			Note that when $ B $ occurs there are $ t $ columns in $ A|_{\algS} $ that are linearly dependent on the other columns.
			Formally, there exist a subset $ T\subseteq [n] $ of cardinality $ t $ such that
			\begin{equation}\label{SSA:lem-2:eq:B_S-condition}
				T\subseteq\algS \;\text{ and }\; \langle A_T \rangle \subseteq \langle A_{\algS \setminus T} \rangle.
			\end{equation}

			Towards a union bound argument, we provide a cover of the event $ B $.
			For every subset $ T \subseteq [n] $ of cardinality $ t $, denote by $ B_T $ the event that (\ref{SSA:lem-2:eq:B_S-condition}) has happened.
			From the above, note that
			\begin{equation*}
			\Pr[B] = \Pr\left[\bigvee_T B_T\right].
			\end{equation*}

			We now give a brief overview of the rest of this proof.
			First, we get rid of each event $ B_T $ for which $ T \cap \D \neq \emptyset $ by showing that, \whp, if $ B_T $ occurs for some $ T \cap \D \neq \emptyset $, then there exists a $ B_{T'} $ with $ T' \cap \D = \emptyset $ that also occurs.
			We then only need to bound events $ B_T $ with $ T \cap \D = \emptyset $.
			Consider such subset $ T \subseteq \notD $ and an assignment of columns other than $ T $.
			From the consistency of $ ALG $, there exists a fixed subset $ S'\subset [n] $ such that if $ T \subseteq \algS $ then $ \algS = S' $.
			In other words, when columns in $ \bar{T} $ are fixed, the event $ B_T $ (which implies $ T \subseteq \algS $) occurs  when $ \langle A_T \rangle \subseteq \langle A_{S' \setminus T} \rangle $, where $ \langle A_{S' \setminus T} \rangle $ is a deterministic subspace.
			Therefore, we may use lemma \ref{SSA:lem:X-in-V} to bound with $ 2^{-t^2} $ the probability that $ t $ i.i.d.\@ random binary vectors are in a deterministic subspace of dimension at most $ m-t$.
			Because there are no more than $ {n-k \choose t} $ such subsets we get the required bound.

			Denote by $ L_\emptyset $ the event that the columns of $ \D $ are linearly dependent and by $ \bar{L}_\emptyset $ its complementary.
			From inequality (\ref{SSA:lem-proof:eq:L_S-bound}) it follows that $ \Pr[L_\emptyset] \le o(1) $.
			Therefore,
			\begin{equation*}
			\begin{split}
			\Pr[B]
			&= \Pr\left[\bigvee_T B_T\right] \\
			&\le \Pr[L_\emptyset] + \Pr\left[\bigvee_T B_T \prmid \bar{L}_\emptyset\right] \\
			&\le o(1) + \Pr\left[\bigvee_T B_T  \prmid \bar{L}_\emptyset\right].
			\end{split}
			\end{equation*}

			Conditioned on that $ \bar{L}_\emptyset $ has happened, suppose that $ B_T $ occurred for some $ T \subseteq [n] $ with $ T \cap \D \neq \emptyset $.
			In this case, the rank of $ A|_\algS $ is lower that $ |\algS|-t $.
			Because the columns of $ \D $ are linearly independent, there exists a basis $ \mathcal{B}\subseteq A_\algS $ of the vector space $ \langle A_\algS \rangle $ such that $ \D\cap\algS \subseteq \mathcal{B} $.
			Therefore, there exists a subset $ T' \subseteq \algS $ such that $ B_{T'} $ occurs and $ T' \cap \D = \emptyset $.
			Hence,
			\begin{equation*}
			\Pr\left[\bigvee_T B_T \prmid \bar{L}_\emptyset\right] = \Pr\left[\bigvee_{T:T\cap \D = \emptyset} B_T \prmid\bar{L}_\emptyset\right].
			\end{equation*}
			Using a union bound we get
			\begin{equation*}
			\Pr\left[\bigvee_{T:T\cap \D = \emptyset} B_T \prmid\bar{L}_\emptyset\right]
			\leq \sum_{T: T\cap \D = \emptyset} \Pr\left[ B_T \prmid\bar{L}_\emptyset\right].
			\end{equation*}
			The sum goes over exactly $ n-k \choose t $ subsets, so we are left to show for a fixed subset $ T \subseteq [n] \setminus \D $ of cardinality $ t $ that $ \Pr[B_T | \bar{L}_\emptyset] \le 2^{-t^2}$.

			By the law of total probability we have that
			\begin{equation*}
			\begin{split}
			\Pr\left [B_T \prmid \bar{L}_\emptyset\right ]
			&= \sum_{H \in \{0,1\}^{m\times (n-t)}}
						\Pr\left[A|_{\bar{T}}=H \prmid \bar{L}_\emptyset \right]
						\Pr\left [B_T \prmid A|_{\bar{T}}=H\right].
			\end{split}
			\end{equation*}
			Consider a subset $ T \subseteq \notD $ of cardinality $ t $ and $ H \in \{0,1\}^{m \times (n-t)} $, we will show that
			$$
				\Pr\left[B_T \prmid { A|_{\bar{T}}=H}\right] \le 2^{-t^2}.
			$$
			The proof of Condition 2 of Lemma \ref{SSA:lem:conditions} will follow from
			\begin{equation*}
			\Pr\left [B_T \prmid \bar{L}_\emptyset\right ]
			\le \sum_{H \in \{0,1\}^{m\times (n-t)}} \Pr\left [A|_{\bar{T}}=H\prmid\bar{L}_\emptyset\right ] 2^{-t^2}
			= 2^{-t^2}.
			\end{equation*}

			Now, use the explicit notation $ \algS(A) = \algS $ for the outcome of $ ALG $ on a test matrix $ A $.
			From the consistency of $ ALG $ and because $ T \cap \D = \emptyset $, there exists a subset $ \algSTH \subseteq [n] $ such that for all $ A \in [H]_T $ if $ T \subseteq \algS(A) $, then $ \algS(A) = \algSTH $.
			Denote by $V_{H,T} $ the subspace spanned by the columns of $ \algSTH \setminus T $ (i.e., $ V_{H,T} = \langle A_{\algSTH \setminus T} \rangle $).
			Note that because $ (\algSTH \setminus T) \subseteq \bar{T} $ the subspace $ V_{H,T} $ is deterministic.
			Hence, together with the definition of $ B_T $ we have that
			\begin{equation*}
			\begin{split}
			\Pr\left [B_T \prmid  A|_{\bar{T}}=H\right ]
			&= \Pr\left [T\subseteq \algS \land \langle A_T\rangle \subseteq V_{H,T} \prmid  A|_{\bar{T}}=H\right ] \\
			&\le \Pr\left [\langle A_T\rangle \subseteq V_{H,T} \prmid  A|_{\bar{T}}=H\right ].
			\end{split}
			\end{equation*}
			Furthermore, because $ A_T $  is independent of $ A|_{\bar{T}} $ and $ T\cap \D = \emptyset $ we have:
			\begin{equation}\label{SSA:lem-cond2:eq:final}
				\Pr\left [\langle A_T\rangle \subseteq V_{H,T} \prmid  A|_{\bar{T}}=H\right ]
			= \Pr\left [\langle A_T\rangle \subseteq V_{H,T} \right ].
			\end{equation}
			Now, because $ V_{H,T} $ is spanned by less than $ m-t $ vectors its dimension is at most $ m-t-1 $.
			Finally, bound (\ref{SSA:lem-cond2:eq:final}) with the probability of $ t $  i.i.d.\@ random binary vectors to belong the deterministic subspace $ V_{H,T} \subseteq \mathbb{R}^m$. From Lemma \ref{SSA:lem:X-in-V}, we have that
			\begin{equation*}
			\Pr\left [\langle A_T\rangle \subseteq V_{H,T} \right ]\le 2^{-t^2}.
			\end{equation*}

		\newcommand{\Gevent}{\bar{L}}
		\emph{Condition 3}.
		This proof is similar to the one of condition 2.
		Assume that the third condition holds and that $ m > 2k $, otherwise the lemma holds by Condition 1.
		Let $ I:=I_{\D, ALG} $ be the function for which $ ALG $ is second-stage-consistent.
		Denote by $ L := L_{I(A)} $ the event that the columns of $ I(A) \cup \D $ are linearly dependent.
		Note that $ L $ is covered by the events in $ \{L_S | S \subseteq \notD \;, |S|= k \} $ (as defined in Condition 1 proof).
		Therefore, from (\ref{SSA:lem-proof:eq:union-L_S-bound}) together with the assumption that $  M > (1+\epsilon_n) \hat{M}_{QGT}$, we have that
		\begin{equation*}
			\Pr \left[ L \right]
			\le o(1).
		\end{equation*}
		As before, consider the event $ B $ and its cover $ \{B_T: T\subseteq [n], \; |S|=t\} $.
		Now, similarly, we bound $ B $ as follows:
		\begin{equation*}
			\Pr\left[B\right]
			\le o(1) + \Pr\left[\bigvee_T B_T \prmid \Gevent\right].
		\end{equation*}
		Conditioned that $ {\Gevent} $ happened, whenever $ B_T $ occurs for some subset $ T $ with $ T \cap (\D \cup \SA) \neq \emptyset $, there exists a subset $ T' $ with $ T' \cap (\D \cup \SA) = \emptyset $ such that $ B_{T'} $ also occurs.
		Denote by $ D_T $ the event that $ T \cap \SA = \emptyset $.
		To conclude
		\begin{equation*}
		\Pr\left[\bigvee_T B_T \prmid \Gevent\right]
		= \Pr\left[\bigvee_{T:T\cap \D = \emptyset} B_T\land D_T \prmid\Gevent\right].
		\end{equation*}

		By using a union bound we get
		\begin{equation}
		\Pr\left[\bigvee_{T:T\cap \D = \emptyset} B_T \land D_T \prmid\Gevent\right]
		\leq \sum_{T: T\cap \D = \emptyset} \Pr\left[ B_T \land D_T \prmid\Gevent\right].
		\end{equation}

		To finish this proof, while not repeating ourselves, we only show that for any relevant subset $ S\subseteq \notD $ and $ H \in \{0,1\}^{m \times n-t} $ the following holds
		$$\Pr\left [B_T \land D_T \prmid \Gevent, A|_{\bar{T}}=H\right ] \le 2^{-t^2}.$$

		Now, use the explicit notation $ \algS(A) = \algS $ for the outcome of $ ALG $ on a test matrix $ A $.
		Recall that $ ALG $ is second-stage-consistent.
		Hence, there exists a deterministic subspace $  V_{H,T} $ such that whenever $ D_T $ occurs and $ T \subseteq  \algS(A) $ holds, we have that $ \langle A_{\algS(A) \setminus T} \rangle =  V_{H,T}$.
		We conclude that
		\begin{equation*}
		\begin{split}
		\Pr\left [B_T  \land D_T \prmid \Gevent, A|_{\bar{T}}=H\right ]
		&= \Pr\left [T\subseteq \algS(A) \land \langle A_T\rangle \subseteq  V_{H,T} \land D_T \prmid \Gevent, A|_{\bar{T}}=H\right ] \\
		&\le \Pr\left [\langle A_T\rangle \subseteq  V_{H,T} \land D_T \prmid \Gevent, A|_{\bar{T}}=H\right ] \\
		& = \Pr\left [\langle A_T\rangle \subseteq  V_{H,T} \land D_T \right ] \\
		&\le\Pr\left [\langle A_T\rangle \subseteq  V_{H,T} \right ] \\
		&\le 2^{-t^2}.
		\end{split}
		\end{equation*}
		And we done.
	\end{proof}

	\subsection{$m$-Thresholding is consistent}
	\label{sec:m-thresholding-is-consistent}
	\begin{lem} \label{boosting:lem:basic-thresholding-is-consistent}
		$m$-Thresholding is consistent, and hence it has the relaxed rank property.
	\end{lem}
	\begin{proof}
		Fix $ \D $ and denote by $ \algS(A) $ the outcome of $m$-Thresholding on a test matrix $ A\in\{0,1\}^{m \times n} $.
		Consider a subset $ S\subseteq [n]\setminus\D $ and a matrix $ H \in \{0,1\}^{m\times |\bar{S}|} $.
		We need to provide a subset $ \algSH $ such that for all $ A\in [H]_{S} $, if $ S \subseteq \algS(A)  $ then $ \algS(A) = \algSH $.
		Assume $ |S|\le m $, otherwise the claim trivially holds.

		Recall that the score $ \psi_i $ of item $ i\in[n] $ is a function of the $ i $th test matrix column and of the tests outcome $ y $.
		Because $ S \cap \D = \emptyset $, for every $ A,A' \in [H]_{S} $ we have that $ Ax=A'x $.
		Namely, the tests outcome vector is equal for all tests matrices in $ [H]_{S} $.
		Therefore, the score $ \psi_i $ of an item $ i\in \bar{S} $ has fixed value for all tests matrices in $ [H]_{S} $.
		Sort the items in $ \bar{S} $ by descending order of score.
		Denote by $ S' \subseteq \bar{S} $ the subset that contains the first $ m-|S| $ items.
		Note that the subset $ S' $ is	determent by $ H $ and $S$.
		Define the subset $ \algSH := S'\cup S $.
		We have that if $ S \subseteq \algS(A)$ then $ \algS(A)=\algSH $.
	\end{proof}

	\subsection{Sufficient condition for second-stage-consistency}
	\label{sec:second-stage-consistency-algs}
		Consider a QGT algorithm $ ALG $ and the Subset Select algorithm produced by our proposed framework.
		That is, the $ (ALG) $-Then-Thresholding algorithm.
		We now discuss the reason why $ (ALG) $-Then-Thresholding may not be consistent.
		Let  $ S^\dagger $ and $ \algS $ denote the outcomes of the QGT algorithm $ ALG $ and of the Subset Select algorithm ($ ALG $)-Then-Thresholding, respectively.
		Suppose that for some problem instance, $ ALG $ did not recover all defective items (i.e, $ S^\dagger  \neq \D $).
		Recall, that the $ (ALG) $-Then-Thresholding algorithm calculates the score $ \phi_i $ for an item $ i $, which depends on the test matrix columns of $ S^\dagger $, $ \D $ and $ i $.
		Then, ($ ALG $)-Then-Thresholding returns $ S^\dagger $ together with the first $ m-k $ items sorted by score.
		Note that these score values depend also on the non-defective items that were in $ S^\dagger $, denote these non-defective items by $ I\subseteq S^\dagger\setminus\D $.
		The column entries of items in $ I $ may affect the algorithm outcome $ \algS $ in an inconsistent manner.
		That is, there might be two test matrices that differ only in the contents of the $ I $ columns such that for both of these test matrices, all of the items in $ I $ are part of the algorithm's outcome $ \algS $, however, the rest of the outcome is not identical.
		In this case, ($ ALG $)-Then-Thresholding is not consistent.
		Nevertheless, ($ ALG $)-Then-Thresholding may be second-stage-consistent (for instance if $ ALG $ satisfies the condition in Lemma \ref{boosting:lem:when-is-second-stage-consistent}).

		Intuitively, a second-stage-consistent algorithm has at most $ k $ non-defective items whose column entries affect the algorithm outcome in an inconsistent manner.
		As we formally define in Definition \ref{def:second-stage-consistent},
		these $ k $ non-defective items may be determined after observing $ A $.

		Consider an algorithm $ ALG $ for the QGT problem and
		denote its output on an input test matrix $ A \in \{0,1\}^{m \times n} $ by $ S^\dagger(A) $.
		In Lemma \ref{boosting:lem:when-is-second-stage-consistent} we define a property such that if $ ALG $ satisfies it, then $ (ALG) $-Then-Thresholding is second-stage-consistent.
		Intuitively the property is as follows.
		Consider two problem instances that differ only in the content of a set $S\subseteq[n]\setminus\D$ of matrix columns that correspond to non-defective items.
		If in each of the inputs, $ S $ is not part of $ ALG $'s solution, then the two solutions are identical.

		\begin{lem} \label{boosting:lem:when-is-second-stage-consistent}
			If for each subset $ S \subseteq \notD $ and matrix $ H \in \{0,1\}^{m \times |\bar{S}|} $ there exists a subset $ S^\dagger_{H,S} $ such that for all $ A\in \{A'\in[H]_{S} \;|\; S \cap S^\dagger(A') = \emptyset \}$ it holds that $ S^\dagger(A) = S^\dagger_{H,S} $, then the Subset Select algorithm $ (ALG) $-Then-Thresholding is second-stage-consistent with the function $ I(A) := S^{\dagger}(A) $.

			Hence, if $ ALG $ satisfies the above, $ (ALG)-Then-Thresholding $ has the relaxed rank property.
		\end{lem}
		Before we prove the above, note that $k$-Thresholding algorithm satisfies the requirements of Lemma \ref{boosting:lem:when-is-second-stage-consistent}.
		Therefore,
		\begin{lem}
			The ($k$-Thresholding)-Then-Thresholding algorithm is second-stage-consistent.
		\end{lem}
		Now, consider the algorithm \emph{Iterative-Thresholding} (see Algorithm \ref{alg:Iterative-Thresholding} in Section \ref{sec:empirical}). Starting with some subset $ \algS = \emptyset $, this algorithm calculates for each item $ i $ its score $ \phi_i = \langle A, y-A\one_\algS \rangle / \|A_i\|_1$.
		Iteratively it adds to $ \algS $ the item with the highest score $ \phi_i $ (excluding items that are already in $ \algS $) and updates all scores according to the new $ \algS $.
		The algorithm halts and returns $ \algS $ after $ k $ iterations (i.e., when $ |\algS| = k $).
		Note that this algorithm also satisfies the requirement of Lemma \ref{boosting:lem:when-is-second-stage-consistent} and therefore
		\begin{lem}
			The (Iterative-Thresholding)-Then-Thresholding algorithm is second-stage-consistent.
		\end{lem}

		\begin{proof}[Proof of Lemma \ref{boosting:lem:when-is-second-stage-consistent}]
			Denote by $ \algS(A) $ the outcome of $ (ALG) $-Then-Thresholding on the test matrix $ A\in \{0,1\}^{m \times n} $.
			Consider a subset $ S\subseteq \notD $, a matrix $ H \in \{0,1\}^{m\times |\bar{S}|} $ and the function $ S^{\dagger}(A) $.
			We need to provide a subset $ \algSH $ such that for all  $ A \in [H]_{S} $ if $ S \subseteq \algS(A)  $ and $ S \cap S^\dagger(A) = \emptyset $ hold then $ \algS(A) = \algSH $.
			Namely, $ \algS(A)=\algSH$ for each test matrix $ A\in[H]_S $ such that $ S $ is part of the new outcome (i.e., $ \algS(A) $), but was not part of the original outcome (i.e., $ S^\dagger(A) $).
			Denote the set of relevant matrices as
			$$
			\mathcal{H}=\mathcal{H}_{H,S,ALG} := \left \{A \in [H]_S \prmid S^\dagger(A)\cap S = \emptyset \,\land\,  S \subseteq \algS(A)\right \}.
			$$
			Assume $ |S|\le m-k $, otherwise the claim trivially holds (where the minus $ k $ is because $ S^\dagger(A) \subseteq \algS(A) $ by the definition of ($ ALG $)-Then-Thresholding).

			Observe that by the definition of $ (ALG) $-Then-Thresholding the score $ \phi_i $ of an item $ i \in [n] $ depends only on the test matrix columns of $ S^\dagger(A) \cup \D \cup \{i\} $.
			Consider the subset $ S^\dagger_{H,S} $ as defined in the lemma statement.
			By definition, for all $ A\in \mathcal{H} $ because $ S\cap S^\dagger= \emptyset$ we have that $ S^\dagger=S^\dagger_{H,S} $.
			Therefore, the score $ \phi_i $ for $ i\in \bar{S} $	is fixed for all test matrices in $\mathcal{H}$.
			Sort the items in $ \bar{S} $ by descending order of this fixed scores.
			Denote by $ S' \subseteq \bar{S} $ the subset that contains the first $ m-k-|S| $ items.
			Define the subset $ \algSH := S'\cup S \cup S^\dagger_{H,S}$.
			The subset $ S'\cup S^\dagger_{H,S}$  is fixed for any test matrix $ A\in\mathcal{H} $ and additionally $ S'\cup S^\dagger_{H,S} \subseteq \algS(A)$.
			Therefore, for every $ A\in \mathcal{H} $ if $ S \subseteq \algS(A)$ then $ \algS(A)=\algSH $.
		\end{proof}

	\subsection{Proofs of Lemma \ref{boosting:lem:top-k-number-of-tests} and Lemma \ref{boosting:lem:top-m-number-of-tests}} \label{boosting:subsec:basic-thresholding}
	Recall that $ k $-Thresholding is a variation of the Basic-Thresholding algorithm and that the score for item $ i\in[n] $ in the Basic-Thresholding algorithm defined as $ \phi_i:=\sum_{j=1}^m A_{ji}y_j / |A_i|$.

	In the following we describe the score $ \psi_i $ that we propose for the $ k $-Thresholding algorithm.
	For every test pool $ j \in [m] $ and its outcome $ y_j $, we may look at the \emph{complementary test} pool and its outcome.
	That is the test pool of the items that were not in the $ j $th test pool.
	Recall that the number of defective items $ k $ is known (or can be computed, see Section \ref{section:k-is-unkown-or-random}).
	Therefore, for every test $ j \in [m] $ we can compute the complementary test outcome $\bar{y}_j := k - y_j$ and its test pool which consists of the $ 0 $ entries of the $ j $th test matrix row.
	Accordingly, we define the matrix of complementary tests as $ \bar{A}:= \one_{m \times n} - A $ and the outcome of the complementary tests as $ \bar{y} = k\cdot 1_m - y $.
	Recall that $ x $ is the indicator of defective items and that $ Ax = y $. Note that we have also $ \bar{A}x = \bar{y} $.
	Using this observation, for every item $i \in [n]$, the algorithm calculates its score $\psi_i$ to be the sum of outcomes of tests and complementary tests in which item $i$ is within their test pool. Formally,
	\begin{equation}\label{boosting:eq:estimator_psi}
	\psi_i := \sum_{j=1}^m \left ( A_{ji} y_j + \bar{A}_{ji} \bar{y}_j \right ),
	\end{equation}
	Note that each score function $ \psi_i $ uses information from $ m $ tests, while $ \phi_i $ uses information from about half that many.
	Additionally and as shortly shown, the distribution of $ \psi_i $ is based on the binomial distribution.
	As this distribution has been extensively studied, it facilitates the analysis.

	Now we prove Lemma \ref{boosting:lem:top-m-number-of-tests}.
	The proof of Lemma \ref{boosting:lem:top-k-number-of-tests} is almost identical, so we omit it.

	\begin{proof}[Proof of Lemma \ref{boosting:lem:top-m-number-of-tests}]
		We start by describing the distribution of a score function $ \psi_i $ using a binomial random variable.
		Note that each element of the score sum in (\ref{boosting:eq:estimator_psi}) is $ A_{ji} y_j + \bar{A}_{ji} \bar{y}_j $. Namely, that is the number of defective items that are in the same test or complementary-test pool of item $ i $.
		Therefore, for a non-defective item $ i \in \notD $ and each test $ j \in [m] $ the expression $ A_{ji} y_j + \bar{A}_{ji} \bar{y}_j$ is distributed as the  Binomial random variable $ B\left(k, \nhalf \right) $.
		Whereas, for a defective item $ i \in \D $ it is distributed as $ 1 + B\left(k-1, \nhalf \right) $.

		Hence, the score function of each non-defective item $i\in [n] \setminus \D$ is distributed as
		$${\psi_i \sim B(mk, \nhalf)},$$
		whereas each defective item $i \in \D$ score function is distributed as
		$$\psi_i \sim m + B(m(k-1), \nhalf).$$

		We need to show that, w.h.p., all $k$ defective items appear among the first $ m $ items sorted by score.
		We will do so by showing that there exists some value $B\in \mathbb{R}$
		such that, w.h.p, $B$ is smaller than all of the defective-items' scores and is larger than all but potentially $m-k$ non-defective-items' scores.

		First, observe that for a non-defective item $i\in [n] \setminus \D$ we have that
		$$ \mathbb{E}[\psi_i] = \frac{mk}{2} $$
		and for defective item $i\in \D$  it is
		$$ \mathbb{E}[\psi_i] = \frac{m(k+1)}{2},$$
		therefore we express $B$ as
		\begin{equation*}
		\frac{m(k+\beta)}{2}
		\end{equation*}
		for some $\beta \in \left(0,1\right)$.

		For analysis, we will use the following inequality that we prove in the Appendix (see Section \ref{sec:appendix:binomial-tail-bound}).
		\begin{lem}\label{lem:pr-of-bernoulli-not-in-center}
			Consider $ N \in \mathbb{N}$, $ t:=t(N)\in\mathbb{N} $ such that $\sqrt N \le t \le o(N)$, and $X \sim B(N,\nhalf)$. It holds that:
			$$
				\Pr\left [X < \frac{N}{2} - t\right ] =
				\Pr\left [X >\frac{N}{2} + t\right ]
				\leq O\left ({\frac{\sqrt N}{t}}  e^{-\frac{2t^2}{N}} \right ).
			$$
		\end{lem}
		Assume that $m > k\lognk$.
		By Lemma \ref{lem:pr-of-bernoulli-not-in-center}, for a non-defective item $ i\in \notD $ we have that
		$$
		\Pr\left [\psi_i \geq \frac{m(k+\beta)}{2}\right ] <O\left(\sqrt\frac{k}{m}e^{-\frac{\beta^2 m}{2k}}\right)
		=o(1)e^{-\frac{\beta^2 m}{2k}},
		$$
		and for defective item $ i \in \D $
		$$
		\Pr\left [\psi_i \leq \frac{m(k+\beta)}{2}\right ] < O\left(\sqrt\frac{k}{m}e^{-\frac{(1-\beta)^2 m}{2k}}\right)
		=o(1)e^{-\frac{(1-\beta)^2 m}{2k}}.
		$$

		Use Markov's inequality to bound the probability that there are more than $ m - k $ non-defective items with a score larger than $ B $. That is
		\begin{equation} \label{thm1-pr-non-defective-bound}
		o(1) \frac{n-k}{m-k}e^{-\frac{\beta^2 m}{2k}}
		\le o(1) \frac{n}{k}e^{-\frac{\beta^2 m}{2k}}
		\leq o(1)n^{1-\theta}e^{-\frac{\beta^2 m}{2k}}.
		\end{equation}
		Although $ m>k\lognk=O(k \log n) $, note that  in (\ref{thm1-pr-non-defective-bound}) we bound $ m -k $ by $ k $.
		This costs us a factor of $ 1/\lognk $ in the right hand side expression.
		However, for our threshold analysis we consider the logarithm of inequality (\ref{thm1-pr-non-defective-bound}), and therefore we lose only a low order term in the exact threshold analysis (see Remark \ref{remark:2k-ssbt-is-also-like-ssbt} for further discussion).

		Using a union bound, we get that the probability that there exists a defective item with score below $ B $ is at most:
		\begin{equation} \label{thm1-pr-defective-bound}
			o(1)k e^{-\frac{(1-\beta)^2 m}{2k}}.
		\end{equation}
		Therefore, combining (\ref{thm1-pr-non-defective-bound}) and (\ref{thm1-pr-defective-bound}) we get that if $m$ is such that
		\begin{equation} \label{eq:lem:m-thresholding:objective}
					o(1)n^{1-\theta}e^{-\frac{\beta^2 m}{2k}} + o(1)k e^{-\frac{(1-\beta)^2 m}{2k}} = o(1),
		\end{equation}
		then $ B $ has the desired property.

		Note that in order to achieve the above asymptotic bound it suffices that $ m $ will satisfy
		$ \frac{{\beta^2}m}{2k} > \left(1-\theta\right) \ln n$
		and
		$ \frac{(1-\beta)^2m}{2k} > \ln k = \theta \ln n$. In other words,
		\begin{equation}\label{thm1-m1-bound}
		m > 2k \cdot \max \left \{ \frac{1-\theta}{\beta^2} , \frac{\theta}{(1-\beta)^2}\right \}\ln n.
		\end{equation}

		We would like to find an $\beta$ which minimizes the above equation's right side. Note that
		$ \frac{1-\theta}{\beta^2} $ and $\frac{\theta}{(1-\beta)^2}$ are monotonically decreasing and  monotonically increasing in $\beta$, respectively. Therefore, an $ \beta $ for which those two expressions are equal, is optimal.
		We define $\beta(\theta)$ as follows:
		$$
		\beta(\theta) := 	\left\{
		\begin{array}{ll}
		\nhalf & \mbox{if } \theta=\nhalf \\
		\frac{\theta-1+\sqrt{\theta(1-\theta)}}{2\theta-1} & \mbox{otherwise. }
		\end{array}
		\right.
		$$
		As $\frac{1-\theta}{\beta(\theta)^2} = \frac{\theta}{(1-\beta(\theta))^2}$ and $\beta(\theta) \in (0,1)$, the chosen $\beta(\theta)$ is optimal.
		By assigning $ \alpha = \beta(\theta)^{-1} $ in (\ref{thm1-m1-bound}), we conclude that for  $ m > k \alpha^{2} \ln \frac{n}{k} $
		the set $S$ contains w.h.p. all defective items.
	\end{proof}
	\begin{remark}\label{remark:2k-ssbt-is-also-like-ssbt}
		Note that the analysis in inequality (\ref{thm1-pr-non-defective-bound}) was done for an algorithm that picks only the first $ 2k $ items (instead of first $ m $) sorted by descending order of scores.
		We refer to this algorithm variation as the \emph{$ 2k $-Thresholding}.
		Doing the same analysis but without neglecting the low order term in (\ref{thm1-pr-non-defective-bound}), will yield the same threshold up to a factor of 1-o(1).

		In Section \ref{sec:empirical}, we conducted simulations of the algorithms: $ k $-Thresholding, $ m $-Thresholding and $ 2k $-Thresholding (see test set \ref{simulations:testset:bt-ssbt-2kssbt}).
		For some fixed $ n $ and $ k $, we simulated each algorithm on various values of $ m $.
		We then compare the theoretical thresholds (Lemma \ref{boosting:lem:top-k-number-of-tests} and Lemma \ref{boosting:lem:top-m-number-of-tests}) with the minimal $ m $ value such that these algorithms solved almost all problem instances.
		The observed success rate of the $ k $-Thresholding and the $ 2k $-Thresholding algorithms agrees with the theoretical threshold given at Lemma \ref{boosting:lem:top-k-number-of-tests} and Lemma \ref{boosting:lem:top-m-number-of-tests}, respectively.
		The $ m $-Thresholding algorithm succeed for much smaller $ m $ values.
		However, when calculating carefully Lemma \ref{boosting:lem:top-m-number-of-tests}'s threshold and taking in account the low order term in Equation (\ref{thm1-pr-non-defective-bound}), the simulations do agree with the theoretical analysis.
	\end{remark}

	\subsection{Proof of Theorem \ref{thm:SSA-with-little-order-term}}
\begin{proof}
	Consider a Subset Select algorithm $ ALG $ as in the theorem statement,
	and a global constant $ C'>0 $ that we set later.
	Define $ m_1 :=  m - C'\sqrt{m \log n} $ and $ m_2 := m-m_1 $.
	Given the Subset Select algorithm $ ALG $, we propose a new Subset Select algorithm $ ALG' $.
	We will then show that regardless of $ ALG $, the algorithm $ ALG' $ has the relaxed rank property with $ C=0 $, and therefore by Theorem \ref{thm:SSA-rank-condition}, we are done.
	The Subset Select algorithm $ ALG' $,	given a problem instance $ (A,y,k) $,
	runs $ ALG $ on the first $ m_1 $ tests.
	Namely, it runs $ ALG $ on the problem instance $ (A', y',k) $, where $ A'\in\{0,1\}^{m_1 \times n} $ is a submatrix of $ A $ containing the first $ m_1 $ rows and $ y' $ is the first $ m_1 $ entries of $ y $.
	Then, $ ALG' $ returns the same subset $ \algS \subseteq [n] $ that $ ALG $ returned on the modified problem instance.
	Note that $ |\algS| \le m_1 $ and that indeed if $ ALG $ solves efficiently the Subset Select problem for $ m_1>M $, then $ ALG' $ solves efficiently the Subset Select problem for $ m=m_1+m_2>(1+o(1))M $.

	In the rest of the proof, we use the following lemma that we prove in the Appendix as a corollary of Lemma \ref{SSA:lem:X-in-V} (see Section \ref{sec:apx:lem-space-rank-bound}).
	Let $u_1, u_2, \ldots, u_l$ be i.i.d. random vectors sampled uniformly from $\{0,1\}^{m_1}$.
	Denote the vector space spanned by these vectors as $U := \langle u_1, u_2, \ldots, u_l \rangle$ and let $V$ be a deterministic subspace in $ \{0,1\}^{m_1} $.

	\begin{lem} \label{lem:f2-space-rank-bound}
		Let $k_1$ and $k_2$ be integers such that $0 \leq k_1 \leq k_2 \leq {m_1} $.
		If $\dim\left( V \right) \geq k_1$ then the following holds:
		$$
		\Pr_{u_1,u_2,\ldots,u_l}\left[
		\dim\left(
		V \cup U
		\right)
		< k_2
		\right]
		\leq
		{l \choose {k_2-k_1-1}}2^{(k_2-1-m_1)(l-(k_2-k_1)+1)}
		$$
	\end{lem}
	We will show that every subset $ S \subseteq [n] $ that was constructed independently of the last $ m_2 $ rows of $ A $ and its cardinality is at most $ m_1 $,  will satisfy $ \rankof{A|_S}=|S| $ \whp.
	This implies that \whp $ \rankof{A|_\algS} = |\algS| $.
	Apart from the fact that $ \algS $ was constructed without observing the last rows, we also use the fact that its cardinality is at most $ m_1 $.
	For convenience, we assume that $ |\algS|=m_1 $.

	Denote by $ B_1 , B_2, \ldots, B_{m_1}, \ldots, B_m $ the rows of the matrix $ A|_{\algS} $.
	Consider the event that the dimension of the space spanned by $ B_1, B_2, \ldots B_{m_1} $ is at least $ m_1-\nicefrac{m_2}{2} $ and denote it by $ E_1 $. Formally, the event $ E_1 $ is
	\begin{equation*}\label{eq:thm-rank-proof:E1}
	\dim \left(\langle B_1,B_2, \ldots, B_{m_1}\right \rangle) \geq m_1-\nicefrac{m_2}{2}.
	\end{equation*}
	Similarly, denote by $ E_2 $ and $ E_3 $ the events:
	\begin{equation*}
	\begin{split}
	\dim \left (\langle B_1,B_2, \ldots, B_{m_1+\nicefrac{m_2}{2}} \rangle\right ) & \geq  m_1-\log m_1,\\
	\dim \left (\langle B_1,B_2, \ldots, B_{m}\right \rangle) & = m_1;
	\end{split}
	\end{equation*}
	respectively. Denote by $ \bar{E}_1, \bar{E}_2 $ and $ \bar{E}_3 $ the complementary events of $ E_1, E_2 $ and $ E_3 $, respectively.

	Note that the $ E_3 $ is the event that we are after, i.e., $ \rank\left(A|_{\algS}\right) = m_1 $.
	By the law of total probability we have that:
	\begin{equation*}
	\Pr \left[E_3\right] \geq \Pr [E_1]\cdot \Pr [E_2 | E_1 ] \cdot \Pr [E_3 | E_2].
	\end{equation*}
	Therefore, We will show that the event $ E_3 $ holds w.h.p. by proving that
	\begin{equation}\label{eq:thm-rank-proof:total-bound}
	\Pr [E_1]\cdot \Pr [E_2 | E_1 ] \cdot \Pr [E_3 | E_2]  = 1 - o(1).
	\end{equation}
	Let $ c > 0 $ be a small enough constant.
	Using lemma \ref{lem:f2-space-rank-bound}, with $ V = \emptyset $ (and therefore $ k_1 = 0 $), $ l = m_1 $ and $ k_2 = m_1-\nicefrac{m_2}{2} $,
	we have that $ \Pr [\bar{E}_1|{\algS}=S_0] $ for any subset $ S_0 $ of cardinality $ m_1 $ is upper bounded by:
	\begin{equation*}
	{m_1 \choose {m_1-\nicefrac{m_2}{2}-1}}2^{(m_1-\nicefrac{m_2}{2}-1-m_1)(m_1-(m_1-\nicefrac{m_2}{2})+1)} \leq
	{m_1 \choose \nicefrac{m_2}{2}+1} 2^{-cm_2^2}
	\end{equation*}
	Therefore, using a union bound over all possible subsets $S$ of cardinality $m_1$ we have that
	\begin{equation}\label{eq:thm-rank-proof:E1-bound}
	\Pr \left[
	E_1
	\right]
	\geq
	1-
	\sum_{{S_0}}
	\Pr \left[ \bar{E}_1 | \algS = {S_0}\right]
	\geq
	1-{n \choose m_1}{m_1 \choose \frac{m_2}{2} + 1} 2^{-cm_2^2}
	= 1-o(1).
	\end{equation}
	The last equality in (\ref{eq:thm-rank-proof:E1-bound}) follows the definition of $ m_1 $ and $ m_2 $. That is, $ m_1 = m -C\sqrt{m \log n} $ and $ m_2 = m-m_1 $.

	Note that for every $m_1<j\leq m$ the row $ B_j $ is a uniformly random vector in $ \{0,1\}^{m_1}$ (because these rows are not observed by the algorithm when it constructed  $ \algS $).
	Next, we give an upper bound to $ \Pr \left[\bar{E}_2|E_1 \right] $.
	Using Lemma \ref{lem:f2-space-rank-bound} with the parameters: $ V = \langle B_1, B_2, \ldots, B_{m_1} \rangle $, $ k_1 = m_1 - \nicefrac{m_2}{2} $, $ l = \nicefrac{m_2}{2} $ and $ k_2 = m_1 - \log m_1 $.
	We have that $ \Pr \left[\bar{E}_2|E_1 \right] $ is upper bounded by:
	\begin{equation*}
	{\nicefrac{m_2}{2} \choose {\nicefrac{m_2}{2}- \log m_1 - 1}}
		2^{(-\log m_1 - 1)(\log m_1 + 1)}
	\leq {\nicefrac{m_2}{2} \choose \log m_1 + 1}
		{m_1}^{-\log {m_1}}
	=o(1)
	\end{equation*}
	Therefore,
	\begin{equation}\label{eq:thm-rank-proof:E2-bound}
	\Pr [E_2 | E_1] = 1 - \Pr \left[\bar{E}_2|E_1 \right]=1-o(1)
	\end{equation}
	Last, we upper bound $ \Pr \left[ \bar{E}_3 | E_2 \right] $.

	By applying Lemma \ref{lem:f2-space-rank-bound} with the parameters $ V = \langle B_1,B_2, \ldots, B_{m_1+\nicefrac{m_2}{2}} \rangle$, $ l = \nicefrac{m_2}{2} $, $ k_1 = m_1-\log m_1 $ and $ k_2 = m_1 $ we get the upper bound of
	\begin{equation*}
	{\nicefrac{m_2}{2} \choose {\log m_1 -1 }}
	2^{-(\nicefrac{m_2}{2}-\log m_1+1)}
	\leq {\nicefrac{m_2}{2} \choose \log {m_1} - 1}
	2^{-c(m_2 - \log m_1)}=o(1).
	\end{equation*}
	Hence,
	\begin{equation}\label{eq:thm-rank-proof:E3-bound}
	\Pr [E_3 | E_2] =
	1-\Pr \left[ \bar{E}_3 | E_2 \right]=1-o(1).
	\end{equation}

	Set $ C:=c^{-1} $ and assign (\ref{eq:thm-rank-proof:E1-bound}), (\ref{eq:thm-rank-proof:E2-bound}) and (\ref{eq:thm-rank-proof:E3-bound}) into (\ref{eq:thm-rank-proof:total-bound}). We have that
	\begin{equation*}
	\Pr[E_3] \ge 1-o(1),
	\end{equation*}
	and the proof follows.
\end{proof}

\end{document}

config: arxiv


TITLE: Example of subgroup of $\mathbb Q$ which is not finitely generated
QUESTION [4 upvotes]: I was looking for a proper subgroup of $\mathbb Q$ which is not finitely generated under the addition operation.

We know every finitely generated subgroup of $\mathbb Q$ is cyclic. For a proper subgroup I am just thinking about the subgroup $H$ generated by $\{\frac{1}{p} : p \text{ prime }\}$ may work. It seems $1/4$ is not in $H.$ Is this a  correct example? Thanks

REPLY [5 votes]: Try $\mathbb Z[\frac12]$, that is, the set of binary fractions.
More generally, $\mathbb Z[\frac1p]$, that is, the set of fractions whose denominators are powers of the prime $p$.


TITLE: A problem about Taylor polynomial approximation
QUESTION [0 upvotes]: $f(x)=\frac {e^x-1}{x}$ when $x\neq 0$, $f(x)=1$ when $x=0$.
(a) Compute the n-th Tylor polynomial of $f$ at $0$, $f^{(k)}(0)$ for any $k\in \{0\}\bigcup\mathbb N$, and the remainder $R_{n,0,f}$.
(b) Compute $\int_0^1f(x)dx$ with an error less than $10^{-4}$.

For (a), I found that f is equal to both $\sum^{n+1}_{k=1}\frac {x^{k-1}}{k!}$ and $\sum^{n+2}_{x=1}\frac{x^{k-1}}{k!}$ up to order $n$ at $0$ but they are different polynomials. But according to my textbook they should be exactly the same polynomial. And, I cannot figure out a way to compute the remainder. The only formula I can come up with is $R_{n,0,f}=\int^{x}_{0}\frac{f^{(n+1)}(t)}{n!}(x-t)^ndt$. I don't want to calculate derivatives of $f$ directly so I don't know how to calculate the remainder.
For(b), define $F(x)=\int^{x}_0f(x)dx$. Then by Taylor's theorem, for a given natural number $n\in\mathbb N$, $$F(x)=\sum^{n}_{i=0}\frac{F^{(i)}(0)}{i!}x^i+\int^{x}_0\frac{F^{(n+1)}(t)}{n!}(x-t)^ndt=\sum^{n}_{i=1}\frac{F^{(i)}(0)}{i!}x^i+\int^{x}_0\frac{F^{(n+1)}(t)}{n!}(x-t)^ndt$$, since $F^{(i)}=f^{(i-1)}$ for any $1\leq i$, we have $$F(x)=\sum^{n}_{i=1}\frac{f^{(i-1)}(0)}{i!}x^i+\int^{x}_0\frac{f^{(n)}(t)}{n!}(x-t)^ndt$$. If we could restrict remainder term $\int^{x}_0\frac{f^{(n)}(t)}{n!}(x-t)^ndt$, then we will be able to choose a propriate $n$ in order to calculate the integral within the range.

REPLY [0 votes]: you can go from the macularin series for $e^x.$ that gives you
$$\begin{align}e^x - 1 &= \int_0^x e^t \, dt\\
&=(t-x)e^t\big|_0^x-\int_0^x (t-x)e^t\, dt\\
&=x-\int_0^x (t-x)e^t\, dt \tag 1\\
&=x-\frac 12(t-x)^2e^t\big|_0^x+\int_0^x\frac 12(t-x)^2 e^t\, dt\\
&=x +\frac{x^2}{2!}+\int_0^x\frac 12(t-x)^2 e^t\, dt \tag 2\\
\end{align}$$
$$\frac{e^x - 1}x = 1+\frac x{2!} + \frac {x^2}{3!} + \cdots +\frac{x^{n-1}}{n!} + (-1)^n \frac 1 {xn!}\int_0^x(t-x)^ne^t\, dt$$
when $x$ is away from zero, the remainder $$ (-1)^n \frac 1 {xn!}\int_0^x(t-x)^ne^t\, dt $$ looks alright. i don't know how to handle when $x$ is close to zero.


TITLE: Recursion: In how many ways we can tile a rectangle with size of $1\times 10$ without two adjacent red floor tiles?
QUESTION [0 upvotes]: This is the question:
We have unlimited floor tiles in the colors red or blue. Every color comes in the size of $1\times 1$ or $1 \times 2.$
In how many ways we can tile a rectangle with size of $1\times 10$ without two adjacent red floor tiles?
What is the recursion formula for that problem and that are the start conditions?

I have tried to think about a solution like this:

for rectangle size of $1 \times 1$ we have $2$ options: red or blue $1 \times 1$ floor tile

for rectangle size of $1\times 2$ we have $3$ options: red & blue $1 \times 1,$ $2$ blue $1 \times 1$ or $1$ blue $1 \times 2$

But later then I got stucked with comming up with a solution to Typical Polynomym

REPLY [1 votes]: Notation: $R(1,1)$ is a $1\times 1$ red tile, $R(1,2)$ is a $1\times 2$ red tile and so on.
There are two reasons for which the question seems awkward.

What does how many ways mean?  More precisely, when tiling a $1\times 2$ rectangle, $R(1,1)+B(1,1)$ is the same as $B(1,1)+R(1,1)$?  Looking at your count, it seems that you would like to consider them as representing one tiling.  My answer below considers them as being distinct.  To state it differently: I consider no symmetry that identifies two tilings.

Your example for a $1\times 2$ rectangle is incorrect whatever way of counting you consider; you forgot the $R(1,2)$ construction.

A solution sketch.  A tiling for a $1\times n$ rectangle is considered as having, either a final $R(1,i)$ or a $B(1,i)$ tile.  Denote $r_n$ the number of tiling ending with a red one, and $b_n$ the number of those ending with a blue one.  We need to determine these two sequences.
We have, after some moments of thought about the final tile,
$b_n=b_{n-1}+r_{n-1}+b_{n-2}+r_{n-2}$ and $r_n=b_{n-1}+b_{n-2}$.  Moreover, $b_1=1$ and $b_2=3$, and $r_1=1$ and $r_2=2$.
To have our count, it is sufficient to determine $(b_n)_n$.  But using the two recurrent relations, $b_n=b_{n-1}+2b_{n-2}+2b_{n-3}+b_{n-4}$ with the initial conditions
$b_{-3}=b_{-2}=b_{-1}=0$ and $b_0=1$.  This is the sequence
https://oeis.org/A123392.
For the $1\times 10$ problem, we obtain
$b_8=461$, $b_9=1068$, $b_{10}=2474$, and hence $r_{10}=1529$.  The sum $b_{10}+r_{10}$ is the number we are looking for.
Remark. If we want to obtain the number of tilings after the identification by reflection in the "vertical" mediator of the $1\times 10$ rectangle, the study of the tilings of the $1\times 5$ rectangle is needed and some considerations about the action of the group $\{-1,1\}$ (of the reflection) on the tilings of the $1\times 10$ rectangle.


TITLE: How can I solve the inequation $(x-4)(x+2) \leq 0$?
QUESTION [0 upvotes]: I've been stuck on this textbook question.
So with the inequality given we can assume that $x \leq -2$ or $x \leq 4$, right?
I've gotten confused on the final step, not sure how it all combines into one.

REPLY [1 votes]: Here is another way to approach it differently from studying each case separately:
\begin{align*}
(x - 4)(x + 2) \leq 0 & \Longleftrightarrow (x - 4)(x - 4 + 6) \leq 0\\\\
& \Longleftrightarrow (x - 4)^{2} + 6(x - 4) \leq 0\\\\
& \Longleftrightarrow (x - 4)^{2} + 6(x - 4) + 9 \leq 9\\\\
& \Longleftrightarrow ((x - 4) + 3)^{2} \leq 9\\\\
& \Longleftrightarrow (x - 1)^{2} \leq 9\\\\
& \Longleftrightarrow |x - 1| \leq 3\\\\
& \Longleftrightarrow -2 \leq x \leq 4
\end{align*}
and we are done.
Hopefully this helps !


TITLE: Deriving Uncertainty Relation for Canonical Commuting Observables from Schrödinger Uncertainty Relation
QUESTION [1 upvotes]: In case the names are not standard:
\begin{equation}
 \sigma_{\hat{A}}^{2}\sigma_{\hat{B}}^{2}
  \geq \left\vert
    \frac{1}{2i} \left\langle \left[\hat{A},\hat{B}\right] \right\rangle
    \right\vert^{2}
  +  \left\vert
    \frac{1}{2} \left\langle \left\{\hat{A},\hat{B}\right\}\right\rangle
  -  \left\langle\hat{A}\right\rangle \left\langle\hat{B}\right\rangle
    \right\vert^{2}
\label{eq:1}
\tag{Scrhödinger's Uncertainty Relation}
\end{equation}
\begin{equation}
 \sigma_{\hat{A}}\sigma_{\hat{B}}
  \geq \frac{\left\vert
    \left\langle \left[\hat{A},\hat{B}\right]\right\rangle
    \right\vert}{2}
\label{eq:2}
\tag{Robertson's Uncertainty Relation}
\end{equation}
Given $\hat{Q},\hat{P}$ observables such that $\left[\hat{Q},\hat{P}\right] = i\hbar$
\begin{equation}
 \sigma_{\hat{Q}}\sigma_{\hat{P}}
  \geq \frac{\hbar}{2}
\label{eq:3}
\tag{Uncertainty Relation for Cannonical Commuting Observables}
\end{equation}
For \ref{eq:3}, we know that the equality is reached, meaning $\left[\hat{Q},\hat{P}\right] = i\hbar$ is a sufficient condition for
\begin{equation}
\left\vert
    \frac{1}{2} \left\langle \left\{\hat{A},\hat{B}\right\}\right\rangle
  -  \left\langle\hat{A}\right\rangle \left\langle\hat{B}\right\rangle
    \right\vert^{2}
        =       0
\end{equation}
on \ref{eq:1}.
This is what I'm not able to prove.
An ideal answer would contain the necessary conditions for this - that the \ref{eq:1} turns out to be \ref{eq:2} and the equality is reached - to happen.
PD:

I'm aware of how to derive \ref{eq:3} from the commutation relation by other means. I'm interested in what is mentioned above.
In case it sounds like homework, hints or references are highly appreciated.

REPLY [1 votes]: Robertson's Uncertainty Relation will hold even if
$$\begin{equation}
\left\vert
    \frac{1}{2} \left\langle \left\{\hat{A},\hat{B}\right\}\right\rangle
  -  \left\langle\hat{A}\right\rangle \left\langle\hat{B}\right\rangle
    \right\vert^{2}
        \neq       0
\end{equation}$$
Because
$$\sigma _{A}^{2}\sigma _{B}^{2}\geq \left|{\frac {1}{2}}\langle \{{\hat {A}},{\hat {B}}\}\rangle -\langle {\hat {A}}\rangle \langle {\hat {B}}\rangle \right|^{2}+\left|{\frac {1}{2i}}\langle [{\hat {A}},{\hat {B}}]\rangle \right|^{2}$$
$$\Rightarrow\sigma _{A}^{2}\sigma _{B}^{2}\geq \left|{\frac {1}{2i}}\langle [{\hat {A}},{\hat {B}}]\rangle \right|^{2}$$
since both of them are positive and if something is bigger than the addition of two positive real numbers then it is also bigger than each positive number seperately.
$$\Rightarrow\sigma _{A}^{2}\sigma _{B}^{2}\geq \left|{\frac {1}{2}}\langle [{\hat {A}},{\hat {B}}]\rangle \right|^{2}$$
$$\Rightarrow\sigma _{A}\sigma _{B}\geq {\frac {1}{2}}\left|\langle [{\hat {A}},{\hat {B}}]\rangle \right|$$
Scrhödinger's Uncertainty Relation is a stronger condition and if it satisfied then Robertson's Uncertainty Relation directly follows from that.
But Scrhödinger's Uncertainty Relation is satisfied only if the vector $ {\hat {B}}|\Psi \rangle $ is in the domain of the unbounded operator $ {\hat {A}}$, which is not always the case. A counter example is given here in Wikipedia.
Also refer to chapter 12 of Quantum Theory for Mathematicians by Brian C. Hall 2013 for more information.
Edit: Based on the comment I understood that you are asking the condition for a state in which both inequalities will imply each other and both equalities are satisfied.
Let there be some states $|\Psi_i \rangle$ for which Scrhödinger's Uncertainty Relation satisfies the equality and let there be some states $|\psi_i \rangle$ for which Robertson's Uncertainty Relation satisfies the equality. If $|\Psi_i \rangle$ and $|\psi_i \rangle$ have a common state, then for that state both relations satisfy with equality.
Since such a state satisfies both equalities it also satisfies:
$\begin{equation}
\left\vert
    \frac{1}{2} \left\langle \left\{\hat{A},\hat{B}\right\}\right\rangle
  -  \left\langle\hat{A}\right\rangle \left\langle\hat{B}\right\rangle
    \right\vert^{2}
        =       0
\end{equation}$
But even if $\begin{equation}
\left\vert
    \frac{1}{2} \left\langle \left\{\hat{A},\hat{B}\right\}\right\rangle
  -  \left\langle\hat{A}\right\rangle \left\langle\hat{B}\right\rangle
    \right\vert^{2}
        =       0
\end{equation}$ for a state that doesn't imply that for that state both uncertainty relations are satisfied with equality.


TITLE: $O(2)$ subgroup representation of $O(3)$
QUESTION [0 upvotes]: My objective is to:
Argue that the defining representation of $O(3)$ is irreducible and becomes reducible when restricting to an $O(2)$ subgroup.
The defining rep of $O(3)$ is:
$ \begin{pmatrix}
  a & b &  c \\
  -b & d &  e \\
  -c & -e &  f
 \end{pmatrix}$
which I can argue is an irrep because (geometrically) it has no invariant subspaces, and (algebraically) it is an irrep according to Schur's lemma.
I'm completely confused how to make a $2-\dim O(2)$ rep version of this :(

REPLY [0 votes]: Any $2\times 2$ matrix can be turned into a $3\times 3$ one by making it block-diagonal, with the original $2\times 2$ matrix first and then a $1\times 1$ block with the value $1$ next. This is a very general way that classical matrix groups embed into classical matrix groups of higher dimensions.
Here, geometrically speaking, $O(2)$ acts on the first two coordinates of $\mathbb{R}^3$, so by rotations and reflections within the $xy$-plane. Can you find $1$D and $2$D invariant subspaces?


TITLE: Properties of weighted average
QUESTION [0 upvotes]: Consider a set of real positive numbers $\{x_1,x_2,...,x_n\}$ all greater than a positive real number $s$. Consider $n$ positive weights $w_i$ s.t. $\sum_{i=1}^{n}w_i=1$. Show that $\frac{1}{n}\sum_{i=1}^{n}w_ix_i\geq s$.

REPLY [2 votes]: $$\sum_{i=1}^{n}w_ix_i-s=\sum_{i=1}^{n}w_ix_i-s\sum_{i=1}^{n}w_i=\sum_{i=1}^{n}w_i(x_i-s)\ge 0.$$