ChapterZero

I was searching my sister’s room for interesting books when I came across her webcam (does this sound like too gross an invasion of privacy? :)). Since we need a webcam for our senior design project– right now we’re using an Apple iSight, which has an unfortunate requirement that the machine it’s being used on be an Apple, as well as a tendency to blur our upclose pics of resistors– I decided to try hers out. I was especially ecstatic when I discovered it has 1024×768 still shot capability; that was a feature that I’d been looking for– the iSight only seems to do 640×480. After a little trouble, I got it installed, and working with python; however, even though with the software that comes with it, it can reach 1280×960, with python I can only set it up to 640×480. Maybe that’s because I also can’t tell it to go to a ’still’ mode– it stays in constant 30 fps mode– or maybe the resolution gain is done through software, or maybe for both these reasons.

Anyhow, I got something working with python, so that’s proof of concept and one mark for my side: the one member of our team who has a strong opinion on the subject wants to build the system to run on an Apple, with the iSight. My objection to that stems from the fact that part of our marketing strategy is to place the system in the school’s circuits lab, and all the machines there run windows. Anyhow, it’s always a good idea to go with Windows for these types of projects, so you don’t confuse the profs unnecessarily.

Incidentally, I realized that I’ve never had my picture taken on a webcam before, and never had one posted to the site, so here’s one picture of a very handsome man:

If is a vector space over a field and , we have the following definitions to consider:

1. is convex if whenever and . Here is or .
2. If whenever , then is balanced.
3. The set is absorbing if, for each , there is a positive number such that whenever .

An introduction to Banach Space Theory. Robert E. Megginson

Some consequences of sets’ having these properties are well known or intuitively obvious, especially concerning convexity. Here are some interesting questions, from the same source:

1. Identify all the balanced subsets of . Do the same for .
2. Suppose that is balanced. Prove that is absorbing iff for each there is a positive number such that .
3. Prove that each convex absorbing subset of contains a neighborhood of . Is this true for nonconvex absorbing subsets of ?

In relation to the last question above, consider the polar graph of the relation

Two easy problems. The first one illustrates a general idea that is useful (it can be used to help in analytically deriving the FTA, for instance): show that an even polynomial achieves its minimum on . The second, while interesting, doesn’t have any immediately interesting applications I know of:

Define the convex (a.k.a. Fenchel) conjugate of a function to be the function defined by

show that if and with but not necessarily an integer, then .

I finally saw a complete episode of Numb3rs last night– yes, I am way behind the times. In this episode, Charlie was helping the FBI track two escaped fugitives. The quality of the show surprised me: I was expecting a watered down show, one with all hints of adult content washed out for the kiddies, and the mathematical sophistication of at most a college freshman. There was not any of the gratuitous cursing that mars a lot of today’s reality dramas, and I did notice an emphasis on family dynamics that reminded of Judging Amy, but this episode was not overly saccharine: there was an aborted sex scene, when Charlie’s brother interrupted one of the convicts and his girlfriend mid-coitus. And although the main character repreated certain words way more than necessary–e.g., Bayesian, Markov chain–, the eventual application of math seemed to justify the mentioning of them.

The only two bitter notes left from the show are: 1) the fact that the FBI didn’t even consider that the vehicular collision that gave the convicts their opportunity was staged until Charlie mentioned it, and 2) the writers’ insistence on drawing out Charlie’s discovery that the accident had been rigged. I suspect the latter was done because Charlie only had to apply simple algebra and high school physics to make that discovery; to make it smell more mathematical, they had him talk about modeling the accident using a Markov chain. I’m not even sure what that entails: exactly what aspects of the accident could be modeled in a useful manner using Markov chains, and how would they be relevant to the investigation? The convicts were already loose, and we already knew the accident was staged. At least Charlie’s episodic fascination with Markov chains, and as he refers to it ’statistical probability’ (as opposed to the non-statistical kind, I suppose), paid off in the manner in which he tracked one of the fugitives down.

