# Smooth Approximation of Indicator Function of Convex Sets in $\mathbb{R}^n$

Let $( \mathbb{R}^n, \| \cdot \|_P)$ be the $n$-dimensional Euclidean space equipped with $\ell_p$-norm $\| \cdot \|_p$ for some $p\in [1, + \infty]$. Let $A$ be a convex set in $\mathbb{R}^n$ and define \begin{align} A^{\epsilon} = \{ y \in \mathbb{R}^n \colon \exists x \in A~\text{such that}~\| x -y \| _{p} \leq \epsilon \}, \end{align} where $\epsilon >0$ is a real number. In general, what is the condition that there exists a $3$-order differentiable function $f \colon \mathbb{R}^n \rightarrow [0,1]$ such that $f$ is a good approximation of $\mathbb{1}_{A}$, which is the indicator function of set $A$.

In specific, it is ideal that $f(x) = 1$ when $x\in A$ and $f(x) = 0$ when $x\in \mathbb{R}^n \setminus A^{\epsilon}$. Moreover, the $\ell_q$-norm of the $i$-th order gradient of $f$ is proportional to $\epsilon^{-i}$ for $i = 1,2,3$. That is \begin{align} \| D^{(i)} f (x) \|_{q} \leq C_i \cdot \epsilon^{-i}, ~\text{for any}~~ i = 1,2,3. \end{align} Here the high-order gradients are taken as vectors, $1/q + 1/p = 1$, and $\| \cdot \|_q$ is the dual-norm of $\| \cdot \|_p$.

An inspiration of this problem is that for $p = q= 2$, the problem is solved for any convex sets. In addition, for rectangles of the form $\{ x \in \mathbb{R}^n \colon a_i \leq x_i\leq b_i, i =1, \ldots, n\}$, approximation under $\ell_{\infty}$ is also established. This approximation depends on the function $g(x） = 1/\rho \cdot \log [\sum_{i=1}^n \exp( \rho\cdot x_j)]$ which approximates the function that returns the maximum element of a vector in $\mathbb{R}%d$. See https://arxiv.org/abs/1412.3661v4. But general convex sets in $(\mathbb{R}^n, \| \cdot \|_{\infty})$ is not covered.

Moreover, for Banach spaces, similar results are also established for $\| \cdot \|_{B}$, which is the norm in the Banach space. However, such result depends on the differentiability of $\| \cdot \|_B$, which does not handle convex sets in $(\mathbb{R}^n, \| \cdot \|_{\infty})$.

• The standard way is to convolve the indicator function with a bump. What do you mean by the $\|\cdot\|_p$-norms? Just renorming the finite-dimensional euclidean space does not seem very useful to me. – Jochen Wengenroth Jun 13 '16 at 10:24

Let's pursue Jochen's idea. We assume $A \ne \emptyset.$

Let $$\varphi(t) = \begin{cases} e^{-\frac{1}{t}} &\text{if  t>0}\\ 0 &\text{otherwise.} \end{cases}$$

This function is $\mathcal C^{\infty}$, and $0 < \varphi(t)$ iff $0<t.$

Define $\rho$ as $$\rho(x) := k \varphi(1- \|x\|_2^2)$$ where $k$ is chosen so that $\int \rho(x)\space dx =1.$ $\rho$ is $\mathcal C^{\infty}$, $0 \le \rho$, and $0< \rho(x)$ iff $\|x\|_2^2 < 1.$

Let $\delta > 0$. Set $\rho_{\delta}(x) = \frac{1}{\delta^n} \rho(\frac{x}{\delta})$. Note that $0<\rho_{\delta}(x)$ iff $\|x\|_p < \delta$, and $\int \rho_\delta = 1.$

Let $\mathscr O = A+B_2(0,\delta)$, and consider the function
$$f = I_{\mathscr O} \ast \rho_{\delta} .$$

Clearly $0 \le f \le 1$ and $f$ is $\mathcal C^{\infty}.$

If $a \in A$, then $B_2(a,\delta) \subset A+B_2(0,\delta) = \mathscr O$, so $I_{\mathscr O } \ast \rho_{\delta}(a) = 1.$

If $x \notin A+B_2(0,\delta)$ then $B_2(x,\delta) \cap (A + B_2(x,\delta)) = emptyset$, so $I_{\mathscr O } \ast \rho_{\delta}(x) = 0.$

For derivatives of any order:
$$D^\nu f(x) = D^\nu \int_{\mathscr O} \frac{1}{\delta^n} \rho(\frac{x-y}{\delta}) dy = \frac{1}{\delta ^{|\nu|}} \int_{\mathscr O} \frac{1}{\delta^n} (D^\nu\rho)(\frac{x-y}{\delta}) dy$$ so $$|D^\nu f(x)| \le ( \int |(D^\nu\rho)(y)| dy)\frac{1}{\delta ^{|\nu|}}.$$

Finally, for any $p$, there is a constant C (depending on $p$ and $n$) such that $B_2(0,1) \subset B_p(0,C_p)$. Therefore:
$$A \subset A+B_2(0,\delta) \subset A+B_2(0,2\delta) \subset A+B_p(0,2C_p\delta) = A + B_p(0,\epsilon) = A^{\epsilon}$$ if we take $\delta = \epsilon /(2C_p) .$

With this choice of $\delta$, the function $f$ satisfies all the requirements.

$$\dots\dots\dots$$ In order to apply the result without distinguishing the dimention $n$ of the underlying space, it is of interest to consider the following lemma.

$\mathbf{Lemma}$: Given $p \in \{1,2\} \cup (3,+\infty]$, there is $\rho:\mathbb R^n \rightarrow \mathbb R$ such that:
i) $\rho$ is $\mathscr C^3$
ii) $0 \le \rho$
iii) $\rho(x) > 0$ iff $\|x\|_p < 1$
(iv) and, by re-scaling, $\int \rho(x) \space dx = 1$)

