Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks for any help, Ravi

share|improve this question
    
Please define $x_i$. The question as it stands now is a good candidate to be closed as "not a real question". –  Sasha Jul 18 '12 at 15:49
add comment

3 Answers

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$, $\sum\limits_{i=1}^nf_u(x_i)$ and/or $\sum\limits_{i=1}^ng_u(x_i)$ are smooth and accurate approximations of $\sum\limits_{i=1}^n|x_i|$. For example, every $u\leqslant\varepsilon/n$ yields an error at most $\varepsilon$.

share|improve this answer
1  
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) –  robjohn Jul 21 '12 at 7:48
    
@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. –  Did Jul 21 '12 at 8:13
    
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). –  Ravi Jul 22 '12 at 17:01
    
@Ravi: Yes, what about it? More accurate in which sense? Note that, when $u\to0$, the supremum norm of the difference goes to zero. –  Did Jul 22 '12 at 20:32
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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