That was the core instance of applied math: from the FBI tipline reportings, collated information on recent crimes that he might be responsible for, and the location of family and friends, Charlie made a time series of possible locations of the fugitive. Then, he used some kind of Bayesian inferential techniques to denoise the data– mainly to counteract the uncertainty and corruption in the data coming from the tiplines– and come up with a pattern to the convicts’ movements. It would have been nice if he’d specified in more detail exactly what methods he used, but I suspect then the show would’ve turned into a math lecture. Like Simon Alexander, the newest postdoc in the wavelets group said in reference to explaining harmonic analysis to a Cal I class: “you can either say very little, or very much; there’s not much in between.”

As long as it illustrates one or more non-obvious application of advanced mathematics per episode, I’ll continue to think Numb3rs is worth watching.

Note: I spent a weekend writing a simple implementation of the inefficent spline paradigm described here, in PyGTK; check it out: get the python spline fitting and evaluation code, and PyGTK stub interface. The feature set is small: add new points in the interface by left clicking, and middle click to clear.

Here’s the motivating problem: you have points observed at times – say, samples of the position function of a particle tracing out a path– and you’d like to fit a smooth curve to these points. An intuitive approach to this problem is to represent parametrically, and fit smooth curves to the abscissa and ordinates; this reduces the problem to that of fitting curves to points, which we can solve in many different ways (Lagrange interpolation, etc.) One approach which has several desirable features is that of interpolating splines.

Interpolating splines can be developed under the energy minimization paradigm, in an interesting manner. Under this paradigm, the problem is to, given the points find a smooth function satisfying:

where , the energy function, represents some measure of the undesirability of using the function to represent . The energy function has two components, , the internal energy, which corresponds to a measure of the desirability of , and , the external energy, which corresponds to the compatibility of and . To develop splines, we use

that is, we look for functions whose variation (measured as the norm of their -th derivative) is minimal, and which fit the data points in a least means squared sense. The parameter controls the relative importance we assign to and ; in what follows, when it matters, we assume is fixed.

Here’s the first amazing result: Such exist, and furthermore

1. The curve is a polynomial of degree on each interval
2. At each point , the first derivatives of are continuous, while the -th can be discontinuous.
3. In each of the intervals and ,

I’d love to see a proof of this theorem– I suspect it uses the variational calculus. Certainly (ii) and (iii) are obvious, but (i) is not to me.

Now, we can define splines:

A curve that satisfies (i) and (ii) with is called a cubic or bending spline with knots . If it also satisfies (iii), it is called a natural cubic spline. An interpolation spline is a cubic spline which passes through the points .

So the above theorem guarantees the existence of interpolating cubic splines. But we can do even better, with the next theorem, which shows us how to construct such splines:

Let be values set according to . There is only one natural spline interpolating these values.

Proof:
By (i) above, on each interval , has the form

For convenience, set and , then you can show

and from (ii) above, we have for , giving

This gives us equations we can solve for the unknowns (we know by (iii) ); these relations can be written in the linear system , where is a tridiagonal matrix, is a tridiagonal matrix, is the -vector of 2nd derivatives of , and is the -vector of the values should interpolate. This system can be solved for , and these values can be used to calculate the

See my code for implementation of this scheme for 2d interpolation. At some point, I’m going to show how the energy minimization scheme can be adapted from interpolation to smoothing.

This morning my senior design group met to discuss our pre-proposal, and surprisingly, we found that our number three choice became our number one. Now we’re proposing to develop an automated sorting machine– in this case, our choice of things to sort is resistors. Why the switch? This project is useful, and much easier conceptually.

Our approach breaks the task down into two tasks: design of an algorithm to locate desired resistors in an image, and managing a robotic pincer to physically isolate the desired resistors once found. My team seems willing to let me handle the image processing part, and pretty much do nothing on the robotic part. Although designing a control algorithm for the pincer may be an interesting problem– is an algorithm really needed? we’re hoping it’ll be more of a point and grasp thing– I’m relieved to be free from dealing with hardware.

Here’s my tentative algorithm for the pre-proposal: run an edge detector on the image, isolate line segments (fortuitously for me, we’re using the resistors that are color coded with linear stripes) to locate resistors, and maybe curve extraction to determine the orientation of the resistor, for more information on how to grasp it. Once you’ve located the color stripes, you can check their color to see if the resistor is one of the ones desired. It seems pretty straightforward: even the curve extraction isn’t really needed– once you know the location of the color strips and their inclination, you pretty much know all you need to about the resistor. But… everything looks harder when you’re down in the dirt getting it working, so maybe writing the algorithm will be harder than writing the GUI after all

I’m thinking of using the Hough transform to do the line segment detection.

We’re in the process of bidding for projects in my Senior Design class– we have 15 projects to choose from, and have to select our top 3 choices. My team’s number one choice was the ‘Mini-Me’ Lego robot project, in which we are to create a robot that mimics the movements of a human being monitored with a video camera. I thank the powers that be that nowhere on our list is any of the electronic/circuit/solid-state type projects that dominated the list– as interesting as it may be to design a laser system for measuring the stresses in thin film depositions, I have neither the desire nor copious free time required for any of those hardware construction/lab-intensive projects. Nope, all our choices have a strong signal processing component, just the way I like it.

The question is, how best to attack this problem? My first idea, and probably the most realistic given our time constraints, is to model people as cylinders connected with kinematic constraints, slap a few markers on people and track their movements through those, degrade the movements to a level that the robot can handle, and change them into control signals to the motors. But what would be a more mathematically elegant way of approaching this? The first thing that came to mind was active contours, but even if I could manage to get one to fit the human body perfectly, it’d still be hard to get useful information on local movements from such a model.

It’s an interesting problem to ponder… any bright ideas?

I’ve been having a very hard time reading Grafakos’ book: I’ve spent probably four hours reading only about 6 pages. Part of the reason for this, I hope, is because he expects the introductory material on and weak spaces to be a review– while for me it is new material. If this is what the entire book is like, then I’m in for a rough semester.

One of the points that stumped me for a long time is his proof of the fact that , which uses Chebyshev’s inequality. He states that it is a simple consequence of Chebyshev’s inequality that:

which shows that .

At first I thought he was referring to the probabilistic statement of the inequality:

which I had problems even finding (even planetmath lists the Chebyshev inequality as a sum inequality, with no mention of the continuous version). Even when I did dredge it out of a reference book, I was puzzled– in this case, what would be, and how could I massage this formula to get Grafakos’?

I just found the answer to my question: the general measure theoretic statement of Chebyshev’s inequality as per wikipedia is: if is a nonnegative extended real-valued measurable function, nondecreasing on the range of , then

which looks more pertinent.

Clearly I need to learn more measure and integration theory than I have so far.

Let , and define the distribution function of ,

.

It has the following properties:

1. -a.e. implies that
2. for all
3. 
4. 

Here’s a neat result from Grafakos’ ‘Classical and Modern Fourier Analysis’: if is increasing and , then

Actually, I think you also need to state . As a special case,

.

The proof consists of writing as an integral in terms of , extending the limits of integration of that integral to by inserting an appropriate characteristic function , using Fubini’s theorem– then the trickiest part is recognizing that the original characteristic function is exactly the same as the one needed to get as your interior integral. I’m too lazy to write it out, but it’s a good exercise: it took me embarassingly long to figure out how Grafakos applied the Fubini theorem (namely, the equivalence of the characteristic functions).

The interesting thing about the distribution function is that it is not unique to the function (as a trivial example, under Lebesgue measure, is the same for all translates of ), yet it determines the value of these particular functionals at .

As an example, let

You can use the above result to show . A non-trivial result!