Approximators

Why

We are given an element of some set, and want to find an element (in some subset) which is most similar to it.

Definition

Consider a non-empty set, one of its subsets, and a similarity function on it. An approximator of an element of the set is any element of the subset. So we call the subset the set of approximators. One approximator may be more similar than another. An optimal approximator is a minimizer of the similarity function over the set of approximators.

Notation

Let $B$ be a non-empty set. Let $A \subset B$. Let $d: B \times B \to \R $ be a similarity function. For $b \in B$, every $a \in A$ is an approximator of $b$. An optimal $b$ is a solution of

\[ \begin{aligned} \text{ minimize } & \quad d(b, a) \\ \text{ subject to } & \quad a \in A. \end{aligned} \]

$\varepsilon $ approximations

Let $a, b \in B$. For $\varepsilon > 0$, we say that an element $b$ $\varepsilon $-approximates $a \in A$ if $d(a, b) \leq \varepsilon $.