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})$.

  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 13, 2016 at 10:24

1 Answer 1


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$$

  • $\begingroup$ 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? $\endgroup$
    – Steve
    Commented Aug 8, 2016 at 6:49
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 8, 2016 at 15:43
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Commented Aug 13, 2016 at 15:26
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Commented Aug 13, 2016 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.