With this choice of $\rho$ the original argument can be carried without resorting to the 2-norm.

$\mathbf{Proof}$: With $\varphi$ as above, if $p \in \{2\} \cup (3,+\infty)$, define $\rho$ as $$\rho(x) := \varphi(1- \|x\|_p^p) .$$ With this choice, $\rho$ satisfies i,ii,iii. The condition $p>3$ is needed to justify the claimed smoothness of $\rho.$

If $p=1$ or $p=\infty$, note that the open unit ball in $(\mathbb R^n , \|.\|_p)$ is a polytope of the form $P=\{x| v_i^{'}x<1\}.$ When $p=\infty$, $\{v_i\} = \{\pm e_j\}$ where $\{e_j\}$ is the canonical (vector space) bases of $\mathbb R^n$. When $p=1$, $\{v_i\} = \{-1,1\}^n$. In these cases, take $\rho$ as $$\rho(x) = \prod_i \space \varphi(1-v_i^{'}x) . \blacksquare$$

• Thanks very much, Victor! I think the second argument about the values $I_{\mathcal{O} }* \rho_{\delta}(x)$ should be for $x \notin A + B_2(0, 2\delta)$. In addition, for general $\ell_p$ balls, you utilize the fact that the $\ell_p$ norms are equivalent in the topological sense. But the constant $C_p$ may depends on the dimension $n$. Is it possible to have something that is dimension free? – Steve Aug 8 '16 at 6:49
• I thought you were going to ask that! My first attempt had a $\rho$ taylor to the norm, and the argument $f = 1$ in $A$ and $0$ outside $A^{\epsilon}$ could be done using balls in the p-norm. But I thought that the bounds on derivatives of $f$ would involve $n.$ May be you or someone can check, and see if there is a way out. I'll add the construction of the $\rho$ as answer. – VictorZurkowski Aug 8 '16 at 15:43
• Thanks again for your help! Another question is whether $\int |D^{\nu} \rho(y) | d y$ depends on dimension $n$. Can it be dimension free? In paper On the dependence of the Berry–Esseen bound on dimension'' (mii.lt/files/Bentkus_2003_2.pdf) an approximation function is constructed as $f_{\delta} (x) = g( d(x,A)/\delta)$, where $d(x,A)$ is the distance of $x$ to set $A$ and $g$ is smooth and supported on $[0,1]$. They show that the derivative of this function is bounded by $2/ \epsilon$ and the hessian bounded by $8/\epsilon^2$. Can we prove similar things using mollifier? – Steve Aug 13 '16 at 15:26
• I think that quantity is indeed dimension free because we can explicitly write the normalization constant in $\rho(y)$ as a integral. Then $int | D^{\nu} \rho(y) | dy$ can be written as a integral with respect to the $|y|$, using spherical coordinates. The quantity that involving dimension is canceled by the normalization constant and we are left with a integral on $[0,1]$, which is finite and dimension-free. – Steve Aug 13 '16 at 16:07