1
$\begingroup$

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

$\endgroup$
  • 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$ – Jochen Wengenroth Jun 13 '16 at 10:24
1
$\begingroup$

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

$\endgroup$
  • $\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 Aug 8 '16 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$ – VictorZurkowski Aug 8 '16 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 Aug 13 '16 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 Aug 13 '16 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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