# Towards Efficient Compressive Data Collection
in the Internet of Things

Peng Sun†, Liantao Wu≀, and Zhi Wang§ Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>†School of Science and
Engineering, The Chinese University of Hong Kong, Shenzhen, P. R. China
≀Shanghai Institute of Fog Computing Technology (SHIFT), ShanghaiTech
University, P. R. China  §State Key Laboratory of Industrial Control
Technology, Zhejiang University, P. R. China

###### Abstract

It is of paramount importance to achieve efficient data collection in the
Internet of Things (IoT). Due to the inherent structural properties (e.g.,
sparsity) existing in many signals of interest, compressive sensing (CS)
technology has been extensively used for data collection in IoT to improve
both accuracy and energy efficiency. Apart from the existing works which
leverage CS as a channel coding scheme to deal with data loss during
transmission, some recent results have started to employ CS as a source coding
strategy. The frequently used projection matrices in these CS-based source
coding schemes include dense random matrices (e.g., Gaussian matrices or
Bernoulli matrices) and structured matrices (e.g., Toeplitz matrices).
However, these matrices are either difficult to be implemented on resource-
constrained IoT sensor nodes or have limited applicability. To address these
issues, in this paper, we design a novel simple and efficient projection
matrix, named sparse Gaussian matrix, which is easy and resource-saving to be
implemented in practical IoT applications. We conduct both theoretical
analysis and experimental evaluation of the designed sparse Gaussian matrix.
The results demonstrate that employing the designed projection matrix to
perform CS-based source coding could significantly save time and memory cost
while ensuring satisfactory signal recovery performance.

###### Index Terms:

Internet of Things, data collection, compressive sensing, sparse Gaussian
matrix

##  I Introduction

With the prevalence of smart devices, sensors, RFID tags, etc., and the broad
deployment of wireless communication infrastructures, the Internet of Things
(IoT) is undergoing an unprecedentedly rapid development [1, 2]. Recent years
have witnessed a wide range of IoT applications, such as environmental
monitoring, intelligent transportation systems, smart cities, and smart homes
[3], to name a few.

Data collection is the fundamental operation in IoT to underpin various
applications. The IoT sensor nodes (e.g., smart devices, sensors) need to
periodically report their sensed data to a fusion center (FC), where
information aggregation and extraction tasks are performed. Generally, IoT
sensor nodes are resource-constrained. More precisely, they have limited
computational capability, storage capacity, and power supply. Therefore, it is
of crucial importance to achieve efficient data collection in IoT. Many real-
world signals of interest (e.g., temperature, noise level, air quality level,
and traffic speed) present inherent structural properties (e.g., sparsity).
Thus, compressive sensing (CS) [4] has been widely used to achieve efficient
information acquisition and transmission in IoT, as it promises accurate
recovery of high-dimensional sparse signals from only a small number of random
measurements.

Thus far, a significant amount of research efforts have been devoted to
utilizing CS for compressive data collection in IoT [5, 6, 7, 8]. Most of the
existing works leverage CS as a channel coding scheme to deal with data loss
during information collection in IoT. For instance, the work in [8] mined and
analyzed four different data loss patterns and proposed an environmental
space-time improved compressive sensing (ESTICS) algorithm to reconstruct the
massive missing data accurately. Our previous work [6] modeled the random data
loss during transmission over a lossy wireless link as a CS measurement
process, where the correctly received data samples determine the corresponding
projection matrix. Some recent works (e.g., [9]) have started to employ CS as
a source coding strategy to further improve the accuracy and energy efficiency
of information collection. A simple and straightforward CS-based source coding
scheme is to perform random projection on the original sensed signals at the
IoT sensor nodes before transmission, where some proper projection matrices
are utilized.

In CS-based source coding schemes, the projection matrix is a critical factor
for achieving satisfactory signal reconstruction performance. Specifically,
the CS theory establishes that the projection matrix needs to be incoherent
with the transform basis, where the original signal has a sparse
representation, to guarantee accurate signal recovery. Frequently used
projection matrices in CS can be divided into three categories. The first one
is standard dense random matrices, e.g., random Gaussian or Bernoulli
matrices. Elements in these matrices are independently and identically
distributed random variables with certain distribution functions, i.e.,
Gaussian distribution or Bernoulli distribution. Existing works have
demonstrated that Dense random matrices are incoherent with most sparsifying
bases and satisfy the restricted isometry property (RIP), which promises
accurate signal recovery with high probability. However, as stated in [10],
the implementation of dense random Gaussian/Bernoulli projection matrices
requires the integration of a Gaussian/Bernoulli-distributed random number
generator and the computation of complicated matrix multiplication. This is
too complex and resource-consuming for low-cost IoT sensor nodes with limited
computational capability and storage capacity. The second kind of projection
matrices is structured projection matrices, e.g., Toeplitz matrices. Elements
of this kind of matrices are arranged with a particular pattern, yielding a
lower degree of randomness than dense random matrices. The third kind of
projection matrices is partial basis matrices, such as partial Fourier
matrices, constructed by selecting a subset of rows from an orthogonal Fourier
transform basis. The essential requirement of the projection matrix used in
CS-based source coding is that given a certain number of data samples received
at the FC, we could consistently achieve accurate signal recovery regardless
of the transform basis under which the target signal can be sparsely
represented. However, as stated in [11], partial Fourier matrices can only
adapt to the time domain sparse signals, while as indicated in [12], Toeplitz
matrices are neither applicable to all sparse signals. Therefore, the
shortcoming of structured projection matrices and partial basis matrices lies
in that they are confined to specific sparse signals, leading to a limited
range of applications. To summarize, none of the existing projection matrices
can satisfy our requirement of efficient and wide-area applications of CS
techniques in IoT data collection.

To address the issues mentioned above, in this paper, we design a simple and
efficient projection matrix, named sparse Gaussian matrix, which is easy and
efficient to be implemented on low-cost IoT sensor nodes and applies to
various kinds of sparse signals. Specifically, we first present the
construction of a sparse Gaussian matrix and then theoretically prove its RIP,
which guarantees accurate signal recovery with high probability. Finally, we
conduct extensive experiments to evaluate the performance of the designed
sparse Gaussian matrix. The results demonstrate that employing the designed
sparse Gaussian matrix to perform CS-based source coding can significantly
save time and memory cost for IoT sensor nodes while guaranteeing satisfactory
signal recovery performance at the FC compared to existing projection
matrices.

In summary, this paper makes the following contributions:

  * •

To the best of our knowledge, this is the first work to consider designing a
proper projection matrix to realize efficient and resource-saving CS-based
source coding for efficient data collection in IoT.

  * •

We design a novel, simple projection matrix, named sparse Gaussian matrix, and
theoretically prove its RIP.

  * •

We conduct extensive experiments and the results demonstrate that leveraging
the designed sparse Gaussian matrix to perform CS-based source coding can
significantly reduce the time and memory cost for the IoT sensor nodes while
guaranteeing satisfactory signal recovery performance at the FC.

##  II System Model and Problem Formulation

In this section, we present the system model and problem formulation.

Figure 1: System model.

###  II-A System Model

This paper considers a typical data collection process in IoT, which is
fundamental to enable various applications. Fig. 1 shows the whole process of
data collection. Specifically, the IoT sensor node periodically senses the
physical world. In a specific sensing period, the node will collect a certain
number of data samples and generate an original sensed signal with a sparse
representation under some transform basis (e.g., Fourier basis). The data
samples are then transmitted to the FC for further information aggregation and
extraction. Due to channel noise, congestion, packet collisions, and limited
transmission power, data transmission in IoT is prone to data loss. That is,
only a subset of transmitted data samples can successfully arrive at the FC.
To deal with the data loss, based on the sparse structure of the signal, our
previous work [6] proposed to model the random data loss during transmission
as a CS measurement process. The corresponding projection matrix modeling data
loss is a sparse binary measurement matrix which contains one and only one
“$1$” element in each row and at most one “$1$” in each column, and “$0$”
everywhere else (Note that the formal definition of this projection matrix
will be presented in the next subsection). It has been shown in [6] that the
CS-based sparse signal transmission method achieves much better transmission
performance compared to traditional retransmission-interpolation schemes.

Moreover, as pointed out in our previous work [7], for a large number of
applications in IoT, the transmission rate is much less than the sampling
rate. For example, the upper bound of the transmission rate in IEEE 802.15.4
is 250kbps, while the sampling rate of commercial AD converters is several
MHz. Moreover, when multiple sensor nodes transmit data to the fusion center
(FC) via random access, where packet collisions may happen, a higher
transmission rate generally leads to more severe packet collisions, worsening
the signal recovery performance at the FC. Thus, we introduce a simple CS-
based source coding operation at the sensor node before transmission.
Specifically, instead of directly transmitting the original sensed signal,
which comprises all the acquired data samples, it will be projected onto a
lower-dimensional space before being sent. In this way, the number of actually
transmitted data samples is smaller than the number of acquired data samples,
thus avoiding unnecessary resource costs for IoT sensor nodes. To optimize the
resource cost of the source coding process for the IoT sensor nodes and ensure
satisfactory signal recovery performance at the FC, the projection matrix used
in CS-based source coding should be carefully designed.

###  II-B Problem Formulation

In a specific sensing period, an IoT sensor node is assumed to have acquired
$N$ data samples from the physical world. Then, we denote the original signal
assembled by the $N$ data samples by $\bf{x}$ and
${\bf{x}}=[x_{1},x_{2},...,x_{N}]^{T}$, where $x_{i}$ ($i=1,2,...,N$) is the
$i$-th data sample. It has been shown in [7, 5, 13] that most target signals
in IoT applications have a sparse (compressible) representation in some
transform basis, e.g., Fourier, DCT, wavelets, etc. Formally, if we denote by
${\bf{\Psi}}$ the transform basis under which $\bf{x}$ can be sparsely
represented, we have ${\bf{x}}={\bf{\Psi s}}$, and ${\bf{s}}$ is a sparse
vector, which contains only a small number of nonzero elements.

As stated above, instead of directly transmitting the original signal
$\bf{x}$, it is more desirable to perform a CS-based source coding before
transmission, i.e., conducting a random projection on $\bf{x}$ using a well-
designed projection matrix ${{\bf{\Phi}}_{s}}\in{\mathbb{R}}^{{M_{s}}\times
N}$. Formally, this random projection process can be represented as

${{\bf{x}}_{s}}={{\bf{\Phi}}_{s}}{\bf{x}},$ (1)

where ${{\bf{x}}_{s}}\in{\mathbb{R}}^{M_{s}}$ is the signal after the
projection operation, and it is the signal actually to be transmitted.
${{\bf{\Phi}}_{s}}$ is the employed projection matrix.

As previously mentioned, data transmission from the IoT sensor node to the FC
is subject to data loss. In the same way as in [6], we model the random data
loss during transmission as a CS measurement process, which can be represented
as

${\bf{y}}={{\bf{\Phi}}_{r}}{{\bf{x}}_{s}}={{\bf{\Phi}}_{r}}{{\bf{\Phi}}_{s}}{\bf{x}}={\bf{\Phi}}{\bf{x}}={\bf{\Phi}}{\bf{\Psi}}{\bf{s}}={\bf{A}}{\bf{s}},$
(2)

where ${{\bf{\Phi}}_{r}}\in{\mathbb{R}}^{M\times{M_{s}}}$ is the projection
matrix modeling the random data loss, and it is determined by the correctly
received data samples. ${\bf{\Phi}}={{\bf{\Phi}}_{r}}{{\bf{\Phi}}_{s}}$ is the
equivalent projection matrix,
${\bf{A}}={\bf{\Phi}}{\bf{\Psi}}={{\bf{\Phi}}_{r}}{{\bf{\Phi}}_{s}}{\bf{\Psi}}$
is called the equivalent sensing matrix, and $\bf{y}\in{\mathbb{R}}^{M}$ is
the measurement vector composed of the successfully received data samples at
the FC.

Note that ${{\bf{\Phi}}_{r}}$ is a sparse binary measurement matrix which
contains one and only one “$1$” element in each row and at most one “$1$” in
each column, and “$0$” everywhere else. Mathematically, ${{\bf{\Phi}}_{r}}$ is
constructed as

