Tuesday, September 30, 2014

Identify the Thief

We are terrible at remembering faces shown to us fleetingly. This video, for example, admirably demonstrates this effect: 4/5 people pick the wrong guy!

On a trip from Denver, we were unfortunate enough to see this play out in practice. We were returning from a very satisfying trip to Yellowstone National Park. After returning our rental van (4 adults and 2 kids), we boarded an Avis bus that was supposed to take us to the terminal. We were tired, anxious to get back home, and somewhat distracted.

There is always plenty of distraction when travelling with two little kids.

There were three other people in the same Avis bus: two guys and a lady. One of the guys (who turned out to be a thief) even dropped something during the trip. I watched him get out of his seat, pick it up, and get back in.

After the bus stopped, one of the guys and the lady got off, and I almost bumped into the thief, and politely gave him the right of way. He said, "after you, please", and I got off, and ran to a get a trolley to haul our luggage.

When I returned, I saw that one of our backpacks was missing. I tried running into the airport terminal to find this guy, but I'm embarrassed to confess that seriously I only had the vaguest idea what he looked like.

And I had two "good" looks at him.

This memory effect is especially not good when you're in a sea of people at Denver International Airport.

In any case, we lost a couple of passports, which led to some irritation, and an old digital camera.

More significantly, I  lost a little more trust in strangers, which unfortunately, is less easy to replace.

Friday, September 26, 2014

Interesting Links

1. How MOOCs may have the last laugh after all. (Aswath Damodaran)

2. Murray Gell-Mann: TED talk on Beauty, Truth and Physics

3. The magic of decaffeination: (YouTube video)

4. The link between artificial sweeteners and diabetes: Steve Novella explores problems in a recent study.

5. Online books on Ordinary Differential Equations

Wednesday, September 24, 2014

Interesting Questions

In the past month, I got asked two extremely inquisitive questions by an elementary school kid. I paraphrase them for context and clarity.

1. The upper floor of a two-level house is warmer than the lower floor. In fact, I wrote about this question a long time ago. Warm air is lighter (from ideal gas law, for example) and floats above dense cold air.

Q: If that is so, then why does it get colder as we climb or drive up a tall mountain?

2. What is the temperature of a mixture of ice and water? Until all the ice melts, the "classic" answer is zero centigrade.

Q: If there are icebergs floating in the earths oceans, why isn't the temperature of the oceans equal to zero centigrade?

Friday, September 19, 2014

DCT in 2D: Symmetric Functions

This is an extension of a previous post that sought to approximate a 1D function \(f(x), ~ x \in [0,1)\), that is symmetric about \(x = 1/2\). That is, the shape of the function above the line of symmetry is a mirror image of the function below it.

As as example, we considered the function:  \[f(x) = (1/2-x)^2 + \cos(2 \pi x).^2.\]
We sample the function at \(n\) equispaced points \(x_i = i/(n+1)\), where \(i = 0, 1, 2, ..., n\). Given the bunch of points \(\{x_i, f_i\}\), we approximate the function using a sum of discrete cosine functions, \[f(x) \approx \sum_{j=0}^{N-1} a_j v_j(x_i),\] where,  \(v_j(x) = \cos(2 \pi j x)\) is a typical orthogonal basis function, and \(N\) is the number of basis functions used.

In this post, we add a small wrinkle to the original problem.

Suppose we had a 2D function \(G(x,y) = f(x) f(y)\). This is certainly a special kind of 2D function. It has mirror symmetry about the centerline which it inherits from \(f(x)\). In addition, it has a very special symmetry along the \(x\) and \(y\) directions. For example, \(G(x,y) = G(y,x)\).

For concreteness, let us use the particular \(f(x)\) that we considered above, and build a \(G(x,y)\) out of it. It looks like:


clear all
clf

% number of collocation points is (n+1)
n  = 20;  
% collocation points for discrete cosine series
xi = [0:n]'/(n+1);
% grid is equivalent in the x and y-directions
yi = xi;

%
% Sample Function
%
f = @(x) (1/2-x).^2 + cos(2*pi*x).^2;

[X, Y] = meshgrid(xi);
G      = f(X).*f(Y);

surf(X,Y,G)
view(40,40)
xlabel('x')
ylabel('y')
zlabel('G(x,y)')


Since the "x" and "y" grid-points are at identical locations, we can assert\[G(x_i, y_j) =  \sum_{j=0}^{N-1} a_j v_j(x_i) \sum_{k=0}^{N-1} a_k v_k(y_j.)\] In the matrix language developed in the original post, this is equivalent to \[\mathbf{G} = \mathbf{V a}  (\mathbf{V a})^T = \mathbf{V A V^T},\] where \(\mathbf{A} = \mathbf{a a^T}\).

