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?

  • $\begingroup$ 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? $\endgroup$ – D.W. May 7 '19 at 20:59
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov May 8 '19 at 7:42

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – stats_man97531 May 7 '19 at 21:29
  • $\begingroup$ $n\epsilon+ O(\epsilon^2)$ should work $\endgroup$ – Soumya Basu May 8 '19 at 13:41

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.