${\bf{\Phi}}_{r}(i,j)=\left\\{{\begin{array}[]{*{20}{c}}{1\;\;\;\;\;\;\;\;\;\;\;j{\rm{=J}}(i)}\\\
{0\;\;\;\;\;\;\;\;\text{otherwise}}\end{array}}\right.,$ (3)

where $i$ is the row index of ${\bf{\Phi}}_{r}$, corresponding to the sequence
number of the received data samples, and $j$ is the column index. $J(i)$ is
the sequence number of the data sample sent by the IoT sensor node while being
the $i$-th received data sample at the FC. For example, assume that $7$ data
samples are sent from the node, and only $4$ of them are successfully received
at the FC. If their corresponding sending sequence number is $1$, $2$, $5$,
$7$, then ${\bf{\Phi}}_{r}$ is constructed as

${{\bf{\Phi}}_{r}}=\left[{\begin{array}[]{*{20}{c}}1&0&0&{\begin{array}[]{*{20}{c}}0&0&0&0\end{array}}\\\
0&1&0&{\begin{array}[]{*{20}{c}}0&0&0&0\end{array}}\\\
0&0&0&{\begin{array}[]{*{20}{c}}0&1&0&0\end{array}}\\\
0&0&0&{\begin{array}[]{*{20}{c}}0&0&0&1\end{array}}\end{array}}\right].$ (4)

Finally, at the FC, the original signal $\bf{x}$ can be exactly recovered from
the measurement vector $\bf{y}$ which is composed of a sufficient number of
successfully received data samples via
${\hat{\bf{x}}}={\bf{\Psi}}{\hat{\bf{s}}}$, where ${\hat{\bf{s}}}$ is the
solution to the following constrained optimization problem

${\hat{\bf{s}}}=\arg\min\limits_{\bf{s}}\|{\bf{s}}\|_{0},~{}~{}\text{s.t.}~{}{\bf{y}}={\bf{A}}{\bf{s}},$
(5)

which can be solved using the orthogonal matching pursuit (OMP) method [14].
Furthermore, ${\hat{\bf{s}}}$ can also be found from the solution to the
following convex optimization problem

${\hat{\bf{s}}}=\arg\min\limits_{\bf{s}}\|{\bf{s}}\|_{1},~{}~{}\text{s.t.}~{}{\bf{y}}={\bf{A}}{\bf{s}},$
(6)

which can be solved efficiently using the basis pursuit (BP) algorithm [15].

Herein, the signal recovery performance can be reflected by signal recovery
error, which is calculated as
$\frac{{\left\|{{\bf{x}}-{\bf{\hat{x}}}}\right\|_{2}}}{{\left\|{\bf{x}}\right\|_{2}}}$.
Obviously, a smaller signal recovery error indicates better signal recovery
performance.

Notably, according to CS theory, the equivalent projection matrix
${\bf{\Phi}}={{\bf{\Phi}}_{r}}{{\bf{\Phi}}_{s}}$ plays a critical role in
achieving accurate signal recovery. However, the projection matrix
${{\bf{\Phi}}_{r}}$ which models data loss during transmission is determined
by the pragmatic link quality. Specifically, ${{\bf{\Phi}}_{r}}$ is completely
determined by which transmitted data samples are correctly received at the FC.
Thus, we cannot design ${{\bf{\Phi}}_{r}}$. In contrast, we can carefully
choose the projection matrix ${{\bf{\Phi}}_{s}}$ used in CS-based source
coding at the IoT sensor node. Traditional projection matrices, including
dense random matrices, structured projection matrices, and partial basis
matrices, are either difficult to be implemented on low-cost IoT sensor nodes
or have limited applicability, which motivates our design of sparse Gaussian
matrix in the next section.

##  III Sparse Gaussian Matrix Design

In this section, we present the construction method of the sparse Gaussian
matrix, and theoretically prove its RIP.

###  III-A Sparse Gaussian Matrix Construction

Given a series of numbers $\\{{x_{i}}\\}_{i=1}^{n}$ which are independently
and identically distributed according to a zero-mean Gaussian distribution,
sparse Gaussian matrix is constructed by randomly placing these elements in a
null matrix (Note that the size of the null matrix is larger than the number
of used elements), i.e.,

${\bf{\Phi}}_{sG}=\left[{\begin{array}[]{*{20}{c}}{{x_{1}}}&0&{..}&{{x_{2}}}&0\\\
0&{..}&{{x_{i}}}&0&{..}\\\ 0&{{x_{i+1}}}&0&{..}&{{x_{i+2}}}\\\
0&{..}&0&{{x_{n}}}&0\end{array}}\right],$ (7)

or we can construct it in a structured manner as an analogue to Toeplitz
matrix, i.e.,

${\bf{\Phi}}_{sG}=\left[{\begin{array}[]{*{20}{c}}{{x_{1}}}&0&{..}&{{x_{2}}}&0\\\
0&{{x_{i}}}&0&{..}&{{x_{i+1}}}\\\ {{x_{n-2}}}&0&{{x_{n-3}}}&{..}&0\\\
0&{{x_{n}}}&{..}&{{x_{n-1}}}&0\end{array}}\right].$ (8)

When implementing a sparse Gaussian matrix in an IoT sensor node, the first
step is to generate a null matrix according to the predefined matrix size.
Then, the locations of a small number of nonzero elements are determined
according to a random number generator. Finally, the values of the nonzero
elements are determined according to a Gaussian-distributed (zero mean and
unit variance) random number generator, while the rest locations in the null
matrix are set to $0$.

###  III-B RIP Proof for Sparse Gaussian Matrix

A Matrix ${\bf{\Phi}}$ is said to satisfy RIP of order $K$ with parameter
${\delta_{K}}\in(0,1)$, if

$(1-{\delta_{K}})\|{\bf{\alpha}}\|_{2}^{2}\leq\|{\bf{\Phi\alpha}}\|_{2}^{2}\leq(1+{\delta_{K}})\|{\bf{\alpha}}\|_{2}^{2}$
(9)

holds for all ${\bf{\alpha}}\in{\mathbb{R}}^{N}$ with no more than $K$ nonzero
entries. In other words, $\bf{\Phi}$ satisfies RIP ($K,{\delta_{K}}$).

In practical application scenarios, however, the signals of interest (i.e.,
$\bf{x}$) are usually sparse under an orthogonal transform basis $\bf{\Psi}$
rather than the canonical basis. Therefore, it’s more convenient to consider
the $\bf{\Psi}$-RIP as follows

$(1-{\delta_{K}})\|{\bf{x}}\|_{2}^{2}\leq\|{\bf{\Phi
x}}\|_{2}^{2}\leq(1+{\delta_{K}})\|{\bf{x}}\|_{2}^{2},$ (10)

for all $\bf{x}$ satisfying $\|{{{\bf{\Psi}}^{H}}{\bf{x}}}\|_{0}\leq K$, where
${\bf{\Psi}}^{H}$ denotes the conjugate transpose of $\bf{\Psi}$.

According to the definition of RIP, as long as the eigenvalues of all
submatrices’ gram matrix are in the range of
$({1-{\delta_{K}}},{1+{\delta_{K}}})$, where submatrices are formed by
retaining no more than $K$ columns of ${\bf{\Phi}}$, then the matrix
${\bf{\Phi}}$ satisfies the RIP condition.

######  Lemma 1.

The eigenvalues of a matrix ${\bf{\Phi}}\in{\mathbb{R}}^{m\times m}$ all lie
in the union of $m$ discs ${d_{i}}={d_{i}}({c_{i}},{r_{i}})$, $i=1,2,...,m$,
centered at ${c_{i}}={{\bf{\Phi}}_{ii}}$ with radius

${r_{i}}=\sum\limits_{j=1,j\neq i}^{m}{|{{\Phi}_{ij}}|},$ (11)

where ${{\Phi}_{ii}}$ and ${{\Phi}_{ij}}$ denote the diagonal and off-diagonal
elements of $\bf{\Phi}$, respectively. For the proof of Lemma 1, please refer
to [16].

To prove that the eigenvalues of all submatrices’ gram matrix are in the range
of $({1-{\delta_{K}}},{1+{\delta_{K}}})$, we resort to the following Lemma.

######  Lemma 2.

Suppose ${\delta_{d}},~{}{\delta_{o}}>0$ and
${\delta_{d}}+{\delta_{o}}={\delta_{K}}\in(0,1)$, and if ${G_{ii}}$, the
diagonal elements of matrix ${\bf{G}}={\bf{\Phi}}^{T}{\bf{\Phi}}$ satisfy
$|{G_{ii}}-1|<{\delta_{d}}$ and the off-diagonal elements ${G_{ij}~{}(i\neq
j)}$ satisfy $|{G_{ij}}|<{\delta_{o}}/K$, then ${\bf{\Phi}}$ satisfies RIP
($K,{\delta_{K}}$).

###### Proof.

Please see Appendix A in the online appendix [17]. ∎

If the elements of $\bf{\Phi}$ are independently and identically distributed
according to a Gaussian distribution, then ${G_{ii}}$ is the sum of squares of
Gaussian random variables, and ${G_{ij}~{}(i\neq j)}$ is the sum of products
between independent Gaussian random variables. The range of ${G_{ii}}$ and
${G_{ij}~{}(i\neq j)}$ can be determined by the following Lemma.

######  Lemma 3.

Given $\\{{x_{i}}\\}_{i=1}^{n}$, assume that it has $kn$ ($0<k<1$) nonzero
elements obeying independent and identical Gaussian distribution with zero
mean and variance $1/kn$, then the sum of squares of ${x_{i}}$’s satisfies

$\Pr\left({|\sum\limits_{i=1}^{n}{x_{i}^{2}-1}|\geq{\delta_{d}}}\right)\leq
2\exp(-\frac{{nk\delta_{d}^{2}}}{{16}}).$ (12)

###### Proof.

Please see Appendix B in the online appendix [17]. ∎

######  Lemma 4.

Given two sets of numbers $\\{{x_{i}}\\}_{i=1}^{n}$ and
$\\{{y_{i}}\\}_{i=1}^{n}$, each with $kn$ nonzero elements, which are
independently and identically distributed according to a Gaussian distribution
with zero mean and variance $1/kn$, then

$\Pr\left({|\sum\limits_{i=1}^{n}{{x_{i}}{y_{i}}}|\geq t}\right)\leq
2\exp(-\frac{{n{t^{2}}}}{{4+2t}}),$ (13)

where $0\leq t\leq 1$.

###### Proof.

Assume $\\{{x_{i}}\\}_{i=1}^{n}$ and $\\{{y_{i}}\\}_{i=1}^{n}$ are independent
and identical Gaussian random variables with zero mean and variance $1/n$, and
based on [18], we have

$\Pr\left({|\sum\limits_{i=1}^{n}{{x_{i}}{y_{i}}}|\geq t}\right)\leq
2\exp(-\frac{{{t^{2}}}}{{4{\sigma^{2}}(n{\sigma^{2}}+t/2)}}).$ (14)

Substituting $n=kn$ and ${\sigma^{2}}=1/n$ into Eq. (14), we have Lemma 4. ∎

######  Theorem 5.

Assume that ${\bf{\Phi}}\in{\mathbb{R}}^{m\times n}(n>2)$ is a sparse matrix,
whose nonzero elements are independently and identically distributed according
to a Gaussian distribution with zero mean and and variance $1/m$, then for any
${\delta_{K}}\in(0,1)$, there exist constants ${c_{1}}$ and ${c_{2}}$ which
are only dependent on ${\delta_{K}}$ and $K$, such that as long as
$m>{c_{2}}\ln n$, $\bf{\Phi}$ satisfies RIP($K,{\delta_{K}}$) with probability
exceeding $1-\exp(-{c_{1}}m)$.

###### Proof.

Please see Appendix C in the online appendix [17]. ∎

Theorem 5 has proven the RIP of sparse Gaussian matrix ${\bf{\Phi}}_{sG}$. In
our application scenario of compressive data collection in IoT, however, the
equivalent projection matrix is ${{\bf{\Phi}}_{r}}{\bf{\Phi}}_{sG}$, where
${\bf{\Phi}}_{r}$ is a sparse binary measurement matrix. In other words,
${{\bf{\Phi}}_{r}}{\bf{\Phi}}_{sG}$ is a submatrix of ${\bf{\Phi}}_{sG}$
formed by randomly selecting a subset of rows from ${\bf{\Phi}}_{sG}$.
Therefore, we next present the RIP of ${{\bf{\Phi}}_{r}}{\bf{\Phi}}_{sG}$.

######  Corollary 6.

[RIP for submatrices (by selecting a subset of rows) of sparse Gaussian
matrix] Assume that ${\bf{\Phi}}\in{\mathbb{R}}^{m\times n}(n>2)$ is a sparse
matrix, whose nonzero elements are independently and identically distributed
according to a Gaussian distribution with zero mean and variance $1/n$, then
with regard to submatrices of $\bf{\Phi}$ by selecting $m^{\prime}$ rows from
$\bf{\Phi}$, there exist constants ${c_{3}}$ and ${c_{4}}$ which are only
dependent on ${\delta_{K}}$, $K$ and the proportion
$\mu=\frac{{m^{\prime}}}{m}$, such that as long as $m>{c_{4}}\ln n$,
submatrices of $\bf{\Phi}$ satisfy RIP($K,{\delta_{K}}$) with probability
exceeding $1-\exp(-{c_{3}}m)$.

###### Proof.

Please see Appendix D in the online appendix [17]. ∎

##  IV Performance Evaluation

In this section, we evaluate the performance of employing the designed sparse
Gaussian matrix to perform CS-based source coding for compressive data
collection in IoT and make a comparison with traditional projection matrices.
We utilize a real-world dataset from SensorScope [19] and tailor a temperature
signal of size $N=1024$ as the original signal to be transmitted in the
experiments. We would like to point out that we focus mainly on single-hop
transmission-based data collection in IoT in this paper. Thus, the process of
data collection (as detailed in Section II) from different sensor nodes is
identical. Therefore, in the subsequent experiments, we only consider the case
where one sensor node transmits data to the FC over a lossy channel, and the
results reported in this paper can be easily extended to the case where there
are multiple sensor nodes transmitting data to the FC.

Figure 2: Signal recovery performance comparison of using different projection
matrices.

Figure 3: Signal recovery performance comparison with packet length set to
$16$.

###  IV-A Signal Recovery Performance

We first compare sparse Gaussian matrix and traditional projection matrices in
terms of signal recovery performance. The result of signal recovery error
comparison among using different projection matrices at the sensor node before
transmission is shown in Fig. 3. Note that in this experiment, we assume that
the projection operation is dimensional-invariant, and the number of received
data samples $M$ varies from $64$ to $384$ with a step length of $32$. Herein,
the used sparse Gaussian matrix is of size $1024\times 1024$, and it is
constructed as follows. First, we generate a null matrix of the same size.
Then, we randomly choose $10\%$ (rounded to the nearest integer) locations in
the null matrix to place nonzero elements. Finally, the values of the nonzero
elements are determined according to a Gaussian-distributed (zero mean and
unit variance) random number generator, while the rest locations in the null
matrix are set to $0$. Note that in the subsequent experiments, the used
sparse Gaussian matrices are all constructed in the same way unless otherwise
specified. We can observe from the figure that utilizing dense random matrices
(i.e., Gaussian and Bernoulli matrices), partial basis matrices, and the
proposed sparse Gaussian matrix achieves similar signal recovery performance.
However, when using Toeplitz matrices, a more significant recovery error is
obtained under the same number of received data samples. This is because the
structure of Toeplitz matrices is broken during lossy transmission from the
sensor node to the FC.

Considering that Toeplitz matrices achieve poor signal recovery performance
and that dense random matrices induce high resource cost for sensor nodes
(which will be validated later), we next make a further comparison between
sparse Gaussian matrix and partial basis matrix with packet length taken into
consideration. Assume the packet length is set to $16$, that is, $16$
consecutive data samples are first organized into a data packet, and then all
the generated data packets are transmitted to the FC. The result of signal
recovery error comparison is shown in Fig. 3. As noted in the figure, when
packet length is set to $16$, using partial basis matrices as the projection
matrix results in more significant recovery error than using sparse Gaussian
matrix. This is because when adopting a large packet length, if a data packet
is lost during transmission, all the data samples in it will be missing,
leading to block data loss. However, partial basis matrices are only suitable
to the case of random data loss (i.e., the packet length is $1$, that is, each
transmitted data sample is organized into an independent data packet).

(a) Partial basis matrix

(b) Sparse Gaussian matrix

Figure 4: Signal recovery comparison using a sparse signal in the canonical
basis.

Another limitation of partial basis matrices is that they can only be applied
to the scenario when the target signal is sparse under some orthogonal
transform basis. However, when the target signal is itself sparse. That is,
the sparsifying basis is the canonical basis, partial basis matrices fail to
achieve successful signal recovery. To demonstrate that partial basis matrices
cannot promise accurate signal recovery when the target signal is sparse under
the canonical basis. We synthesize a sparse signal $\bf{x}$ under the
canonical basis with a dimension of $N=1024$. Only $50$ elements of $\bf{x}$
are nonzero (varying from $-1$ to $1$) while most elements are zero. We
respectively employ partial basis matrices and the designed sparse Gaussian
matrix to perform CS-based source coding at the IoT sensor node, and the
number of received data samples is set to $64$. The signal recovery results
using the two kinds of projection matrix are shown in Fig. 4. We can observe
from the figure that accurate signal recovery is achieved when using the
designed sparse Gaussian matrix to perform CS-based source coding, while it
fails to achieve accurate signal recovery when using partial basis matrices,
which further validates the superior performance of the designed sparse
Gaussian matrix and the limitations of partial basis matrices.

###  IV-B Resource Cost

Considering that many low-cost IoT sensor nodes are resource-constrained
(e.g., computational capability, storage capacity), it is inefficient or even
impractical to implement complicated operations on them. Now, we make a
comparison between sparse Gaussian matrix and dense random matrices (e.g.,
Gaussian and Bernoulli matrices) in terms of time and memory cost for
projection matrix construction. We implement the three kinds of projection
matrices on STM32W108 chips that offer IEEE $802.15.4$ communication standard,
with a clock speed of $24$ Mhz, a RAM of $12$ KB, a ROM of $128$ KB, and $4$
AA batteries for power supply.

Figure 5: Time cost comparison among Gaussian, Bernoulli, and sparse Gaussian
matrix for matrix construction.

Figure 6: Memory cost comparison among Gaussian, Bernoulli, and sparse
Gaussian matrix for matrix construction.

The comparison results of time cost and memory cost for matrix construction
are respectively shown in Fig. 6 and Fig. 6 (the matrix is of size $N\times
N$). Note that a random Gaussian number is quantified by $16$ bits, and one
element in Bernoulli matrix is quantified by $1$ bit. Note that when there are
only a few nonzero elements in Bernoulli matrix, we only store the positions
of these nonzero elements, which is more efficient. Also, the number of
nonzero elements in sparse Gaussian matrix will directly impact the resource
cost of sensor nodes. We can see from Fig. 6 that it costs the most time to
construct a random Gaussian matrix, which is self-explanatory. When $N=64$,
sparse Gaussian matrix costs a little more time than Bernoulli matrix and
remains the most efficient one to construct when $N$ increases. As for the
memory cost shown in Fig. 6, sparse Gaussian matrix consumes almost the same
memory as Bernoulli matrix when $N=64$, while remains the most memory-saving
for rest cases. Specifically, when $N=1024$, constructing a Bernoulli matrix
with only two nonzero elements in each row needs $8$ KBytes of memory, while
only $4$ KBytes are enough for sparse Gaussian matrix. Besides, it costs
$1792$ and $763$ ms to construct such a Bernoulli matrix and sparse Gaussian
matrix, respectively.

##  V Conclusion

In this paper, to achieve efficient and resource-saving CS-based source coding
for compressive data collection in IoT, we design a novel, simple projection
matrix, named sparse Gaussian matrix, which is easy and efficient to implement
practical IoT systems. Specifically, we first present the construction method
of sparse Gaussian matrix and then prove its RIP theoretically. Finally, we
conduct extensive experiments to demonstrate that employing the designed
sparse Gaussian matrix to perform CS-based source coding at the sensor node
can significantly save time and memory cost while guaranteeing satisfactory
signal recovery performance.

## References

  * [1] T. Qiu, N. Chen, K. Li, M. Atiquzzaman, and W. Zhao, “How can heterogeneous internet of things build our future: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 20, no. 3, pp. 2011–2027, 2018.
  * [2] L. Wu, P. Sun, Z. Wang, Y. Yang, and Z. Wang, “Toward efficient compressed-sensing-based RFID identification: A sparsity-controlled approach,” _IEEE Internet of Things Journal_ , vol. 7, no. 8, pp. 7714–7724, 2020.
  * [3] Y. Qian, D. Wu, W. Bao, and P. Lorenz, “The Internet of Things for smart cities: Technologies and applications,” _IEEE Network_ , vol. 33, no. 2, pp. 4–5, 2019.
  * [4] R. G. Baraniuk, “Compressive sensing [lecture notes],” _IEEE Signal Processing Magazine_ , vol. 24, no. 4, pp. 118–121, 2007.
  * [5] P. Sun, Z. Tian, Z. Wang, and Z. Wang, “PRSS: A prejudiced random sensing strategy for energy-efficient information collection in the internet of things,” _IEEE Internet of Things Journal_ , vol. 6, no. 2, pp. 2717–2728, 2018.
  * [6] L. Wu, K. Yu, D. Cao, Y. Hu, and Z. Wang, “Efficient sparse signal transmission over a lossy link using compressive sensing,” _Sensors_ , vol. 15, no. 8, pp. 19 880–19 911, 2015.
  * [7] L. Wu, P. Sun, M. Xiao, Y. Hu, and Z. Wang, “Sparse signal ALOHA: a compressive sensing-based method for uncoordinated multiple access,” _IEEE Communications Letters_ , vol. 21, no. 6, pp. 1301–1304, 2017.
  * [8] L. Kong, M. Xia, X.-Y. Liu, M.-Y. Wu, and X. Liu, “Data loss and reconstruction in sensor networks,” in _2013 Proceedings IEEE INFOCOM_. IEEE, 2013, pp. 1654–1662.
  * [9] X. Li, X. Tao, and G. Mao, “Unbalanced expander based compressive data gathering in clustered wireless sensor networks,” _IEEE Access_ , vol. 5, pp. 7553–7566, 2017.
  * [10] H. Mamaghanian, N. Khaled, D. Atienza, and P. Vandergheynst, “Compressed sensing for real-time energy-efficient ECG compression on wireless body sensor nodes,” _IEEE Transactions on Biomedical Engineering_ , vol. 58, no. 9, pp. 2456–2466, 2011.
  * [11] G. Zhang, S. Jiao, X. Xu, and L. Wang, “Compressed sensing and reconstruction with bernoulli matrices,” in _The 2010 IEEE International Conference on Information and Automation_. IEEE, 2010, pp. 455–460.
  * [12] W. U. Bajwa, J. D. Haupt, G. M. Raz, S. J. Wright, and R. D. Nowak, “Toeplitz-structured compressed sensing matrices,” in _2007 IEEE/SP 14th Workshop on Statistical Signal Processing_. IEEE, 2007, pp. 294–298.
  * [13] P. Sun, L. Wu, Z. Wang, Y. Feng, and Z. Wang, “SCRA: Structured compressive random access for efficient information collection in IoT,” _IEEE Internet of Things Journal_ , vol. 7, no. 3, pp. 2356–2367, 2020.
  * [14] J. A. Tropp, “Greed is good: Algorithmic results for sparse approximation,” _IEEE Transactions on Information Theory_ , vol. 50, no. 10, pp. 2231–2242, 2004.
  * [15] E. J. Candès and M. B. Wakin, “An introduction to compressive sampling,” _IEEE Signal Processing Magazine_ , vol. 25, no. 2, pp. 21–30, 2008.
  * [16] R. S. Varga, _Geršgorin and his circles_. Springer Science & Business Media, 2010, vol. 36.
  * [17] P. Sun, L. Wu, and Z. Wang, “Online appendix,” 2021. [Online]. Available: https://www.dropbox.com/s/fcmnr3updvd3hmv/appendix_sG.pdf?dl=0
  * [18] J. Haupt, W. U. Bajwa, G. Raz, and R. Nowak, “Toeplitz compressed sensing matrices with applications to sparse channel estimation,” _IEEE Transactions on Information Theory_ , vol. 56, no. 11, pp. 5862–5875, 2010.
  * [19] F. Ingelrest, G. Barrenetxea, G. Schaefer, M. Vetterli, O. Couach, and M. Parlange, “Sensorscope: Application-specific sensor network for environmental monitoring,” _ACM Transactions on Sensor Networks (TOSN)_ , vol. 6, no. 2, p. 17, 2010.


# Weighted Distance Nearest Neighbor Condensing

Lee-Ad Gottlieb  Timor Sharabi  Roi Weiss

(Ariel University)

###### Abstract

The problem of nearest neighbor condensing has enjoyed a long history of
study, both in its theoretical and practical aspects. In this paper, we
introduce the problem of weighted distance nearest neighbor condensing, where
one assigns weights to each point of the condensed set, and then new points
are labeled based on their weighted distance nearest neighbor in the condensed
set.

We study the theoretical properties of this new model, and show that it can
produce dramatically better condensing than the standard nearest neighbor
rule, yet is characterized by generalization bounds almost identical to the
latter. We then suggest a condensing heuristic for our new problem. We
demonstrate Bayes consistency for this heuristic, and also show promising
empirical results.

##  1 Introduction

The nearest neighbor (NN) classifier, introduced by Fix and Hodges (1951), is
an intuitive and popular learning tool. In this model, a learner observes a
sample of (typically binary) labeled points, and given a new point to be
classified, assigns the new point the same label as its nearest neighbor in
the sample. It was subsequently demonstrated by Cover and Hart (1967) that
when no label noise is present, the nearest neighbor classifier’s expected
error converges to zero as the sample size grows. This and other results
helped spawn a deep body of research into proximity-based classification
(Devroye et al., 1996; Shalev-Shwartz and Ben-David, 2014).

Nearest neighbor classifiers enjoy other advantages as well. They require only
a distance function on the points, and do not even require that the host space
be metric. They also extend naturally to the multi-class setting. Yet they are
not without their disadvantages: For example, a naive nearest neighbor
approach may require storing the entire sample. To address the disadvantages
of the NN classifier, Hart (1968) introduced the technique of sample
compression for the NN classifier. This work defined the minimum consistent
subset problem (also called the nearest neighbor condensing problem): Given a
sample, find a minimal subset of the sample that is consistent with it,
meaning that for every point of the sample, its nearest neighbor in the subset
(that is the condensed set) has the same label. Hart (1968) further suggested
a heuristic for the NN condensing problem. Analysis of this problem, as well
as the creation of new heuristics for it, has been the subject of extensive
research since its introduction (Gates, 1972; Ritter et al., 1975; Devroye et
al., 1996; Wilson and Martinez, 2000).

#### Our Contribution

In this paper, we introduce a novel modification of the NN condensing problem.
In our new condensing problem (presented formally in Section 2), each point of
the condensed set is also assigned a weight. We modify the distance function
to consider _weighted distance_ , meaning that the distance from a new point
to a point in the condensed set is their original distance divided by the
weight of the point in the condensed set. It follows that assigning high
weight to a point in the condensed set increases its influence on the labeling
of new points. We call the new problem of choosing a condensed set and
assigning its weights the _weighted distance nearest neighbor condensing
problem_.

We proceed with an in-depth study of the statistical properties of weighted
distance condensing (Section 3). Crucially, we find that our model allows
dramatically better condensing than what is possible under standard (that is,
unweighted) NN condensing: There are families of instances wherein the optimal
condensing under unweighted NN rule is of size $\Theta(n)$, while condensing
under the weighted NN (WNN) rule yields a condensed set of size exactly 2
(Theorem 1). At the same time, we demonstrate generalization bounds for
condensing under the WNN rule which are almost identical to those previously
known for the NN rule (Theorem 4). This means that the much more powerful
weighted rule can be adopted with only negligible increase in the variance of
the model, so that the more powerful rule does not contribute to overfitting.

Having established these statistical properties of WNN condensing, we suggest
a greedy-based heuristic for this problem, that is the identification of a
condensed set and the assignment of weights to members of this set (Section
4). We further demonstrate that the suggested heuristic is a member of a broad
set of classifiers which are Bayes consistent, thereby lending statistical
support to its use.

After deciding on a heuristic for our condensing problem, we compare its
empirical condensing abilities to those of popular heuristics for the
unweighted NN problem (Section 6). We find that that the condensing bounds of
our heuristic compare favorably to the others, and this suggests that further
research on heuristics for WNN condensing is a promising direction.

Finally, in Section 5, we consider the related problem of finding a nearest
neighbor for a query point, under weighted distances – this is exactly what
must be done to label a new point under WNN condensing. We give a novel
weighted distance approximate nearest neighbor search algorithm based on the
navigating nets of Krauthgamer and Lee (2004).

###  1.1 Related Work

The nearest neighbor condensing problem is known to be NP-hard (Wilfong, 1991;
Zukhba, 2010), and Hart (1968) provided the first heuristic for it. Many other
heuristics have been suggested since, and we mention only a few of them here:
Gates (1972) introduced the reduced nearest neighbor (RNN) rule heuristic to
iteratively contract the sample set. Ritter et al. (1975) introduced the
selective subset heuristic, which additionally guarantees that for any sample
point, the distance to its nearest neighbor in the compressed set is less than
the distance to any sample point with opposite label. Barandela et al. (2005)
subsequently suggested a modification to this algorithm, which they called
modified selected subset (MSS). Angiulli (2005) introduced the fast nearest
neighbor condensing (FCNN) heuristic, while Flores-Velazco (2020) introduced
the RSS and VSS heuristics, which modify the FCNN algorithm to improve its
behavior in cases where the points are too close to each other. Another
popular heuristic, modified condensed nearest neighbor (MCNN), was introduced
by Devi and Murty (2002).

No concrete algorithmic condensing bounds were known for NN condensing until
the work of Gottlieb et al. (2018): They derived hardness-of-approximation
results, and designed an algorithm called NET, which computes in polynomial
time an approximation to the minimum subset almost matching the hardness
bounds. This approach was later extended by Gottlieb and Ozeri (2019) to
asymmetric distance function. Also related to this is the result of Gottlieb
and Kontorovich (2022), which presented non-uniform packing, that is using
balls with different radii.

As for the statistical properties of NN condensing rules, Devroye et al.
(1996, Chapter 19) established Bayes consistency for an intractable rule that
searches for a condensed set of fixed, data-independent size, minimizing the
empirical error on the entire sample. They showed that universal Bayes
consistency is achieved in finite-dimensional spaces provided the size of the
condensed set is sub-linear in the sample size. Hanneke et al. (2021)
introduced a computationally-efficient data-dependent sample-compression NN
rule, termed OptiNet, that computes a net of the samples and associates each
point of the condensed set with the majority vote label in its Voronoi cell.
They showed that OptiNet is universally Bayes consistency in any separable
metric space. A simpler sub-sampling NN rule achieving universal Bayes
consistency in separable metric spaces was demonstrated by Györfi and Weiss
(2021), establishing also error rates. Xue and Kpotufe (2018) studied the
error rates achieved by more complex sub-sampling NN rules. Lastly, Kerem and
Weiss (2023) studied jointly-achievable error and compression rates for
OptiNet under a margin condition.

###  1.2 Preliminaries

#### Metric Space.

A _metric_ $d$ defined on a point set $\mathcal{X}$ is a positive symmetric
function satisfying the triangle inequality, i.e. $d(x,y)\leq d(x,z)+d(z,y)$.
The set $\mathcal{X}$ and metric $d$ together define the metric space
$(\mathcal{X},d)$. Let $B(x,r)$ denote the (open) ball centered at $x$ with
radius $r$; a point $y\in\mathcal{X}$ is in $B(x,r)$ if $d(x,y)<r$.

#### Notation.

We use $[k]$ to denote $\\{1,\ldots,k\\}$. We define the distance between a
point $y$ and set $S$ as the distance of $y$ to the closest point in $S$, that
is $d(x,S)=\min_{y\in S}d(x,y)$. For a set $S$, we denote its cardinality by
$|S|$.

##  2 Nearest neighbor rules

Given a metric space $(\mathcal{X},d)$ and a labeled sample
$S\subset\mathcal{X}$ (where $l(x)$ is the label of point $x\in\mathcal{X}$),
the nearest neighbor condensing problem is to find a subset $\tilde{S}\subset
S$ of minimal cardinality, such that the nearest neighbor rule on $\tilde{S}$
classifies all sample points in $S$ correctly; that is, for any point $x\in
S$,
$l(x)=l(\displaystyle\operatorname{\textup{argmin}}_{y\in\tilde{S}}\left(d\left(x,y\right)\right))$.

Now let $w:\mathcal{X}\to(0,\infty)$ be a positive weight function, and define
the weighted distance

$\displaystyle\tilde{d}(x,x^{\prime})=\frac{d(x,x^{\prime})}{w(x)\cdot
w(x^{\prime})},\qquad x,x^{\prime}\in\mathcal{X}.$

This is our weighted distance nearest neighbor (WNN) rule, under which we may
define a WNN classifier:

$\displaystyle
h_{(\tilde{S},w)}(x)=l(\arg\min_{y\in\tilde{S}}\tilde{d}(y,x)),\qquad
x\in\mathcal{X}.$

Note that the weighted distance may not satisfy the triangle inequality. In
the weighted condensing problem, we seek a subset $\tilde{S}\subset S$ and a
weight assignment $w$ for $\tilde{S}$ (with $w(x)=1$ for all
$x\in\mathcal{X}\setminus\tilde{S}$), such that for each point $x\in S$, the
weighted distance nearest neighbor of $x$ in $\tilde{S}$ has the same label as
$x$, $h_{(\tilde{S},w)}(x)=l(x)$.

It is easy to see that WNN is a generalization of the NN rule, as the latter
can be recovered by simply taking all weights to be equal to 1. Let us
motivate our weighted distance function by illustrating the effect of
weighting on the Euclidean decision boundary between two points. Consider two
points in the Euclidean plane, $p_{1}=(x_{1},y_{1})$ and
$p_{2}=(x_{2},y_{2})$. If $w(p_{1})=w(p_{2})$, then the WNN decision boundary
is equivalent to the NN decision boundary, defined by

$\sqrt{(x_{1}-x)^{2}+(y_{1}-y)^{2}}=\sqrt{(x_{2}-x)^{2}+(y_{2}-y)^{2}},$

which can be simplified to a line in slope-intercept form:

$y=x\cdot\frac{x_{1}-x_{2}}{y_{2}-y_{1}}+\frac{-x_{1}^{2}+x_{2}^{2}-y_{1}^{2}+y_{2}^{2}}{2(y_{2}-y_{1})}.$

In contrast, when $w(p_{1})\neq w(p_{2})$, the decision boundary is defined by

$\frac{\sqrt{(x_{1}-x)^{2}+(y_{1}-y)^{2}}}{w_{1}}=\frac{\sqrt{(x_{2}-x)^{2}+(y_{2}-y)^{2}}}{w_{2}}.$

This can be simplified to the standard equation of a circle

$\displaystyle\left(x+\frac{w_{1}^{2}x_{2}-w_{2}^{2}x_{1}}{w_{2}^{2}-w_{1}^{2}}\right)^{2}+\left(y+\frac{w_{1}^{2}y_{2}-w_{2}^{2}y_{1}}{w_{2}^{2}-w_{1}^{2}}\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{w_{1}^{2}y_{2}^{2}+w_{1}^{2}x_{2}^{2}-w_{2}^{2}y_{1}^{2}-w_{2}^{2}x_{1}^{2}}{w_{2}^{2}-w_{1}^{2}}$
$\displaystyle+\left(\frac{w_{1}^{2}x_{2}-w_{2}^{2}x_{1}}{w_{2}^{2}-w_{1}^{2}}\right)^{2}+\left(\frac{w_{1}^{2}y_{2}-w_{2}^{2}y_{1}}{w_{2}^{2}-w_{1}^{2}}\right)^{2}.$

See Figure 1. The fact that WNN induces a circular boundary (and in higher
dimension, a ball separator) will be useful for our proofs and constructions.

Figure 1: Illustration of decision boundary for equal (left) and unequal
weights (right). In the right figure, $w(p_{1})=1.5$ and $w(p_{2})=1$, where
$p_{1}$ is its left point and $p_{2}$ is its right point.

While the distance function for nearest neighbor condensing rules is often
taken to be the Euclidean norm, all our results below hold for all metric
distance functions.

##  3 Properties of weighted distance nearest neighbor

In this section, we establish condensing properties under WNN, especially in
comparison to condensing properties already known for the regular unweighted
nearest neighbor (NN) rule. We show that the former rule is strictly more
powerful: It can always yield condensing as good as the latter, and in some
cases better by a factor of $\Theta(n)$. At the same time, we derive
generalization bounds for WNN condensing that are essentially the same as
those known for NN condensing, so that the utilization of a more powerful tool
does not lead to an increase in generalization error.

###  3.1 Condensing bounds

As weighted nearest neighbor generalizes unweighted nearest neighbor, it can
only improve the condensing. We can in fact show the following:

######  Theorem 1.

For any $n$, there exists an $n$-point data-set that can be condensed to 2
candidates under the WNN rule, but requires $\Theta(n)$ candidates under the
NN rule.

In place of simply presenting a construction achieving the bound of Theorem 1,
we will instead present a new condensing rule we call the ball cover (BC)
rule, and show that WNN generalizes this rule as well. We then demonstrate
that condensing under NN and BC is incomparable, in that each rule admits
$n$-point sets that it can condense to a constant size, but which the other
cannot condense below $\Theta(n)$ points. This expanded explanation will yield
a better understanding of the power of WNN, and motivate the heuristic of
Section 4 below.

#### Ball Cover Rule.

We define another rule for condensing, the ball cover (BC) rule: Given the
input points $S\subset\mathcal{X}$, we must produce a subset
$\tilde{S}\subset\mathcal{X}$ of minimum cardinality, and also assign each
point $x_{i}\in\tilde{S}$ a radius $r_{i}$. Let $B_{i}=B(x_{i},r_{i})$. We
require that for any two points $x_{i},x_{j}\in\tilde{S}$ with $l(x_{i})\neq
l(x_{j})$, that $r_{i},r_{j}<d(x_{i},x_{j})$. It follows that no ball contains
sample points of the opposite label. The decision rule simply assigns a point
$x\in S$ the same label as the center of a ball containing $x$. A valid BC
condensing satisfies that every $x\in S\setminus\tilde{S}$ is found in a ball
$B_{i}$ satisfying $l(x)=l(x_{i})$. (There is however a caveat relating to the
labeling of points not in the sample: These points can fall into multiple
balls, or no ball at all. In these cases, one may impose some arbitrary
decision rule, such as a priority over the balls.)

The BC rule is motivated by the NET algorithm of Gottlieb et al. (2018). This
algorithm can be viewed as covering the space with balls of equal radius. The
BC rule is an extension of the NET approach to balls of different radii.

It is easy to show that WNN generalizes the BC rule: Given a condensed set
$\tilde{S}$ with assigned radii $r_{i}$, a WNN classifier can be produced by
taking the same points of $\tilde{S}$, and assigning weight $w(x_{i})=r_{i}$
for all $x_{i}\in\tilde{S}$. Consider any point $x\in S\setminus\tilde{S}$
falling in $B_{i}$ but not in $B_{j}$, and we have that
$\tilde{d}(x,x_{i})=\frac{d(x,x_{i})}{w(x_{i})}<\frac{r_{i}}{r_{i}}=1,$ while
$\tilde{d}(x,x_{j})=\frac{d(x,x_{j})}{w(x_{j})}\geq\frac{r_{j}}{r_{j}}=1,$ so
that the WNN rule is indeed consistent with the BC rule on the sample.

#### Comparison between NN and BC.

It remains to prove the following lemma, concerning condensing under the NN
and BC rules:

######  Lemma 2.

For any $n$, there exists an $n$-point data-set that can be condensed to 2
candidates under the NN rule, but requires $\Theta(n)$ candidates under the BC
rule.

Likewise, for any $n$, there exists an $n$-point data-set that can be
condensed to 2 candidates under the BC rule, but requires $\Theta(n)$
candidates under the NN rule.

As WNN generalizes BC, Theorem 1 follows immediately from Lemma 2. It remains
to prove the lemma.

###### Proof of Lemma 2.

For the first item of the lemma, assume without loss of generality that $n$ is
even, and set $\gamma=n/2$. Our example set $\mathcal{X}$ will have $\gamma$
red points and $\gamma$ blue points, with a diameter $\Theta(n)$ and minimum
distance of $1$ between the points. Let $c=\frac{1}{2}$, and add to the set
$\gamma$ red points at positions $\\{(i,c):i\in[\gamma]\\}$, and $\gamma$ blue
points at positions $\\{(i,-c):i\in[\gamma]\\}$. See Figure 2.

Now under the NN rule, there exists a solution which uses only two points:
This solution $S$ takes the red point at $(1,c)$ together with the blue point
at $(1,-c)$: Take any red point at $(i,c)$, and its distance from the red
candidate is $i-1$, while its distance from the blue candidate is exactly
$\sqrt{(i-1)^{2}+4c^{2}}>i-1$. A similar argument applies to the blue points,
and so we conclude that $S$ is a consistent condensing of $\mathcal{X}$.

Turning to the BC rule, we show that any solution under this rule must have
all $n$ points: Assume by contradiction that we can consistently cover all the
points of $\mathcal{X}$ with only $k$ balls, where $k<n$. This implies that
there exists some solution ball which covers 2 or more points of the same
color; assume without loss of generality that this ball is red, and its center
is $p_{i}=(i,c)$. As this ball covers more than a single red point, its radius
must be greater than $1$, but then it contains the blue point $(i,-c)$, which
is forbidden. We conclude that no ball contains more than one point, and so
the optimal solution under BC must contain exactly $n$ points.

Figure 2: Left: A set that admits good condensing under the NN rule, but not
under the BC rule. Right: A set that admits good condensing under the BC rule,
but not under the NN rule.

For the second item of the lemma, assume without loss of generality that $n$
is odd, set $\gamma=\frac{n-1}{2}$, and further assume that $\gamma$ is odd.
Our example has $\gamma$ blue points and $\gamma+1$ red points: Let the points
$\\{(0,2i):i\in[\gamma]\\}$ be red, and the points
$\\{(1,2i+1):i\in[\gamma-1]\\}$ be blue. Set $t=\frac{(\gamma+1)^{2}}{2}$, and
add an additional red point $r=(-t,\gamma+1)$, and an additional blue point
$b=(2t,\gamma+1)$. See Figure 2.

We show that under the BC rule, two balls are sufficient to correctly label
all points: First take the red ball centered at $r$ with radius
$\sqrt{t^{2}+(\gamma+1)^{2}}=\sqrt{t^{2}+2t}<t+1$. Clearly this ball contains
no blue points, since the line containing the blue points is at distance
exactly $t+1$ from $r$. But the ball contains all the red points, as the
farthest red points from $r$ are at $(0,2)$ and $(0,2\gamma)$, both of which
are at distance $\sqrt{t^{2}+(\gamma-1)^{2}}$ from the ball center, and hence
inside the ball. Now take the blue ball centered at $b$ with radius
$\sqrt{4t^{2}+(\gamma+1)^{2}}=\sqrt{(2t)^{2}+2t}<2t+1$. A similar argument to
that above shows that this ball contains all blue points, but none of the red.

We show that under the NN rule, at least $n-2$ points must be found in the
condensed set. First take the blue points on the line $x=1$, and at least one
of these must be in the condensed set: If only $b$ were in the condensed set,
then the other blue points would be closer to every red point in the condensed
set. Now take a blue point $(1,2i+1)$ in the condensed set, and it must be
that the red points $(0,2i),(0,2i+2))$ are both in the condensed set, since
the blue point is their nearest neighbor. It similarly follows that blue
points $(1,2i-1),(1,2i+3)$ are both in the condensed, and in fact that all red
points on the line $x=0$ and all blue points on the line $x=1$ are in the
condensed set. ∎

###  3.2 Learning bounds

Here we establish uniform generalization bounds for WNN rules. By definition,
a general WNN classifier is uniquely determined by a subset of labeled samples
$\tilde{S}$ and a weight function $w$. In addition, since $w(x)=1$ for all
$x\notin\tilde{S}$, $w$ is uniquely determined by its values on $\tilde{S}$.
The following representation lemma establishes a $2|\tilde{S}|$-sample
compression scheme for the class of WNN rules, which will allow us to derive
compression-based error bounds (Littlestone and Warmuth, 1986; Floyd and
Warmuth, 1995; Graepel et al., 2005).

######  Lemma 3.

There exist an encoding function $\mathcal{C}$ and a reconstruction function
$\mathcal{R}$ that satisfy the following: For any finite labeled set $S$, any
subset $\tilde{S}\subset S$, and any weight assignment $w$ for $\tilde{S}$, if
the WNN classifier corresponding to the pair $(\tilde{S},w)$ is consistent on
$S$, then $\mathcal{C}(S,\tilde{S},w)$ returns two ordered labeled subsets
$\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime}\subset S$, each of size
$|\tilde{S}|$, such that the WNN classifier
$h_{\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime}}=\mathcal{R}(\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime})$
is consistent on $S$.

