4
$\begingroup$

Is there an analytic approximation to the inequality:

$$\sum_{i=1}^{n} |x_i| \leq \delta ? $$

I would like to replace the above inequality with a smooth inequality that is "valid" in the sense that if the approximate smooth inequality is satisfied then the original inequality will also be satisfied. It would also be great if the approximating inequality is tight. I have an intuitive idea of "tightness" but don't know how to formalize it for $n > 1$.

$\endgroup$
1
  • $\begingroup$ Please define $x_i$. The question as it stands now is a good candidate to be closed as "not a real question". $\endgroup$
    – Sasha
    Commented Jul 18, 2012 at 15:49

3 Answers 3

9
$\begingroup$

For every positive $u$, the functions $f_u$ and $g_u$ defined by $$ f_u(x)=\frac{x^2}{\sqrt{x^2+u^2}},\qquad g_u(x)=\sqrt{x^2+u^2}, $$ are smooth and such that, for every $x$, $$f_u(x)\leqslant|x|\leqslant g_u(x).$$Furthermore, the error one makes when replacing $|x|$ by $f_u(x)$ or by $g_u(x)$ is at most $$ g_u(x)-f_u(x)=\frac{u^2}{\sqrt{x^2+u^2}}\leqslant u, $$ uniformly on $x$.

Hence, for small (quantifiable) positive values of $u$, the functions $$\sum\limits_{i=1}^nf_u(x_i)\qquad\text{and/or}\qquad\sum\limits_{i=1}^ng_u(x_i)$$ are smooth and accurate approximations of $$\sum\limits_{i=1}^n|x_i|$$ Every $u\leqslant\varepsilon/n$ yields a uniform error which is at most $\varepsilon$, thus all this yields, for example, for every $x$, $$\left|\sum\limits_{i=1}^n|x_i|-f(x)\right|\leqslant\varepsilon$$ where $$f(x)=\sum\limits_{i=1}^n\frac{nx_i^2}{\sqrt{n^2x_i^2+\varepsilon^2}}$$

$\endgroup$
4
  • 1
    $\begingroup$ I was thinking of using $\sqrt{x^2+\alpha^2}$ where the error is bounded by $$ \color{#C00000}{0\le\sqrt{x^2+\alpha^2}-|x|}=\frac{\alpha^2}{\sqrt{x^2+\alpha^2}+|x|}\le\frac{\alpha^2}{\sqrt{x^2+\alpha^2}}\color{#C00000}{\le\alpha} $$ but the two functions are nice. (+1) $\endgroup$
    – robjohn
    Commented Jul 21, 2012 at 7:48
  • $\begingroup$ @robjohn (Thanks.) The function $f_u$ is a tiny bit more accurate than the lower bound $\sqrt{x^2+u}-\sqrt{u}$ when $x$ is small, but all these are similar, really. $\endgroup$
    – Did
    Commented Jul 21, 2012 at 8:13
  • $\begingroup$ What about the approxximation g(x) = x erf(\frac{x}{\sigma})? It seems that is more accurate than f_u(x) and g_u(x). $\endgroup$
    – Ravi
    Commented Jul 22, 2012 at 17:01
  • $\begingroup$ @Ravi: Yes, what about it? More accurate in which sense? Note that, when $u\to0$, the supremum norm of the difference goes to zero. $\endgroup$
    – Did
    Commented Jul 22, 2012 at 20:32
0
$\begingroup$

The original inequality defines a nonsmooth body (cross-polytope, I think is the name). We want to approximate it by a smooth inscribed body.My proposal is to replace the nondifferentiable function $|x_i|$ with $\sqrt{x_n^2+\epsilon}$ which is differentiable and greater than the original function. So if the new inequality holds, so does the old. The smaller $\epsilon$ you take, the "tighter" is the approximation.

$\endgroup$
0
$\begingroup$

I found that $ |x| $ can be approximated by the smooth function $ g(x) = x \cdot \mathrm{erf}(\frac{x}{\sigma}) $. We can get accurate approximation by letting $ \sigma $ go to $ 0 $.

$\endgroup$
1
  • $\begingroup$ This seems to work as an approximation of $|x|$, with the additional property that $g(x=0) = 0$ if that matters. $\endgroup$
    – alfC
    Commented May 11, 2020 at 21:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .