An intermezzo: MATH 245

Amongst all these serious posts concerning the stress of university and other such things, I believe it’s high time that I lighten things up — and what better way to lighten things up than with some math?

As promised, here’s the solution I gave to Problem #5 on the MATH 245 midterm. The problem was:

Let a_1, a_2, \ldots, a_\ell be points in \mathbf{R}^2. Show that there is a unique point x \in \mathbf{R}^2 which minimizes the sum \sum\limits_{i=1}^\ell |x-a_i|^2, and find a formula for this point x in terms of a_1, \ldots, a_\ell.

I was pressed for time on the exam, so since I couldn’t see any obvious solution of the problem by linear algebraic methods, I resorted (as I often do with problems like this) to tedious analytic methods. The general idea of it is as follows. You suppose a_i = (a_{i1}, a_{i2}), and define a function of two variables f(x,y) = \sum |(x,y) - (a_{i1},a_{i2})|^2. You then take the partial derivatives \frac{\partial f}{\partial x} and \frac{\partial f}{\partial y} which turn out to be \sum 2(x-a_{i1}) and \sum 2(y-a_{i2}) respectively. Setting these both equal to zero we obtain that (\tilde{x},\tilde{y}) = (\frac{1}{\ell} \sum a_{i1}, \frac{1}{\ell} \sum a_{i2}) which happens to be the centroid of the (possibly degenerate, and certainly degenerate if \ell > 3) simplex formed by those points in the plane.

When I reached this point in the solution, the exam was over, so I lost a few marks. To complete this solution, you have to take second derivatives and thereafter form the Hessian matrix of the function f. You then must show that the Hessian matrix is positive-definite in order to successfully prove that (\tilde{x}, \tilde{y}) is indeed a local minimum of f, and is hence the minimizing point we seek.


About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in linear algebra and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s