###### Proof.

We first describe the encoding function $\mathcal{C}$ that given $S$ and the
pair $(\tilde{S},w)$, selects
$\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime}$. Then we will describe the
reconstruction function $\mathcal{R}$ and conclude that
$\mathcal{R}(\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime})$ is indeed
consistent on $S$.

Given $S$ and $(\tilde{S},w)$, the encoding function $\mathcal{C}$ returns two
ordered lists $\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime}\subset S$ such
that $\tilde{S}^{\prime}$ has the same sample points in $\tilde{S}$ but in a
specific order, and $\tilde{\mathcal{W}}^{\prime}$ consists of sample points
from $S$ from which appropriate weights for $\tilde{S}^{\prime}$ can be
deduced via $\mathcal{R}$. The first sample in the list $\tilde{S}^{\prime}$
corresponds to $x\in\tilde{S}$ having the maximal weight, and the first sample
in $\tilde{\mathcal{W}}^{\prime}$ is also taken as $x$. Subsequent points are
added to $\tilde{S}^{\prime}$ and $\tilde{\mathcal{W}}^{\prime}$ by the
following procedure: Starting with initial weights as determined by $w$,
multiplicatively increase the weights of all points of $\tilde{S}$ not yet
placed in $\tilde{S}^{\prime}$, until one of the following occurs:

  * (i)

