Mathematics and technology

One of the courses I was taking during my third year of undergraduate studies was a full-year Abstract Algebra course, covering among others ring theory and Galois theory in great detail. The course was a requirement for my program, and it was one of the few courses that I was not sure at all I’d enjoy. It turned out that many of my friends in Math enjoyed it, but I didn’t. I felt no, or very few connections with Computer Science (later I discovered through friends that if you study advanced complexity theory and theoretical Computer Science it will be very useful), and as a result I started feeling unmotivated.

At some point during the same year I found a book called “Mathematics and Technology” by Christiane Rousseau and Yvan Saint-Aubin. This book was different, extremely refreshing and motivating. Each chapter is a technological problem that has been solved via applied mathematics. For instance, it presents the math behind: the trilateration of the GPS, the motion of a robotic arm in 3D, error correcting codes, public-key cryptography, Google’s PageRank algorithm, why MP3‘s are sampled at 44.1Khz, the JPEG compression standard, the DNA computer (super-cool chapter!), and many other applications. The book is simply a collection of really interesting problems, accompanied by the mathematical background and principles that allow the reader to understand the basic solutions to those problems. It’s not a perfect or comprehensive book by any means, but it is a beautiful one, in the sense that every chapter is a nicely-told story and the provided theory is strongly tied to each application. I think the mathematical maturity it requires is at most that of a 3rd year undergraduate student in math, though I’m sure you could understand most of it with a basic Calculus and Linear Algebra background.

Advertisements

The American Scholar

Richard Hamming’s “You and your research” is an essay that is often recommended reading for graduate students, as a means of advice from an accomplished scientist. I agree with most of the points he raised: work on the important problems in your field, get the courage to try to solve them, be prepared, be patient and positive etc. There is one point that he made though, which has really bothered me from the day I first read the transcription of his speech:

I had incipient ulcers most of the years that I was at Bell Labs. I have since gone off to the Naval Postgraduate School and laid back somewhat, and now my health is much better. But if you want to be a great scientist you’re going to have to put up with stress. You can lead a nice life; you can be a nice guy or you can be a great scientist.

This really doesn’t make much sense to me. Why does willingness to compromise your health make you a more dedicated scientist? Is a sick or dead scientist better than a healthy one? Is constant stress and fear a prerequisite for being productive and creative? I don’t think they are.

I think I prefer Emerson’s “The American Scholar“.

Cool courses

This semester the Computer Science department at McGill is offering a couple of courses for which my friends and I are very excited. The first one is Structure and Dynamics of Networks, which apparently is otherwise known as Network Science, but it really should be called Applied Graph Theory for Large Graphs. Naming aside, the lectures seem to be very promising, as examples will involve networks from different areas, such as biology, political and social science etc.

The second one is Topics in Game Theory, where I believe we’ll study algorithms for selecting strategies to minimize the probability of loss (or maximize the probability of winning) in games where there are many participants. Or at least, that’s what I am expecting — the syllabus doesn’t seem to be posted yet.

Last but not least, the graduate Mobile Robotics class is offered again this year. This course starts with lecture-style material in the first half, during which the students are exposed to motion planning algorithms, sensors, and some fundamental problems in algorithmic robotics. The second half consists of student presentations of research papers. The class is highly interactive and lots of fun.

Don’t skip your guitar lessons

In the beginning of the semester I decided it was time for me to finally take guitar lessons. I had tried in the past to teach myself, but I couldn’t get past the beginner stage. So, when the opportunity arose to take guitar lessons through McGill’s mini courses I seized it and I was really looking forward to them. My instructor was Denis Chang, without a second-thought one of the most talented guitarists and gifted teachers I have ever seen. The man is the ideal teacher: he’s really experienced and knowledgeable, a master in his craft, supportive whenever you need him to be, extremely funny and quite the teaser. Besides, he has some of the coolest guitars I’ve seen. Going to his classes is a real joy. Lessons were held once a week for about two hours and initially there were around ten people registered for the course, but somehow he managed to give individual attention to each of us.

 

During the last three weeks, though, my coursework and the requirements of my research project didn’t allow much time for me to dedicate to my guitar. I had to skip my three last lessons, but I thought that most other students would attend. Today, which was the day of the last lesson, I decided to go meet Denis and tell him that he’s been a great teacher and he’s made me like the instrument much more. I discovered to my surprise (which is why I’m writing this post) that almost everyone in the class had been skipping the last lessons, just like me. I found Denis waiting for his students in the usual room where we practise (in the SSMU building) playing the piano and killing time. After feeling perplexed that I found none of my classmates there, I started feeling angry and disappointed. It was really depressing to see that one of the best teachers I’ve had was receiving this kind of treatment from his students — myself included, of course. He said that it’s OK, that it’s understandable because it’s the last week of classes and everyone is busy with course work, but that didn’t make me feel better at all. It didn’t seem fair to me that he wouldn’t receive an applause on the last lesson like all good teachers do.

 

I really like my coursework this semester, and my working hard is something that just feels right because I enjoy what I’m doing. Yet, this was the first time since I’ve started at McGill that I’ve felt guilty about my efforts. I hope it’s the last. In the meantime, here’s what Denis can do:

 

 

Netflix prize winners at McGill

