<p>Use Taylor series expansion for the function <span class="math-container">$\prod_{i=1}^{n} (u_i + y)$</span> around <span class="math-container">$y=0$</span> to obtain the error as <span class="math-container">$\epsilon (\prod_{j=1}^{n} u_j) \sum_{i=1}^{n} u_i^{-1} + O(\epsilon^2)$</span>. Note that Taylor series works for <span class="math-container">$\epsilon = O(1/poly(n))$</span>, because <span class="math-container">$\mathbf{u}$</span> is a unit normed vector and the product <span class="math-container">$\prod_{j=1}^{n} u_j &lt; 1$</span>. </p>

CC BY-SA 4.0
2019-05-07T21:29:23.000Z
I'm having some slight difficulty parsing this. Should it be "obtain the error as $\epsilon = ...$? Also, can we make a statement about how wrong our algorithm can be just in terms of $\epsilon$? Thanks! Still trying to wrap my head around this.
stats_man97531
CC BY-SA 4.0
2019-05-08T13:41:46.337Z
$n\epsilon+ O(\epsilon^2)$ should work
Soumya Basu
CC BY-SA 4.0
2019-05-07T21:01:28.210Z
2019-05-07T21:16:31.670Z
2019-05-07T21:16:31.670Z
Soumya Basu
<p>Say we have two unit vectors <span class="math-container">$\hat{u}, \hat{v} \in \mathbb{R}^n$</span> where <span class="math-container">$\hat{u} = (u_1,...,u_n)$</span> and <span class="math-container">$\hat{v}$</span> approximates  <span class="math-container">$\hat{u}$</span>. <span class="math-container">$~\hat{v} = (u_1+\epsilon, ...,u_n+\epsilon)$</span> where <span class="math-container">$\epsilon = \frac{1}{poly(n)}$</span>. </p>

<p>We have an algorithm which takes the product of all elements and outputs the product. For the exact case (with <span class="math-container">$\hat{u}$</span>), <span class="math-container">$x = \prod_i^nu_i$</span>. For the approximate case (with <span class="math-container">$\hat{v}$</span>), 
<span class="math-container">$x^* = \prod_i^n(u_i + \epsilon)$</span>. </p>

<p>What is the error of <span class="math-container">$x^*$</span> with respect to <span class="math-container">$x$</span>? How do we bound the error of <span class="math-container">$x^*$</span> in terms of epsilon? How is the error analysis typically handled in this situation?</p>

CC BY-SA 4.0
2019-05-07T20:59:07.843Z
Do you really mean it is the same $\epsilon$ in each coordinate, or do you perhaps mean $(u_1+\epsilon_1,\dots,u_n+\epsilon_n)$?  Do you care about relative error or absolute error?
D.W.
CC BY-SA 4.0
2019-05-08T07:42:03.403Z
1) this is neither computer science, nor research level. 2) your notation needs to be fixed the way @DW suggested. 3) already for $n=2$ you can see that $|x^* - x|$ can be as large as $\epsilon(u_1+u_2) + \epsilon^2$ and will not be a function of only $\epsilon$.
Sasho Nikolov
<ds.algorithms><approximation-algorithms><upper-bounds><analysis-of-algorithms>
How is additive error handled in this simple algorithm? 'Product of all elements'
stats_man97531
# How is additive error handled in this simple algorithm? 'Product of all elements'

(Asked by: username_0 on 2019-05-07)

Say we have two unit vectors $\hat{u}, \hat{v} \in \mathbb{R}^n$ where $\hat{u} = (u\_1,...,u\_n)$ and $\hat{v}$ approximates $\hat{u}$. $~\hat{v} = (u\_1+\epsilon, ...,u\_n+\epsilon)$ where $\epsilon = \frac{1}{poly(n)}$.

We have an algorithm which takes the product of all elements and outputs the product. For the exact case (with $\hat{u}$), $x = \prod\_i^nu\_i$. For the approximate case (with $\hat{v}$),
$x^\* = \prod\_i^n(u\_i + \epsilon)$.

What is the error of $x^\*$ with respect to $x$? How do we bound the error of $x^\*$ in terms of epsilon? How is the error analysis typically handled in this situation?

**Tags:** ds.algorithms, approximation-algorithms, upper-bounds, analysis-of-algorithms

> **Comments:**
> **username_1**: Do you really mean it is the same $\epsilon$ in each coordinate, or do you perhaps mean $(u_1+\epsilon_1,\dots,u_n+\epsilon_n)$?  Do you care about relative error or absolute error?  
> **username_2**: 1) this is neither computer science, nor research level. 2) your notation needs to be fixed the way @DW suggested. 3) already for $n=2$ you can see that $|x^* - x|$ can be as large as $\epsilon(u_1+u_2) + \epsilon^2$ and will not be a function of only $\epsilon$.  

---

## 1 answers

### Answer by username_3 on 2019-05-07. Score: 2

Use Taylor series expansion for the function $\prod\_{i=1}^{n} (u\_i + y)$ around $y=0$ to obtain the error as $\epsilon (\prod\_{j=1}^{n} u\_j) \sum\_{i=1}^{n} u\_i^{-1} + O(\epsilon^2)$. Note that Taylor series works for $\epsilon = O(1/poly(n))$, because $\mathbf{u}$ is a unit normed vector and the product $\prod\_{j=1}^{n} u\_j < 1$.

> **Comments:**
> **username_0**: I'm having some slight difficulty parsing this. Should it be "obtain the error as $\epsilon = ...$? Also, can we make a statement about how wrong our algorithm can be just in terms of $\epsilon$? Thanks! Still trying to wrap my head around this.  
> **username_3**: $n\epsilon+ O(\epsilon^2)$ should work  

---