A point $x\in\tilde{S}\setminus\tilde{S}^{\prime}$ has weight equal to that of
a point already in $\tilde{S}^{\prime}$, say $x_{1}$. Then $x$ is added to
$\tilde{S}^{\prime}$ and $x_{1}$ is added to $\tilde{\mathcal{W}}^{\prime}$.

  * (ii)

There is some point $x\in S\setminus\tilde{S}$ that became equidistant (under
weighted distance) from its closest point $x_{1}\in\tilde{S}$ of the same
label, and its closest point $x_{2}\in\tilde{S}$ with opposite label. It must
be that $x_{1}$ is already in $\tilde{S^{\prime}}$, or else the weights of
$x_{1},x_{2}$ would increase in unison. Then $x_{2}$ is added to
$\tilde{S}^{\prime}$ and $x$ is added to $\tilde{\mathcal{W}}^{\prime}$.

The weight increase procedure is carried on until all samples of $\tilde{S}$
have been placed in $\tilde{S}^{\prime}$.

As for the reconstruction, given two lists of sample point-label pairs
$\tilde{S}^{\prime}=((x_{1},y_{1}),\dots,(x_{m},y_{m}))$ and
$\tilde{\mathcal{W}}^{\prime}=((x^{\prime}_{1},y^{\prime}_{1}),\dots,(x^{\prime}_{m},y^{\prime}_{m}))$
that have been computed by $\mathcal{C}$ as described above, the
reconstruction function $\mathcal{R}$ construct a WNN classifier corresponding
to the pair $(\tilde{S}^{\prime},w^{\prime})$, where the weight assignment
$w^{\prime}$ is computed as follows. The weight of the first point in
$\tilde{S}^{\prime}$ is set to $w^{\prime}(x_{1})=1$. The weights of
subsequent points in $\tilde{S}^{\prime}$ are set depending on their
corresponding points in $\tilde{\mathcal{W}}^{\prime}$: For $k>1$,

  * •