Almost every Friday at 3pm there is a talk at McGill’s Computer Science department. Today was definitely one of the coolest ones: two members of the team that won the Netflix prize gave a talk on their machine learning techniques. Martin Chabbert and Martin Piotte, graduates of the Ecole Polytechnique de Montreal were members of BellKor Pragmatic Chaos that won the $1 million, 20 minutes before the deadline. Among the most interesting lessons in their fascinating talk, was the fact that at the end they had intelligently combined about 800 predictors using machine learning techniques and clever approximations. However, as they said, it was becoming evident towards the end of the competition that the only way to win, by hitting the mark of 10% improvement on Netflix’s movie recommendation algorithm, was to join forces with other teams, namely BellKor and BigChaos  — explains the weird team name. This meant sharing technical expertise, sharing predictors to be combined in ensemble classification, and of course sharing the money 🙂 Here are the technical documents that explain how they did it: Pragmatic Theory, BigChaos, BellKor.

Affine spaces & projective geometry

What would happen if we took \mathbb {R}^{3} and pretended that we didn’t know where it’s origin was? One of the ramifications would be that points and vectors in that space would have to be considered different entities. When the origin O is fixed and we know it any point P in the space can be represented as the vector OP. This means that when we are working in an affine space (any point can be the origin), points are regarded as fixed locations in space and vectors are regarded as displacements without an origin — two different things.

Formally, an affine space consists of a vector space V and a set of points P such that:

  • if p_1,p_2 \in P then p_1-p_2 \in V
  • if p \in P and v \in V then v+p \in P

So, to specify an affine space we need a basis v_1,v_2 for V (suppose it’s the image plane) and a point p \in P to act as the “unknown” origin. v_1, v_2, p becomes the reference frame of the affine space. As usual, every vector in the affine space can be expressed as {c_1}{v_1}+{c_2}{v_2}+0p, while points are expressed as {a_1}{v_1}+{a_2}{v_2}+1p. In other words, vectors are of the form (c_1, c_2, 0) while points are of the form (a_1, a_2, 1).

Does this remind you of anything? Yup, homogeneous coordinates. I believe this is why my lecture notes mentioned that “(X,Y,Z) is interpreted as a line (vector, horizon) when Z=0 and as a point when Z=1.” It makes much more sense now then back when I first looked at that black magic of a sentence.

OK, so far so good. What really confuses me now, and confused some of my friends when they took the graphics course at UofT, is the question of why is it necessary to use affine spaces & homogeneous coordinates (and thus differentiate between points and vectors) in computer graphics? Why can’t we use our good old euclidean geometry? I believe the answer has to do with the types of transformations that euclidean geometry allows: only rigid-body transformations (i.e. identity, translations and rotations) are allowed and they preserve distances and angles.

Which classes of transformations are missing from that list and might be very useful in computer graphics? Linear transformations (e.g. scaling, reflection and shear), affine transformations (they preserve parallel lines) and projective transformations (artistic perspective). For instance, euclidean geometry says that two parallel lines never meet thus failing to describe perspective and the vanishing point on the horizon:

Projective geometry allows projective transformations such as the above. Euclidean geometry is a subset of affine and that in turn is a subset of projective, with respect to the classes of transformations each one includes. So, I presume that the answer to my question  is that in computer graphics people use projective geometry because it makes the end result much more realistic.

Some links to whet your appetite: #1, #2, #3, #4, #5, #6, #7

Homogeneous coordinates

My first two lectures on computer graphics left me puzzled with some unanswered questions that have to do with basic projective geometry and its transformations. I’ll try to collect my thoughts and some links, and write them down primarily for the sake of summarizing to reduce my own confusion.

Basically, both in computer vision and in computer graphics the first geometric problem that we study is that of projecting points from a 3D scene to a 2D image plane (think of it as a photograph), using the pinhole camera model. The projection looks like this:

An important thing to notice on this picture is that any point that lies on one of the dotted lines will be projected to the same image location. This leads us to write (X,Y,Z)\sim(cX,cY,cZ) for any nonzero c, where (X,Y,Z) is the euclidean coordinate system that we are accustomed to. This “equality” holds in the sense of equivalence classes, not in the sense of euclidean geometry.

Using a similar triangles argument we can prove that the pixel (x,y) on the image is equal to (\frac{X}{Z}f, \frac{Y}{Z}f). However, (x,y) can also be viewed as part of the 3D scene like this (x,y,f)=(\frac{X}{Z}f, \frac{Y}{Z}f, f) \sim (\frac{X}{Z}, \frac{Y}{Z}, 1)\sim(X,Y,Z) provided that f,Z\neq 0. The correspondence between image pixels (x,y) and representatives of the equivalence classes of \sim is one-to-one. The equivalence class corresponding to an image pixel is called the homogeneous coordinates of that pixel. Many of the articles that I found online assumed f=1 for the sake of simplicity and mentioned that the mapping (x,y)\rightarrow(x,y,1) is “just a trick” to be followed blindly because {It Just Works}^\copyright

What happens when Z=0? In that case (X,Y,Z) does not correspond to any point in the euclidean space, but to a unique point-at-infinity along the direction (X,Y). The proof is in the first link.

Here are some of the links that might prove to be helpful for this topic: #1, #2