Specific Problem: For concreteness, less us consider a specific problem. Suppose \(x_i = -1000 + (i-1)\), and \(N = 101\). Thus, we are interested in the following summation, \[F = \log \left(e^{-1000} + e^{-1001} + ... + e^{-1100} \right).\]
Exact Solution: The term in the parenthesis is a geometric series, with \(a = e^{-1000}\) and \(r = 1/e\). Thus, exact solution may be obtained from the geometric series summation formula: \[Z = \frac{a (1-r^N)}{1-r}.\] Thus, \[F = \log Z = \log a + \log (1 - r^N) - \log (1-r),\] which can be evaluated, yielding \(F = -999.54\).
Brute Force Solution: If we attempt a brute force evaluation using the following Matlab commands
a = -1000;
b = -1100;
y = [a:-1:b]';
SumX = log(sum(exp(y)))
We get -Inf as the answer, since the brute flow calculation leads to underflow.
Analysis: If we knew all the \(x_i\) before carrying out the summation, we could use the technique I describe next. Note that this technique would not work if we had to keep a running (logarithm of) sum (that is the \(x_i\) were streaming in, one by one).
However, as I describe in a following post, we can repurpose the key idea from this method to tackle the general problem.
The key insight recognizes that we can rewrite the problem as: \[F = \log e^{-1000} \left(1 + e^{-1} + ... + e^{-100} \right).\] Using the property of logarithms, this implies, \[F=-1000 + \log \left(1 + e^{-1} + ... + e^{-100} \right).\] This second term in the series does not pose significant numerical problems if summed up directly.
The series does add up to -999.54, as expected.
When we pulled out the \(e^{-1000}\), we essentially descaled the problem. If we knew all the \(x_i\) beforehand, we can pull out the most significant (read largest) term out, and sum up the remaining lower order terms without bumping into false infinities or zeros.
However, if we don't have the entire string of \(x_i\) available, we don't know what the most significant term is. Right?
Wrong!
In the future post, I will discuss how we can view the summation pairwise, and repurpose this same idea to address the above shortcoming.
Exact Solution: The term in the parenthesis is a geometric series, with \(a = e^{-1000}\) and \(r = 1/e\). Thus, exact solution may be obtained from the geometric series summation formula: \[Z = \frac{a (1-r^N)}{1-r}.\] Thus, \[F = \log Z = \log a + \log (1 - r^N) - \log (1-r),\] which can be evaluated, yielding \(F = -999.54\).
Brute Force Solution: If we attempt a brute force evaluation using the following Matlab commands
a = -1000;
b = -1100;
y = [a:-1:b]';
SumX = log(sum(exp(y)))
We get -Inf as the answer, since the brute flow calculation leads to underflow.
Analysis: If we knew all the \(x_i\) before carrying out the summation, we could use the technique I describe next. Note that this technique would not work if we had to keep a running (logarithm of) sum (that is the \(x_i\) were streaming in, one by one).
However, as I describe in a following post, we can repurpose the key idea from this method to tackle the general problem.
The key insight recognizes that we can rewrite the problem as: \[F = \log e^{-1000} \left(1 + e^{-1} + ... + e^{-100} \right).\] Using the property of logarithms, this implies, \[F=-1000 + \log \left(1 + e^{-1} + ... + e^{-100} \right).\] This second term in the series does not pose significant numerical problems if summed up directly.
The series does add up to -999.54, as expected.
When we pulled out the \(e^{-1000}\), we essentially descaled the problem. If we knew all the \(x_i\) beforehand, we can pull out the most significant (read largest) term out, and sum up the remaining lower order terms without bumping into false infinities or zeros.
However, if we don't have the entire string of \(x_i\) available, we don't know what the most significant term is. Right?
Wrong!
In the future post, I will discuss how we can view the summation pairwise, and repurpose this same idea to address the above shortcoming.
No comments:
Post a Comment