If $x_{k}$ appears in $(x_{1},\dots,x_{k-1})$, say as $x_{j}$, then we are in
case (i), and thus put $w^{\prime}(x_{k})=w^{\prime}(x_{j})$.

  * •

If $x_{k}$ does not appear in $(x_{1},\dots,x_{k-1})$, then we are in case
(ii), and $(x^{\prime}_{k},y^{\prime}_{k})$ corresponds to a witness for
$(x_{k},y_{k})$ and some other point in $(x_{1},\dots,x_{k-1})$, say
$(x_{j},y_{j})$. The identity of $x_{j}$ can be inferred by finding the point
in $(x_{1},\dots,x_{k-1})$ with label opposite to $y_{k}$ and having the
minimal weighted distance to $x^{\prime}_{k}$,

$\displaystyle
x_{j}=\operatorname*{arg\,min}_{x_{i}\in\\{x_{1},\dots,x_{k-1}\\}:y_{i}\neq
y_{k}}\left\\{\frac{d(x^{\prime}_{k},x_{i})}{w^{\prime}(x_{i})}\right\\},$

breaking ties towards $x_{i}$ with smallest index $i$. Then
$w^{\prime}(x_{k})$ is set to satisfy the equation

$\displaystyle\frac{d(x^{\prime}_{k},x_{k})}{w^{\prime}(x_{k})}=\frac{d(x^{\prime}_{k},x_{j})}{w^{\prime}(x_{j})}.$

Since multiplying the weights of several points in unison do not change their
pairwise weighted-distance boundaries, it is clear that during the whole
construction process done in $\mathcal{C}$, the classifier remains consistent
on $S$, provided ties in weighted distances are decided in favor of points in
$\tilde{S}^{\prime}$ of smaller index. Hence
$\mathcal{R}(\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime})$ is consistent
on $S$. ∎

Lemma 3 can be used to derive generalization bounds, as we show in Theorem 4.
But note first that the reconstruction function $\mathcal{R}$ of Lemma 3
heavily relies on that $\tilde{S}^{\prime}$ and $\tilde{\mathcal{W}}^{\prime}$
are ordered. Below in Section 4 we will consider a subclass of WNNs whose
$\mathcal{R}$ assumes no such matching is given, and this matching needs to be
deduced. In this case a tighter generalization bound holds, which we will
leverage to establish Bayes consistency for the aforementioned subclass in
Section 4.2. Formally, a reconstruction function $\mathcal{R}$ is said to be
_permutation invariant_ if for any two arbitrary permutations
$\sigma_{1},\sigma_{2}$ of the samples in $\tilde{S}^{\prime}$ and
$\tilde{\mathcal{W}}^{\prime}$ respectively,

$\displaystyle\mathcal{R}(\sigma_{1}(\tilde{S}^{\prime}),\sigma_{2}(\tilde{\mathcal{W}}^{\prime}))=\mathcal{R}(\tilde{S}^{\prime},\tilde{\mathcal{W}}^{\prime}).$
(1)

In other words, a permutation invariant $\mathcal{R}$ is able to deduce the
matching between the samples in $\tilde{S}^{\prime}$ and their weights from
the unordered elements of $\tilde{S}^{\prime}$ and
$\tilde{\mathcal{W}}^{\prime}$ alone.

We can now present the generalization bounds. These essentially correspond to
sample compression-based error bounds for the compression scheme established
in Lemma 3. Similar finite-sample bounds (up to constants) for standard NN
rules have been established in Gottlieb et al. (2014); Kontorovich et al.
(2017); Hanneke et al. (2021); in particular, leveraging the fact that such
bounds are dimension free, Hanneke et al. (2021) derived similar bounds to
establish universal Bayes consistency of a nearest neighbor rule (OptiNet) in
any essentially-separable metric space.

######  Theorem 4.

For any probability distribution of $x$, any labeling function
$l:\mathcal{X}\to\\{-1,1\\}$, and any $n\in\mathbb{N}$ and $0<\delta<1$, it
holds that with probability $1-\delta$ over the i.i.d. labeled sample
$S=\left\\{(x_{1},l(x_{1})),\dots,(x_{n},l(x_{n}))\right\\}$, for any
$\tilde{S}\subset S$ and weight assignment $w$ for $\tilde{S}$, if the WNN
classifier $h_{(\tilde{S},w)}$ corresponding to the pair $(\tilde{S},w)$
correctly classifies all points in $S$, then

$\displaystyle\textup{err}(h_{(\tilde{S},w)})\leq\frac{2}{n-|\tilde{S}|}\left(|\tilde{S}|\log
2n+\log\frac{n}{\delta}\right).$ (2)

If in addition the reconstruction function $\mathcal{R}$ is permutation
invariant, then

$\displaystyle\textup{err}(h_{(\tilde{S},w)})\leq\frac{2}{n-|\tilde{S}|}\left(|\tilde{S}|\log{\left(\frac{2en}{|\tilde{S}|}\right)}+\log\frac{n}{\delta}\right).$
(3)

###### Proof of Theorem 4..

Consider first the case of non-invariant $\mathcal{R}$. Set $m=|\tilde{S}|$
and let $\mathcal{I}_{n,m}$ denote the set of all (ordered) sequences of
length $m$ of indices from $\\{1,2,\dots,n\\}$. For
$\bm{i}=(i_{1},\dots,i_{m})\in\mathcal{I}_{n,m}$ denote by $S(\bm{i})$ the
subset of $S$ with indices in $\bm{i}$. For a weight assignment
$w^{\prime}(\bm{i})$ for $S(\bm{i})$, write
$\widehat{\textup{err}}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})$ for the empirical
error of $h_{(S(\bm{i}),w^{\prime}(\bm{i}))}$ over the $n-m$ samples in
$S\setminus S(\bm{i})$, that is

$\displaystyle\frac{1}{n-m}\sum_{(x_{j},y_{j})\in S\setminus
S(\bm{i})}\mathbbm{1}_{\\{h_{(S(\bm{i}),w^{\prime}(\bm{i}))}(x_{j})\neq
y_{j}\\}},$

and note that the samples in $S\setminus S(\bm{i})$ are i.i.d. and independent
of $S(\bm{i})$. For $\varepsilon>0$, we bound