Using the property of orthogonality, we hit both sides with the appropriate factors to obtain \[\mathbf{V^T G V} =   \frac{(n+1)^2}{4} \begin{bmatrix} 2 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0& 0\\ 0 & 0& 0& 1 & 0\\ 0 & 0 & 0& 0& 1\end{bmatrix} \mathbf{A}  \begin{bmatrix} 2 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0& 0\\ 0 & 0& 0& 1 & 0\\ 0 & 0 & 0& 0& 1\end{bmatrix}.\]  If \(\mathbf{a} = (a_0, a_1, ..., a_{N-1})\) then this implies that the RHS is equal to, \[\frac{(n+1)^2}{4} \begin{bmatrix} 4 a_0^2 & 2 a_0 a_1 & 2 a_0 a_2 & ... & 2 a_0 a_{N-1}\\ 2 a_1 a_0 & a_1^2 & a_1 a_2 & ... & a_1 a_{N-1}\\ 2 a_2 a_0 & a_2 a_1 & a_2^2 & ...&  a_1 a_{N-1}\\  \vdots & \vdots & \vdots & \vdots & \vdots \\ 2 a_{N-1} a_0 & a_{N-1} a_1 & a_{N-1} a_2 & ... & a_{N-1}^2\end{bmatrix},\]

In the above equation, the LHS is known. The diagonal of the the computed matrix yields the vector \(\mathbf{a}\) that we seek.

Programmatically,

nmodes   = 7;

%
% Build the matrix of basis vector V = [v_0 v_1 ...  v_N-1]
%

V     = zeros(n+1, nmodes);
V(:,1) = ones(n+1,1);

for j = 2:nmodes
  V(:,j) = cos(2*pi*(j-1)*xi);
end

%
% Compose the matrix: The key step
% Replace small negative values with 0 to prevent imaginary roots
%

M      = diag(V'*G*V);
M(M<0) = 0;                
M      = sqrt(M);

a    = zeros(nmodes,1);
a(1) = M(1)/(n+1);

a(2:nmodes) = 2*M(2:nmodes)/(n+1);

%
% Compute Norm on the Same Grid
%
g       = V*a;
Gapprox = g*g';
disp('Norm of Error');
norm(Gapprox - G)/(n+1)^2


This yields the coefficients for the basis vectors which can be used to reconstruct the function. Here are contour plots of the original data on the grid, and the smooth fitted function.




Wednesday, September 10, 2014

Links

1. Why Arkansas is pronounced differently from Kansas

2. Mathematical Gifs my David Whyte

3. Tennis Ball + Soccer Ball = Interesting Physics Lesson

4. The Big History Project and Bill Gates

Monday, September 8, 2014

The Magic of Compounding

While Albert Einstein may never have said that compound interest is "the most powerful source in the universe", the exponential growth implied by the magic of compounding can lead to spectacular outcomes.

Example 1: As as example, consider the following: You start with a penny on day one. On day two, you double it. So you have $0.02. On day 3, you double it again ($0.04), and so on.

Without actually carrying out the math, can you guess how much money you will end up with at the end of a 30 day month?

The answer of course is 2^29 pennies, which is over 5 million dollars!

Example 2: The idea is also enshrined in legend. Consider, for example, the story of the chess-board and grains of rice. Essentially, a king was asked to set one grain of rice in the first square, two in the next, and to keep on doubling until all the 64 squares on the chessboard were used up.

A quick calculation shows that the total number of grains would be \[2^0 + 2^1 + ... + 2^{63} = 2^{64} - 1.\] Assuming each grain weights 25 mg, this corresponds to more than 450 billion tonnes of rice, which is about 1000 times larger than the annual global production.

Example 3: What makes Warren Buffett fabulously wealthy? If you start with an amount \(P\) and grow it at an annual growth rate of \(i\) for \(n\) years, you end up with,\[A = P (1 + i)^n.\] Two ways to get compounding to work its magic is to have large growth rates and/or long incubation times. In Buffett's case, he has managed both; he's compounded money at more than \(i = 0.20\), for a long time, \(n=60\) years. With this $100 becomes, \[A = $100  (1+0.2)^{60} = $5,634,514.\]
Example 4: This is in someways my favorite example, because it doesn't deal with material things. It is an insight that comes from this essay that I wrote about a while ago. I love the following quote:
What Bode was saying was this: "Knowledge and productivity are like compound interest.'' Given two people of approximately the same ability and one person who works ten percent more than the other, the latter will more than twice outproduce the former. The more you know, the more you learn; the more you learn, the more you can do; the more you can do, the more the opportunity - it is very much like compound interest. I don't want to give you a rate, but it is a very high rate. Given two people with exactly the same ability, the one person who manages day in and day out to get in one more hour of thinking will be tremendously more productive over a lifetime.