# Attemps for Constant Approximation Algorithms of KDE

$$
\newcommand{\fkp}{\hat{f}_{K, P}}
\newcommand{\fkpi}{\hat{f}_{K, \Pi P}}
\newcommand{\sumpp}{\sum\limits_{p\in P}}
\newcommand{\sumppp}{\sum\limits_{p\in P'}}
\newcommand{\sumxk}{\sum\limits_{x\in K}}
\newcommand{\kxp}{k(\|x^* - p\|^2)}
\newcommand{\gxp}{g(\|x^* - p\|^2)}
\newcommand{\epstwo}{\frac{\epsilon}{2}}
\newcommand{\epsfour}{\frac{\epsilon}{4}}
\newcommand{\epssix}{\frac{\epsilon}{6}}
\newcommand{\xp}{\|x^* - p\|^2}
\newcommand{\maxxd}{\max_{x \in \mathbb{R}^d}}
\newcommand{\maxxm}{\max_{x \in \mathbb{R}^m}}
\newcommand{\norm}[1]{\|#1\|}
\newcommand{\R}{\mathbb{R}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\oc}{\overline{c}}
$$
$$
\newcommand{\gammaone}{\epstwo\cdot\frac{\sumpp \kxp}{\sumpp \gxp \cdot \xp}}
\newcommand{\sumppcondition}[1]{\sum\limits_{p\in P, \norm{x^* -p}^2 \le #1}}
\newcommand{\sumppconditionp}[1]{\sum\limits_{p\in P, \norm{x^* -p}^2 > #1}}
$$
$$
\newcommand{\gammatwo}{\epsfour\cdot\frac{\sumppcondition{\xi} \kxp}{\sumppcondition{\xi} \gxp \cdot \xp}}
\DeclareMathOperator*{\argmax}{arg\,max}
$$

## Description of Algorithm
We already know the SkEB problem can be reduced into the problem: with a ball of radius $r$ we can output the maximum points and the center of the ball. And the SkEB problem can be solved 2-approximation of the smallest ball radius.

We first assume the SkEB problem can be extactly solved then, we tried the calculate with the algorithm1 described in the SkEB paper will work or not.

This algorithm based on the tuition: we can use a cluster of a points to represent the most mass of the KDE estimation, then we try to find this cluster by checking all the possible radius integer. Details are described as following:

- Set the ball $\B$ radius to $(0, \sqrt{\log n}]$, set each interval to $1$. Then, do the dual problem on the SkEB paper. (Return the location of that ball with the maximum points in it.)
- Find the maximum KDE estimation value of those balls, set the center of the Ball as the approximate center $x'$.

## Tuitions and Attempts
We think the tuitions logic behind this algorithm is that we assumed there is a core set of points $P' \subseteq P$ such that $P'$ fits in a sphere with radius less than $\sqrt{\log n}$. The center of a smallest ball up to an integer radius is a constant approximation of the value of the GMM with $P'$ as its center, and the sum of the kernel values of the points in $P\setminus P'$ is at most another constant.

Then, we define an auxiliary sphere $\A$ centered at $x^*$ including constant approximate of the sum value. We have
$$
\sum_{p' \in \A \cap P}e^{-\norm{x^* - p'}^2} \ge c\sumpp e^{-\norm{x^* - p}^2}.
$$

Then, $\B$ is based on the maximum value of the estimation. And ball $\B$ also including the most points in this ball. However, we don't know whether it is correct to including the maximum number of the points inside that ball will make it better than some other balls.

The $\B$ can only give us that the best average unweighted density of a ball with radius $r_\B$. However, with Gaussian Kernel, those points are actually weighted by the center $x'$ we choose. Thus, $\B$ is not the best averae density of radius $r_\B$. We are struggling with the rest of the proof.

## Problems
1. We cannot assume all the points are on the boundary of sphere $\B$.
2. We cannot get the relation between $x^*$ and $x'$.
3. $x'$ of $\B$ doesn't reflect the weighted density when we didn't consider the Gaussian kernels.