$\displaystyle\mathbb{P}\Big{\\{}\widehat{\textup{err}}(h_{(\tilde{S},w)})=0\,\,\wedge\,\,|\tilde{S}|=m\,\,\wedge\,\,\textup{err}(h_{(\tilde{S},w)})>\varepsilon\Big{\\}}$
$\displaystyle\leq\,\,$
$\displaystyle\mathbb{P}\Big{\\{}\exists\bm{i}\in\mathcal{I}_{n,m},\exists
w^{\prime}(\bm{i}):\widehat{\textup{err}}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})=0\,\,\wedge\,\,\textup{err}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})>\varepsilon\Big{\\}}$
$\displaystyle\leq\,\,$
$\displaystyle\sum_{\bm{i}\in\mathcal{I}_{n,m}}\mathbb{E}\Big{\\{}\mathbb{P}\big{\\{}\exists
w^{\prime}(\bm{i}):\widehat{\textup{err}}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})=0\,\,\wedge\,\,\textup{err}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})>\varepsilon\mid
S(\bm{i})\big{\\}}\Big{\\}}.$ (4)

Fix $\bm{i}\in\mathcal{I}_{n,m}$ and $S(\bm{i})$, and consider the class of
WNN classifiers given by

$\displaystyle\mathcal{H}_{S(\bm{i})}=\\{h_{(S(\bm{i}),w^{\prime}(\bm{i}))}:\text{$w^{\prime}(\bm{i})$
weight assign.\ for $S(\bm{i})$}\\}.$

The growth function $\Pi_{\mathcal{H}_{S(\bm{i})}}(n)$ of
$\mathcal{H}_{S(\bm{i})}$ counts the maximum number of different possible
labelings of $n$ points from $\mathcal{X}$:

$\displaystyle\Pi_{\mathcal{H}_{S(\bm{i})}}(n)=\max_{\\{z_{1},\dots,z_{n}\\}\subset\mathcal{X}}\Big{|}\big{\\{}(h(z_{1}),\dots,h(z_{n})):h\in\mathcal{H}_{S(\bm{i})}\big{\\}}\Big{|}.$

Then by a standard argument (Mohri et al., 2018),

$\displaystyle\mathbb{P}\big{\\{}\exists
w^{\prime}(\bm{i}):\widehat{\textup{err}}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})=0\,\,\wedge\,\,\textup{err}(h_{(S(\bm{i}),w^{\prime}(\bm{i}))})>\varepsilon\mid
S(\bm{i})\big{\\}}$ $\displaystyle\leq
2\Pi_{\mathcal{H}_{S(\bm{i})}}(2(n-m))\cdot e^{-(n-m)\varepsilon/2}.$

To bound $\Pi_{\mathcal{H}_{S(\bm{i})}}(2(n-m))$, note that by Lemma 3, for
any weight assignment $w^{\prime}(\bm{i})$ for $S(\bm{i})$ and any set
$S^{\prime}$ of $2(n-m)$ points from $\mathcal{X}$, there exists a subset
$\tilde{\mathcal{W}}^{\prime}\subset S^{\prime}\cup\tilde{S}(\bm{i})$ of size
$m$ such that the WNN classifier $h_{S(\bm{i}),\tilde{\mathcal{W}}^{\prime}}$
gives the same labeling as $h_{(S(\bm{i}),w^{\prime}(\bm{i}))}$ on the
$2(n-m)$ points in $S^{\prime}$. Since the number of different classifiers in

$\displaystyle\Big{\\{}h_{S(\bm{i}),\tilde{\mathcal{W}}^{\prime}}:\text{$\tilde{\mathcal{W}}^{\prime}$
is a list of $m$ points}\text{from a sample of size $2n-m$}\Big{\\}}$

is at most $|\mathcal{I}_{2n-m,m}|\leq|\mathcal{I}_{2n,m}|$, it follows that

$\displaystyle\Pi_{\mathcal{H}_{S(\bm{i})}}(2(n-m))\leq|\mathcal{I}_{2n,m}|.$

Hence, Eq. (4) is bounded from above by

$\displaystyle\sum_{\bm{i}\in\mathcal{I}_{n,m}}|\mathcal{I}_{2n,m}|e^{-(n-m)\varepsilon/2}\leq|\mathcal{I}_{n,m}||\mathcal{I}_{2n,m}|e^{-(n-m)\varepsilon/2}.$
(5)

Put

$\displaystyle\varepsilon$
$\displaystyle=\frac{2}{n-m}\left(\log{(|\mathcal{I}_{n,m}|\cdot|\mathcal{I}_{2n,m}|)}+\log\frac{n}{\delta}\right)\leq\frac{2}{n-m}\left(m\log{2n}+\log\frac{n}{\delta}\right),$
(6)

where we used the bound $|\mathcal{I}_{n,m}|\leq n^{m}$. Then the right hand
side of (5) is $\delta/n$. Summing over the $n$ possible values of $m$
completes the proof for the case of non-invariant $\mathcal{R}$.

As for the case of permutation invariant $\mathcal{R}$, the only difference
from the proof above is the definition of $\mathcal{I}_{n,m}$. For the
permutation invariant case we take $\mathcal{I}_{n,m}$ to be the set of all
(unordered) subsets of $\\{1,2,\dots,n\\}$ of size $m$. Then
$|\mathcal{I}_{n,m}|\leq{n\choose m}\leq(\frac{en}{m})^{m}$. Putting this into
Eq. (6), we have

$\displaystyle\varepsilon$
$\displaystyle\leq\frac{2}{n-m}\left(m\log{\frac{2en}{m}}+\log\frac{n}{\delta}\right),$

in accordance with (3). ∎

##  4 Greedy heuristic for WNN, and its properties

In this section, we suggest a heuristic to produce a weighted condensed set.
The heuristic is motivated by the ball cover rule introduced above. After
presenting the heuristic, we establish that it is Bayes consistent under mild
assumptions.

###  4.1 Heuristic

Our heuristic for WNN condensing is based on a greedy approach for the BC
rule, meaning that at each step, we identify a ball covering the maximum
number of uncovered points of the same label (and no points of the opposite
label), and add it to our ball set. Similarly, in our WNN heuristic (see
Algorithm 1), we iteratively add to the condensed set a point and weight which
correspond to the center and radius of the ball covering the largest number of
as of yet not covered points. (The equivalence of the radius in the BC rule to
weight in the WNN rule was already established above in Section 3.1.) As in
Flores-Velazco and Mount (2021), the notation $d_{\operatorname{ne}}(x)$
denotes the distance from $x$ to its closest oppositely labeled point in $S$
(its ‘nearest enemy’).

Algorithm 1 Greedy weighted heuristic

Input: Point set $S$

Initialize solution set $T\leftarrow\emptyset$, $S^{\prime}\leftarrow S$,
weight function $w:S\rightarrow\\{1\\}$

while $S^{\prime}\neq\emptyset$ do

$x\leftarrow\operatorname{\textup{argmax}}_{x\in
S}|B(x,d_{\operatorname{ne}}(x))\cap S^{\prime}|$

$S^{\prime}\leftarrow S^{\prime}\setminus B(x,d_{\operatorname{ne}}(x))$

$T\leftarrow T\cup\\{x\\}$

$w(x)\leftarrow d_{\operatorname{ne}}(x)$

end while

return $T,w$.

###  4.2 Bayes Consistency

In the following, we consider a family of WNN classifiers that use a specific
(data-dependent) weight function $w_{\operatorname{ne}}$, that assigns to each
data point $(\tilde{x},\tilde{y})\in\tilde{S}\subset S$ weight equal to the
minimal distance from $\tilde{x}$ to the points in $S$ that have the opposite
label from $\tilde{y}$, and for points $x\notin\tilde{S}$ assigns
$w_{\operatorname{ne}}(x)=1$; that is, defining $S^{+}$ and $S^{-}=S\setminus
S^{+}$ as the split of $S$ into positively and negatively labeled points
respectively,
$w_{\operatorname{ne}}(\tilde{x})=d_{\operatorname{ne}}(\tilde{x}),$ where

$\displaystyle
d_{\operatorname{ne}}(\tilde{x})=\begin{cases}d(\tilde{x},S^{-}),&\qquad\tilde{x}\in\tilde{S}^{+},\\\
d(\tilde{x},S^{+}),&\qquad\tilde{x}\in\tilde{S}^{-}.\end{cases}$

Note that for this subclass of WNN classifiers there is a simpler compression
scheme than that of Lemma 3; in particular, the reconstruction function
$\mathcal{R}$ can be made permutation invariant in the sense of (1). Indeed,
the weight assignment $w_{\operatorname{ne}}$ for $\tilde{S}$ can be encoded
into a subset $\tilde{\mathcal{W}}\subset S\setminus\tilde{S}$ consisting of
the nearest enemies of the samples in $\tilde{S}$. Then the weight for
$(\tilde{x},\tilde{y})\in\tilde{S}$ can be uniquely determined by splitting
$\tilde{\mathcal{W}}$ into its positively and negatively labeled samples
$\tilde{\mathcal{W}}^{+}$ and $\tilde{\mathcal{W}}^{-}$ and putting
$w_{\operatorname{ne}}(\tilde{x})=\min_{(x,y)\in\tilde{\mathcal{W}}^{-\tilde{y}}}d(\tilde{x},x).$
With this rule, for any two permutations $\sigma_{1},\sigma_{2}$,
$\mathcal{R}(\sigma_{1}(\tilde{S}),\sigma_{2}(\tilde{\mathcal{W}}))=\mathcal{R}(\tilde{S},\tilde{\mathcal{W}})$.

We first consider the (computationally intractable) learning rule that finds
the subset $\tilde{S}^{*}\subset S$ of minimal cardinality such that the
classifier $h_{(\tilde{S}^{*},w_{\operatorname{ne}})}$ is consistent on $S$,

$\displaystyle\tilde{S}^{*}=\operatorname*{arg\,min}_{\tilde{S}\subset
S}\\{|\tilde{S}|:h_{(\tilde{S},w_{\operatorname{ne}})}(x)=y,\forall(x,y)\in
S\\}.$ (7)

The following theorem establishes the Bayes consistency of
$h_{(\tilde{S}^{*},w_{\operatorname{ne}})}$.

######  Theorem 5.

Let $(\mathcal{X},d)$ be a separable metric space and assume $x$ has an
atomless distribution and that the labeling function $l$ is countably piece-
wise continuous. Then, almost surely,

$\displaystyle\textup{err}(h_{(\tilde{S}^{*},w_{\operatorname{ne}})})\xrightarrow[n\to\infty]{}0.$
(8)

The proof below essentially establishes that $|\tilde{S}^{*}|$ is almost
surely sub-linear in the sample size $n$. An application of the error bound
(3) of Theorem 4 (corresponding to a permutation-invariant rule) then
establishes (8). Note that a sub-linear $|\tilde{S}^{*}|$ in conjunction with
the error bound (2) (corresponding to a non-permutation invariant rule) do not
suffice to establish Bayes consistency with our proof technique: Without
further assumptions on the tail of the distribution of $x$, the rate at which
$|\tilde{S}^{*}|/n\xrightarrow[n\to\infty]{}0$ can be arbitrarily slow.

###### Proof of Theorem 5..

Denote by $\mu$ the probability distribution of $x$ and abbreviate
$h_{\tilde{S}^{*}}=h_{(\tilde{S}^{*},w_{\operatorname{ne}})}$. For $r>0$ let

$\displaystyle
U_{r}=\left\\{x\in\textup{supp}(\mu):\frac{1}{\mu(B_{r}(x))}\int_{B_{r}(x)}l(x^{\prime})\mu(dx^{\prime})=l(x)\right\\};$

that is, $U_{r}$ is the set of all points in the support of $\mu$ where $l$ is
essentially constant in the ball of radius $r$ around $x$. The assumptions
that $x$ is atomless and that $l$ is piece-wise continuous imply that
$\mu(U_{r})$ is monotonic decreasing and continuous in $r$ and satisfies

$\displaystyle\lim_{r\to 0}\mu(U_{r})=1.$ (9)

Given $\varepsilon>0$, let $r^{*}=r^{*}(\varepsilon)>0$ be such that

$\displaystyle\mu(U_{r^{*}})\geq 1-\alpha,$

where $\alpha=\alpha(\varepsilon)\in(0,1/8)$ satisfies

$\displaystyle\frac{8\alpha\log\left(\frac{e}{2\alpha}\right)}{1-4\alpha}\leq\frac{\varepsilon}{2}.$
(10)

Since the left hand side of (10) goes to 0 monotonically (and continuously) as
$\alpha\to 0$, such an $\alpha$ always exists (this choice of $\alpha$ will be
made clear below).

Given a sample $S$ of size $n$, denote by $\bm{X}_{n}=(x_{1},\dots,x_{n})$ the
instances in $S$ and by $\bm{Y}_{n}=(y_{1},\dots,y_{n})$ their corresponding
labels. Let $\bm{X}_{r^{*}}\subseteq\bm{X}_{n}\cap U_{r^{*}}$ be an
$r^{*}$-net of $\bm{X}_{n}\cap U_{r^{*}}$ (an $r$-net of a set is defined in
Appendix 5) and let $\bm{Y}_{r^{*}}$ be the corresponding labels in
$\bm{Y}_{n}$, stacked into the labeled set
$\tilde{S}_{(1)}=(\bm{X}_{r^{*}},\bm{Y}_{r^{*}})$. Let
$U_{r^{*}}^{c}=\mathcal{X}\setminus U_{r^{*}}$ denote the set complement of
$U_{r^{*}}$ and let $\tilde{S}_{(2)}=S\cap(U_{r^{*}}^{c}\times\mathcal{Y})$.
Define the labeled dataset

$\displaystyle\tilde{S}_{r^{*}}=\tilde{S}_{(1)}\cup\tilde{S}_{(2)}\subset S.$

Then $h_{\tilde{S}_{r^{*}}}$ is consistent on $S$. Indeed, any
$(x_{i},y_{i})\in S\cap(U_{r^{*}}^{c}\times\mathcal{Y})$ is included in
$\tilde{S}_{r^{*}}$ and is thus classified correctly by
$h_{\tilde{S}_{r^{*}}}$. For any $(x_{i},y_{i})\in
S\cap(U_{r^{*}}\times\mathcal{Y})$, since $\bm{X}_{r^{*}}$ is an $r^{*}$-net
of $\bm{X}_{n}\cap U_{r^{*}}$, there is $\tilde{x}\in\bm{X}_{r^{*}}$ with

$\displaystyle d(x_{i},\tilde{x})<r^{*}.$

Since $\tilde{x}\in U_{r^{*}}$ and $d(x_{i},\tilde{x})<r^{*}$, we have
$y_{i}=l(x_{i})=l(\tilde{x})=\tilde{y}$ with probability 1. In addition, any
point $(x_{j},y_{j})\in S$ with an opposite label to $\tilde{y}$ satisfies
$d(x_{j},\tilde{x})\geq r^{*}$, and so $w_{\operatorname{ne}}(\tilde{x})\geq
r^{*}$. Thus,

$\displaystyle\tilde{d}(x_{i},\tilde{x})=\frac{d(x_{i},\tilde{x})}{w_{\operatorname{ne}}(\tilde{x})}<1.$

Additionally, any $\tilde{x}^{\prime}\in\tilde{S}_{r^{*}}$ with a different
label from $y_{i}$ has weight

$\displaystyle w_{\operatorname{ne}}(\tilde{x}^{\prime})\leq
d(x_{i},\tilde{x}^{\prime}).$

Thus,

$\displaystyle\tilde{d}(x_{i},\tilde{x}^{\prime})=\frac{d(x_{i},\tilde{x}^{\prime})}{w_{\operatorname{ne}}(\tilde{x})}\geq
1.$

So the WNN classifier $h_{\tilde{S}_{r^{*}}}$ classifies the point
$(x_{i},y_{i})$ correctly in this case as well, and so $h_{\tilde{S}_{r^{*}}}$
is consistent on $S$. It follows that the subset $\tilde{S}^{*}$ in (7)
computed by the learning rule satisfies

$\displaystyle|\tilde{S}^{*}|\leq|\tilde{S}_{r^{*}}|.$ (11)

We next bound $|\tilde{S}_{r^{*}}|=|\tilde{S}_{(1)}|+|\tilde{S}_{(2)}|$ with
high probability. Since by construction $\mu(U_{r^{*}}^{c})\leq\alpha$,
Hoeffding’s inequality implies that

$\displaystyle\mathbb{P}\left\\{|\tilde{S}_{(2)}|>2n\alpha\right\\}=\mathbb{P}\left\\{|\bm{X}_{n}\cap
U_{r^{*}}^{c}|>2n\alpha\right\\}\leq e^{-2n\alpha^{2}}.$

As for $|S_{(1)}|$, by Hanneke et al. (2021, Lemma 3.7), there is
$t_{r^{*}}:\mathbb{N}\to\mathbb{R}^{+}$ in $o(1)$ such that

$\displaystyle\mathbb{P}\left\\{|\bm{X}_{r^{*}}|\geq
nt_{r^{*}}(n)\right\\}\leq 1/n^{2}.$

Since $t_{r^{*}}\in o(1)$, we may take $n$ sufficiently large so that
$t_{r^{*}}(n)\leq 2\alpha$. So for all sufficiently large $n$,

$\displaystyle\mathbb{P}\\{|\tilde{S}_{r^{*}}|>4\alpha
n\\}\leq\frac{1}{n^{2}}+e^{-2n\alpha^{2}}.$

We bound

$\displaystyle\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\varepsilon\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\varepsilon\,\,\wedge\,\,|\tilde{S}_{r^{*}}|\leq
4\alpha n\right\\}+\mathbb{P}\left\\{|\tilde{S}_{r^{*}}|>4\alpha n\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\varepsilon\,\,\wedge\,\,|\tilde{S}_{r^{*}}|\leq
4\alpha n\right\\}+\frac{1}{n^{2}}+e^{-2n\alpha^{2}}.$ (12)

To complete the proof we show below that for all sufficiently large $n$,

$\displaystyle\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\varepsilon\,\,\wedge\,\,|\tilde{S}_{r^{*}}|\leq
4\alpha n\right\\}\leq\frac{1}{n^{2}}.$ (13)

Since the right hand side of (12) is summable over $n$, the Borel-Cantelli
Lemma implies that almost surely,

$\displaystyle\textup{err}(h_{\tilde{S}^{*}})\xrightarrow[n\to\infty]{}0,$

concluding the proof of the Theorem.

To show (13), put $\delta=\delta_{n}=1/n^{2}$ in (3) and observe that the
right hand side of (3) is monotonic increasing with $|\tilde{S}|$. Thus, using
(11), we have that under the event $\\{|\tilde{S}_{r^{*}}|\leq 4\alpha n\\}$,

$\displaystyle\frac{2}{n-|\tilde{S}^{*}|}\left(|\tilde{S}^{*}|\log{\left(\frac{2en}{|\tilde{S}^{*}|}\right)}+3\log
n\right)$
$\displaystyle\leq\frac{2}{n-|\tilde{S}_{r^{*}}|}\left(|\tilde{S}_{r^{*}}|\log{\left(\frac{2en}{|\tilde{S}_{r^{*}}|}\right)}+3\log
n\right)$ $\displaystyle\leq\frac{2}{n-4\alpha n}\left(4\alpha
n\log{\left(\frac{en}{2\alpha n}\right)}+3\log n\right)$
$\displaystyle=\frac{8\alpha\log{\left(\frac{e}{2\alpha}\right)}}{1-4\alpha}+\frac{3\log
n}{(1-4\alpha)n}$
$\displaystyle\leq\frac{\varepsilon}{2}+\frac{\varepsilon}{2}=\varepsilon,$

where in the last inequality we used the choice of $\alpha$ in (10) and took
$n$ sufficiently large so that $\frac{3\log
n}{(1-4\alpha)n}\leq\frac{\varepsilon}{2}$. Applying Lemma 4, it follows that

$\displaystyle\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\varepsilon\,\,\wedge\,\,|\tilde{S}_{r^{*}}|\leq
4\alpha n\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{\textup{err}(h_{\tilde{S}^{*}})>\frac{2}{n-|\tilde{S}^{*}|}\left(|\tilde{S}^{*}|\log{\left(\frac{2en}{|\tilde{S}^{*}|}\right)}+3\log
n\right)\right\\}\leq\frac{1}{n^{2}},$

establishing (13). ∎

As for our greedy heuristic in Algorithm 1, note that the intractable
optimization problem (7) can be cast as a set cover problem. Algorithm 1 then
corresponds to the standard greedy approximation for set cover (Chvatal,
1979). This approximation is guaranteed to compute $\tilde{S}$ of size at most
$O(|\tilde{S}^{*}|\log|\tilde{S}^{*}|)$. Hence, if
$|\tilde{S}^{*}|\log|\tilde{S}^{*}|$ is guaranteed to be almost surely sub-
linear, an adaptation of our proof of Theorem 5 implies that the greedy
heuristic is Bayes consistent. This is made formal in the following Corollary.

######  Corollary 6.

Under the conditions of Theorem 5 and an additional appropriate tail condition
on the probability distribution of $x$, the greedy weighted heuristic of
Algorithm 1 is Bayes consistent.

###### Proof of Corollary 6.

In the proof of Theorem 5 we fetched a function
$t_{r^{*}}:\mathbb{N}\to\mathbb{R}^{+}$ in $o(1)$ to establish that the size
of a $r^{*}$-net (with $r^{*}>0$) is sub-linear in $n$. Inspecting the proof
of Theorem 5, to guarantee that $|\tilde{S}^{*}|\log|\tilde{S}^{*}|$ is almost
surely sub-linear in $n$, it suffices to additionally assume that
$t_{r^{*}}\in o(1/\log n)$. ∎

As two examples of the applicability of Corollary 6, if random variable $x$ is
bounded then $|\tilde{S}^{*}|=O(1)$, and if $x$ has a normal distribution then
$|\tilde{S}^{*}|=O(\log n)$. Hence in these examples Algorithm 1 is Bayes
consistent.

##  5 Search algorithm

In previous sections, we motivated the WNN rule, and gave a heuristic for
producing a condensed set and weights. In this section, we consider the
algorithmic problem of, given a weighted condensed set $\tilde{S}$ and weight
function $w$, labeling a new point $q$ (the _query_) via the WNN rule on
$\tilde{S},w$. This is the same as finding the weighted distance nearest
neighbor of $q$ in $\tilde{S}$

We note that if the number of distinct weights in $w$ is at most $k$, then we
can reduce the above problem to solving $k$ separate (unweighted) nearest
neighbor problems: Group the points of $\tilde{S}$ by into at most $k$ groups,
each containing only points of the same weight. For each group, preprocess an
unweighted nearest neighbor search structure. Given the query $q$, find the
nearest unweighted neighbor of $q$ within each group. One of these $k$ points
must be the weighted distance nearest neighbor.

We will give an approximate search algorithm with run-time independent of the
number of distinct weights. This algorithm is a modification of the navigating
net algorithm for doubling spaces Krauthgamer and Lee (2004), and we first
describe this structure.

#### Navigating nets.

For a metric $(\mathcal{X},d)$, let $\lambda$ be the smallest value such that
every ball in $\mathcal{X}$ of radius $r$ (for any $r$) can be covered by
$\lambda$ balls with radius $\frac{r}{2}$. $\lambda$ is the _doubling
constant_ of $\mathcal{X}$, and $\log_{2}\lambda$ is the _doubling dimension_
of $\mathcal{X}$ ($\operatorname{ddim}:=\operatorname{ddim}(\mathcal{X})$).
Doubling spaces also obey a _packing property_ : The number of points at
minimum inter-point distance at least $b$ within a ball of radius $r$ is at
most $(r/b)^{O(\operatorname{ddim})}$.

An $r$-_net_ of $\mathcal{X}$ is a subset $S\subset\mathcal{X}$ satisfying the
following:

  * •

Packing: The minimum inter-point distance in $S$ is greater than $r$.

  * •

Covering: For every $x\in\mathcal{X}$, $d(x,S)\leq r$.

A _navigating net_ is a nested series of $r$-nets, each set a net of the
subsequent one with twice its radius. Assume without loss of generality that
the smallest inter-point distance in $\mathcal{X}$ is exactly 1, and let $t$
be the smallest integer satisfying
$2^{t}\geq\operatorname{diam}(\mathcal{X})$. Then the navigating net is
composed of a series of $r$-nets $\\{S_{2^{t}},S_{2^{t-1}},\ldots,S_{1}\\}$
where for all nets $S_{2^{i+1}}\subset S_{2^{i}}$. This series of $r$-nets is
called a _hierarchy_.

A tree is then defined over the hierarchy: To every point in each level of the
hierarchy we associate a unique vertex, so that each point in $S_{2^{i}}$
corresponds to some $i$-level vertex. To an $i$-level vertex associated with
some point $p\in S_{2^{i}}$ ($i<t$) we assign a _parent_ , a single
$(i+1)$-level node associate with (an arbitrary) point in $S_{2^{i+1}}$ within
distance $2^{i+1}$ of $p$. The navigating net is composed of the hierarchy and
its associated tree, and can be computed in time
$2^{O(\operatorname{ddim})}t$.

#### Our solution.

Given a navigating net, we will need to make a simple modification to it: For
every node $v\in T$, we record heaviest point among all the points associated
with the nodes in the sub-tree rooted at $v$.

A $(1+\epsilon)$-approximate weighted nearest neighbor query (for
$\epsilon<1$) proceeds as follows: Starting from the root at level $t$, the
query descends down the levels of the tree. At each level $i$, we compute a
list of all nodes whose associated points are within (unweighted) distance
$\frac{2\cdot 2^{i}}{\epsilon}$ of query point $q$ (and by the packing
property of doubling spaces, there are $\epsilon^{-O(\operatorname{ddim})}$
such nodes). This can be done easily, as by the triangle inequality, an
$i$-level nodes within this distance of $q$ has its $(i+1)$-level parent
within distance

$\frac{2\cdot
2^{i}}{\epsilon}+2^{i+1}=\frac{2^{i+1}}{\epsilon}+2^{i+1}<\frac{2\cdot
2^{i+1}}{\epsilon},$

and so this parent was found in the previously computed list for level $i+1$.
So the node list for level $i$ can be computed by inspecting all children of
the nodes in the list for level $i+1$, and retaining only those nodes whose
associated points are sufficiently close to query $q$. For each node in every
list, the algorithm queries the weighted distance of the associated point to
$q$. The point with the smallest weighted distance is returned. See Algorithm
2, and its run time in Lemma 7.

Algorithm 2 Weighted distance nearest neighbor

Input: Modified navigating net tree $T$, query $q$

Initialize nearest $\leftarrow\emptyset$, $L\leftarrow\\{\text{root of }T\\}$

for each $i=t,\ldots,1$ do

$L^{\prime}\leftarrow\emptyset$

for each $v\in L$ do

for each child $w$ of $v$ do

if $d(q,w)\leq\frac{2\cdot 2^{i}}{\epsilon}$ then

$L^{\prime}\leftarrow L^{\prime}\cup\\{w\\}$

if $\tilde{d}(q,w)<\tilde{d}(q,\text{nearest})$ then

nearest $\leftarrow w$

end if

end if

end for

end for

$L\leftarrow L^{\prime}$

end for

return nearest

######  Lemma 7.

Algorithm 2 returns a $(1+\epsilon)$-approximate weighted distance nearest
neighbor of $q$ in time $\epsilon^{-O(\operatorname{ddim})}t$.

###### Proof.

Let $p^{*}$ be the weighted nearest neighbor of $q$, and let $i$ be the
integer satisfying $d(q,p^{*})<\frac{2^{i}}{\epsilon}\leq 2d(q,p^{*})$. Let
$v$ be the $i$-level tree ancestor of the leaf node associated with $p^{*}$,
and we have by the triangle inequality that $d(q,v)\leq
d(q,p^{*})+d(p^{*},v)<\frac{2^{i}}{\epsilon}+2\cdot 2^{i}<\frac{2\cdot
2^{i}}{\epsilon}$. It follows that $v$ is found in the $i$-level list. If
$p^{*}$ is the heaviest ancestor of $v$, then it will be encountered by the
algorithm and returned. If a different point $p$ is stored in $v$, then
necessarily $w(p)\geq w(p^{*})$. And further, $d(q,p)\leq d(q,v)+d(v,p)\leq
d(q,p^{*})+d(v,p^{*})+d(v,p)\leq d(q,p^{*})+4\cdot
2^{i}\leq(1+8\epsilon)d(q,p^{*})$, so that $p$ is a
$(1+8\epsilon)$-approximate nearest neighbor. ∎

##  6 Experimental results

In this section we present promising experimental results for condensing under
WNN, using the heuristic of Section 4. We ran two separate trials: one on
small data sets, and the other on a large data set. Each of these trials
contribute to understanding and quantifying the quality of our heuristic.

###  6.1 Small dataset trial

The first trial was on relatively small datasets. For these sets, we can use
an integer program (IP) to compute the optimal solution under NN condensing,
which is instructive in understanding the quality of the tested heuristics.

#### Integer programming for NN condensing.

We formalize an integer program for NN condensing. As this problem is NP-hard,
we do not expect the algorithm to have a reasonable run time for large sets,
but for smaller sets it successfully returns an optimal solution (after large
run time).

To model the NN condensing problem as an integer program, we introduced
constraints corresponding to the inclusion of a point in the condensed set.
This allowed us to identify the minimal non-empty subset of examples that can
recover all labels of the sample via the nearest neighbor classifier.

For each sample point $x$, we introduce a 0–1 variable $v(x)$, corresponding
to whether $x$ will appear in the condensed set. For each ordered pair of
points $x$ and $x^{\prime}$ with opposite labels, we introduce the constraint
$v(x^{\prime})\leq\sum_{x^{\prime\prime}\in
C(x,x^{\prime})}v(x^{\prime\prime})$, where $C(x,x^{\prime})$ is the set of
points with the same label as $x$ which are all closer to $x$ than
$x^{\prime}$ is to $x$. (Note that $x\in C(x,x^{\prime})$.) This constraint
enforces that if $x^{\prime}$ appears in the condensed set (meaning
$v(x^{\prime})=1$), then there must be in the condensed set some point closer
to $x$ with the same label as $x$. We also need the constraint
$\sum_{x}v(x)\geq 1$, to disallow the empty set. Finally, the objective is to
minimize $\sum_{x}v(x)$, which corresponds to minimizing the size of the
condensed set. We implented this program using the Python cvxpy library.

#### Datasets.

We ran trials on the banana, circle and iris data sets, see Figure 3.

  * •

Banana. This data set is a synthetic collection, previously used by Flores-
Velazco and Mount (2021) for NNC. It contains instances arranged in several
banana-shaped clusters. (The $x$ and $y$ axes represent the respective
properties At1 and At2 defined there.) For our experiment, we retained only
200 of more than 5000 original points.

  * •

Circle. This is a synthetic randomized data set containing 200 points. It
contains instances arranged in a circular cluster, surrounded by instances of
the opposing class.

  * •

Iris. This is the very popular data set of the UCI Machine Learning
Repository. It consists of three classes, each containing 50 instances of a
certain species of iris. For our experiments, we considered only two classes
of the three (namely Setosa and Versicolour).

Figure 3: The banana, circle and iris data sets

#### Experiments and results.

As proof of concept, we ran on the above datasets multiple algorithms for NN
condensing – namely, the MSS (Barandela et al., 2005) and RSS (Flores-Velazco
and Mount, 2021) heuristics, and the exact IP described above – and also our
greedy heuristic for WNN condensing, as presented above in Algorithm 1.

We found that our weighted condensing heuristic achieved superior compression
when compared to the unweighted heuristics, see Table 1. Interestingly, it was
still slightly worse that the optimal unweighted solution achieved by the IP.

Table 1: Comparison of achieved condensing Dataset | Points | MSS | RSS | IP | WNN
---|---|---|---|---|---
Circle | 200 | 52 | 45 | 7 | 12
Banana | 200 | 74 | 66 | 32 | 35
Iris | 100 | 11 | 9 | 2 | 4

###  6.2 Large dataset trial

We also investigated the performance of the above heuristics on the notMNIST
dataset, published by Yaroslav Bulatov in 2011, and further studied in the
context of NN classification by Balsubramani et al. (2019); Kerem and Weiss
(2023). This dataset consists of approximately $19,000$ different font glyphs
of the letters A-J, that is ten classes. Each image is of dimension $28\times
28$. Since this data set is quite large, the IP utilized above is not
feasible. Yet for large data sets, we are able to sample from the whole set,
and this allows us to report and compare the test error achieved by the
classifiers.

To facilitate the execution of our experiment on a standard computer, we first
applied uniform manifold approximation and projection dimensionality reduction
(UMAP) (McInnes et al., 2018). This served to reduce the dimension from
$28\times 28$ to only $3$. (See Kerem and Weiss (2023) for a visual
demonstration.)

The dataset was split into train ($70\%$) and test ($30\%$) sets. We
considered the heuristics used in the previous section, that is MSS and RSS
for NN condensing, and our greedy heuristic for the WNN rule. As we are also
interested in test error, we compared these results to the case where the
sample is not compressed (we refer to this as 1-NN). Figure 4 (top) shows the
error obtained on the test set, over 10 realizations of the random split. The
compression ratios achieved are shown in Figure 4 (bottom).

These results highlight the following: RSS was the least competitive in error
and compression. While MSS achieved better compression than our greedy WNN,
its test error was worse. In particular, the greedy WNN achieved essentially
the same error as the standard nearest neighbor rule, while compressing the
data-set by approximately $80\%$.

Figure 4: Comparing the test error and compression rates achieved by our
greedy WNN heuristic with other popular condensing heuristics.

##  7 Conclusions

We have demonstrated that WNN condensing is more powerful than standard NN
condensing, yet is characterized by similar generalization bounds. Hence WNN
can only improve the degree of compression, while maintaining the same
theoretical guarantees. Our suggested heuristic is theoretically sound, and
gave promising empirical results. This indicates that WNN condensing
heuristics are deserving of further study.

## References

  * Angiulli (2005) Fabrizio Angiulli.  Fast condensed nearest neighbor rule.  In _Proceedings of the 22nd international conference on Machine learning_ , pages 25–32, 2005.
  * Balsubramani et al. (2019) Akshay Balsubramani, Sanjoy Dasgupta, Shay Moran, et al.  An adaptive nearest neighbor rule for classification.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Barandela et al. (2005) Ricardo Barandela, Francesc J Ferri, and J Salvador Sánchez.  Decision boundary preserving prototype selection for nearest neighbor classification.  _International Journal of Pattern Recognition and Artificial Intelligence_ , 19(06):787–806, 2005.
  * Chvatal (1979) Vasek Chvatal.  A greedy heuristic for the set-covering problem.  _Mathematics of operations research_ , 4(3):233–235, 1979.
  * Cover and Hart (1967) T. Cover and P. Hart.  Nearest neighbor pattern classification.  _IEEE Transactions on Information Theory_ , 13(1):21–27, 1967.  doi: 10.1109/TIT.1967.1053964.
  * Devi and Murty (2002) V Susheela Devi and M Narasimha Murty.  An incremental prototype set building technique.  _Pattern Recognition_ , 35(2):505–513, 2002.
  * Devroye et al. (1996) Luc Devroye, László Györfi, and Gábor Lugosi.  _A probabilistic theory of pattern recognition_.  Springer-Verlag New York, Inc., 1996.
  * Fix and Hodges (1951) E. Fix and J. L. Hodges.  Discriminatory analysis, nonparametric discrimination: Consistency properties.  57(3):238–247, 1951.
  * Flores-Velazco (2020) Alejandro Flores-Velazco.  Social distancing is good for points too!  _arXiv preprint arXiv:2006.15650_ , 2020.
  * Flores-Velazco and Mount (2021) Alejandro Flores-Velazco and David Mount.  Guarantees on nearest-neighbor condensation heuristics.  _Computational Geometry_ , 95:101732, 2021.
  * Floyd and Warmuth (1995) Sally Floyd and Manfred Warmuth.  Sample compression, learnability, and the Vapnik-Chervonenkis dimension.  _Machine learning_ , 21(3):269–304, 1995.
  * Gates (1972) W. Gates.  The reduced nearest neighbor rule.  _IEEE Transactions on Information Theory_ , 18:431–433, 1972.
  * Gottlieb and Kontorovich (2022) Lee-Ad Gottlieb and Aryeh Kontorovich.  Non-uniform packings.  _Information Processing Letters_ , 174:106179, 2022.
  * Gottlieb and Ozeri (2019) Lee-Ad Gottlieb and Shira Ozeri.  Classification in asymmetric spaces via sample compression.  _arXiv preprint arXiv:1909.09969_ , 2019.
  * Gottlieb et al. (2014) Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer.  Efficient classification for metric data (extended abstract COLT 2010).  _IEEE Transactions on Information Theory_ , 60(9):5750–5759, 2014.  doi: 10.1109/TIT.2014.2339840.  URL http://dx.doi.org/10.1109/TIT.2014.2339840.
  * Gottlieb et al. (2018) Lee-Ad Gottlieb, Aryeh Kontorovich, and Pinhas Nisnevitch.  Near-optimal sample compression for nearest neighbors.  _IEEE Transactions on Information Theory_ , 64(6):4120–4128, 2018.
  * Graepel et al. (2005) Thore Graepel, Ralf Herbrich, and John Shawe-Taylor.  PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification.  _Machine Learning_ , 59(1):55–76, 2005.
  * Györfi and Weiss (2021) László Györfi and Roi Weiss.  Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces.  _The Journal of Machine Learning Research_ , 22(1):6702–6726, 2021.
  * Hanneke et al. (2021) Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss.  Universal Bayes consistency in metric spaces.  _The Annals of Statistics_ , 49(4):2129 – 2150, 2021.  doi: 10.1214/20-AOS2029.  URL https://doi.org/10.1214/20-AOS2029.
  * Hart (1968) Peter Hart.  The condensed nearest neighbor rule (corresp.).  _IEEE transactions on information theory_ , 14(3):515–516, 1968.
  * Kerem and Weiss (2023) Omer Kerem and Roi Weiss.  On error and compression rates for prototype rules.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pages 8228–8236, 2023.
  * Kontorovich et al. (2017) Aryeh Kontorovich, Sivan Sabato, and Roi Weiss.  Nearest-neighbor sample compression: Efficiency, consistency, infinite dimensions.  In _Advances in Neural Information Processing Systems_ , pages 1573–1583, 2017.
  * Krauthgamer and Lee (2004) Robert Krauthgamer and James R. Lee.  Navigating nets: Simple algorithms for proximity search.  In _15th Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 791–801, Jan 2004.
  * Littlestone and Warmuth (1986) Nick Littlestone and Manfred K. Warmuth.  Relating data compression and learnability.  unpublished, 1986.
  * McInnes et al. (2018) Leland McInnes, John Healy, and James Melville.  Umap: Uniform manifold approximation and projection for dimension reduction.  _arXiv preprint arXiv:1802.03426_ , 2018.
  * Mohri et al. (2018) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of machine learning_.  MIT press, 2018.
  * Ritter et al. (1975) G. Ritter, H. Woodruff, S. Lowry, and T. Isenhour.  An algorithm for a selective nearest neighbor decision rule (corresp.).  _IEEE Transactions on Information Theory_ , 21(6):665–669, 1975.
  * Shalev-Shwartz and Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, 2014.
  * Wilfong (1991) Gordon Wilfong.  Nearest neighbor problems.  In _Proceedings of the Seventh Annual Symposium on Computational Geometry_ , SCG ’91, pages 224–233, 1991.
  * Wilson and Martinez (2000) D. R. Wilson and T. R. Martinez.  Reduction techniques for instance-based learning algorithms.  _Machine Learning_ , 38:257–286, 2000.
  * Xue and Kpotufe (2018) Lirong Xue and Samory Kpotufe.  Achieving the time of 1-nn, but the accuracy of k-nn.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1628–1636. PMLR, 2018.
  * Zukhba (2010) A. V. Zukhba.  Np-completeness of the problem of prototype selection in the nearest neighbor method.  _Pattern Recognit. Image Anal._ , 20(4):484–494, December 2010.  ISSN 1054-6618.