Projections and Projection Matrices

As a simple example we project on to a line. First, calculate \(e\) and \(p\).

\[\begin{align} 0 &= \vec{e} \bullet{}\vec{a} && \vec{e} \perp \vec{a} \text{ so the dot product is zero}\\ 0 &= (\vec{b}-\hat{x}\vec{a})\bullet{}\vec{a} && \text{notice } \vec{e} = \vec{b}-\vec{p} = \vec{b}-\hat{x}\vec{a}\\ 0 &= \vec{b}\bullet \vec{a} - \vec{a} \hat{x}\bullet \vec{a} && \text{distribute } \vec{a}\\ 0 &= (\vec{b} \bullet \vec{a}) - \hat{x} (\vec{a} \bullet \vec{a}) && \text{notice } \hat{x} \text{ is a scalar, so the last term can be } \hat{x} \vec{a} \bullet \vec{a}\\ \hat{x} (\vec{a} \bullet \vec{a}) &= (\vec{b} \bullet \vec{a})\\ \hat{x} &= \dfrac{\vec{b} \bullet \vec{a}}{\vec{a} \bullet \vec{a}} \implies \vec{p} = \dfrac{\vec{b} \bullet \vec{a}}{\vec{a} \bullet \vec{a}} \vec{a} && \text{because } \vec{p} = \hat{x}\vec{a} \end{align}\]

We can summarize the projection to the matrix as, \(\vec{p} = P\vec{b}\). This is easy to find if we present the equation the other way around. Notice that with vectors the order is inconsequential, because \(\vec{a} \bullet \vec{b} = \vec{b} \bullet \vec{a}\)

\[\begin{align} 0 &= \vec{a} \bullet \vec{e} && \vec{a}, \vec{e} \text{ on opposite sides}\\ 0 &= (\vec{a} \bullet \vec{b}) - \hat{x}(\vec{a} \bullet \vec{a})\\ \hat{x}(\vec{a} \bullet \vec{a}) &= (\vec{a} \bullet \vec{b})\\ \hat{x} &= \dfrac{\vec{a} \bullet \vec{b}}{\vec{a} \bullet \vec{b}} = \dfrac{\vec{a}^T\vec{b}}{\vec{a}^T\vec{a}} \end{align}\]

With \(\hat{x}\) in this form, we can calculate the permutation matrix, \(P\) from \(\vec{p} = P\vec{b}\)

\[\begin{align} \vec{p} &= \vec{a}\dfrac{\vec{a}^T\vec{b}}{\vec{a}^T\vec{a}}\\ \vec{p} &= \dfrac{\vec{a}\vec{a}^T}{\vec{a}^T\vec{a}}\vec{b} \implies P = \dfrac{\vec{a}\vec{a}^T}{\vec{a}^T\vec{a}} && \text{because } \vec{p}= P\vec{b} \end{align}\]

Project Onto a Plane in \(\mathbb{R}^3\)

Note that \(\vec{a}^T\vec{a}\) in the denominator evaluates to a scalar. If we want to project onto a plane, the denominator becomes \(A^TA\), which evaluates to a matrix.

  • Division by a matrix has no meaning. You cannot divide by a martix.
  • In arithmatic, we undo multiplication with division.
  • To undo the effects of a matrix multiplication, we multiply the inverse of the matrix. \(A^{-1}A\vec{b}=\vec{b}\)
  • We must re-arrange the equation so that we use inverse matrices instead of division.

We can think of projecting onto a plane as projecting onto multiple vectors. To project \(\vec{b}\) onto \(A\), we are looking for the vector \(\hat{x}\), such that \(\vec{p}=A\hat{x}\), where \(\vec{p}\) is the point on the plane closest to \(\vec{b}\). The first step is to find the vector \(\hat{x}\).

Like the first example, we define the error vector, \(\vec{e}\), as the vector that goes from the plane to \(\vec{b}\)

\[\begin{equation*} \vec{e} = \vec{b} - A\hat{x} \end{equation*}\]

Assume \(A\) is a matrix made of two vectors, \(a_1\) and \(a_2\) in \(\mathbb{R}^3\):

\[\begin{equation} A = \begin{bmatrix} a_{11} & a_{21} \\ a_{12} & a_{22} \\ a_{13} & a_{23} \end{bmatrix} \end{equation}\]

Our error vector, \(\vec{e}\) will be perpendicular to both \(a_1\) and \(a_2\). We want to find the closest point on \(A\) to \(\vec{b}\). Set \(\vec{e}\) and \(\vec{a}\) perpendicular \(0 = \vec{a}_n^T\vec{e}\)

\[\begin{align} 0 &= \vec{a}_1^T(\vec{b} - A\hat{x})\\ 0 &= \vec{a}_2^T(\vec{b} - A\hat{x}) \end{align}\]

There is a simple way to write the equation that captures all components at once.

\(A^T(\vec{b}-A\hat{x})\)

Which can be written as

\(A^T\vec{b} = A^TA\hat{x}\)

Which can be solved for \(\hat{x}\)

\((A^TA)^{-1}A^T\vec{b} = \hat{x}\)

Now that we have the \(\hat{x}\) vector, we can find the projection matrix. Remeber that \(\vec{p} = P\vec{b}\). If we can arrange the equation above correctly, it gives us \(P\).

\(\vec{p} = A\hat{x}\)

Subsitute \(\hat{x}\)

\(\vec{p} = A(A^TA)^{-1}A^T\vec{b}\)

Now the equation is in the form \(\vec{p} = P\vec{b}\), so

\(P = A(A^TA)^{-1}A^T\)

Getting Npm, Anaconda, Jupyter, and Brew to Play Together

I chose to use Anaconda to manage my Python installation in favor of the OSX stock Python 2.7 or brew'd Python. This makes it easy to switch between Python 2 and Python 3, and it works well with Project Jupyter.

I would like to default to Python 3.4.3, because that works best with iPython notebooks in Project Jupyter. But npm packages often use node-gyp to build, and node-gyp is not compatible with Python 3. When I tried to install the npm fsevents package, I got the following error:

gyp ERR! configure error 
gyp ERR! stack Error: Python executable "python" is v3.4.3, which is not supported by gyp.
gyp ERR! stack You can pass the --python switch to point to Python >= v2.5.0 & < 3.0.0.
gyp ERR! stack     at failPythonVersion (/usr/local/lib/node_modules/npm/node_modules/node-gyp/lib/configure.js:108:14)
...

It is possible to specify a python version when npm installing npm install --python=python2.7. We can also configure npm to use a specific version of python (stackoverflow).

$ npm config set python python2.7

This solved the node-gyp problem, but created another problem. By default, npm modules installed with the -g are installed to /usr/local. You can check where global npm modules are stored with

$ npm config get prefix

I usually just use sudo when installing global npm modules in OSX. However, for some reason the when I sudo npm install -g with with npm configured to use Python 2.7, Python ran as a different user without admin privileges, and failed. (Does anyone know why?)

It is safe to use sudo when npm installing, but I would prefer to sudo as little as possible. To solve the problem, I configured npm to install global packages to a directory that does not require admin privileges.

It is not difficult to configure npm to use a custom path for storing global modules (stackoverflow).

$ npm config set prefix '~/.npm-packages'

Then add the following to .bashrc (linux) .bash_profile (osx)

export PATH="$PATH:$HOME/.npm-packages/bin"

This allows us to npm install -g without sudo. It also allows Anaconda to manage python installations, giving us Python 3.4.3 by default in the terminal.

Awareness

In Fall 2014, I took the MIT Media Lab class Principles of Awareness, taught by the Media Lab Director Jio Ito, and Venerable Tenzin Priyadarshi.

Part of this class involved blogging about the topics. I started the blog here, and later picked up at the class blog.

On the conclusion of the class, I wrote this poem about my experiences.

Emperor Moth

Sometimes when I lie awake at night
trying to fall asleep
The cares of a waking human badger my thoughts
I think to myself:
"I am an emperor moth"

And I am the moth
for a moment lightly fluttering
through the evening breeze
the full moon on my wings
reflected in the forest river far below
And I am human again

lying awake and night
a forgotten obligation
Hounded by the cares of a waking human
I think to myself:
"I am a gray wolf"

Far below the moth
I am standing on a hill
I am hungry for my next meal
I am beside my brothers and sisters
To the wolf, thoughts and feelings are the same
An unfulfilled promise has slipped into my mind
and I am human again

The wolf cannot make a promise
but lives for family relations
And the moth never tries to be a moth
only flies toward the light

But I can make or even break a promise
and I can live for my family and my pack
and try to be the moth
And I can fly toward the light

Somewhere between my own restless mind
and the cardinal thoughts of the wolf
I am flying toward the light

Praise for The Name of the Wind

I love escaping into a fantasy world. At best, reading a fantasy novel is a vacation, a waking dream, a story you become a part of. After I finished reading through all 5 books in A Song of Fire and Ice for a second time, I started looking to scratch the Fantasy/SciFi itch. However, I often find fantasy novels frustrating. For example...

  • The Hobbit is amazing, but I've read it 18 times. LOTR is acceptable, but I finished it recently.
  • Neal Stephenson is pretty good, but his stories are about caricatures and ideas, not characters and relationships.
  • The Belgariad series was enjoyable, but felt juvenile - Every Character is obviously either good or bad. Nothing bad ever happens to any of the good characters. The obvious good guys "win" every single encounter.
  • I started Eye of the World on three separate occasions. I could tolerate the campyness, it moved just a little too slowly, and I lost interest every time.

I started reading Wizard's First Rule, the first book in the The Sword of Truth series. But after the first ~5 chapters I gave up, frustrated.

In the best stories, I believe the characters and their actions as much as I believe my own personal relationships. A convincing cast pulls me in to the story better than anything else.

However, most fantasy stories do not have convincing characters. The most offensively unconvincing characters are love interests.

Let me outline the plot at the beginning of Wizard's First Rule...

Our hero lives on the outskirts of a small remote village. While investigating the mysterious sudden murder of his parents, he notices a beautiful female traveler walking in the wilderness alone. He also notices four sinister men who are surreptitiously stalking the traveler. Our hero meets the girl, helps her avoid, and eventually defeat her stalkers.

It turns out that the girl is actually a highly intelligent and powerful magician (not quite powerful enough to defeat the four men by herself), and while she maintains a tough exterior, she has been through traumatizing experiences, and occasionally needs the dependable kindness and emotional support that only our hero can provide. Our hero finds her quite attractive, but comes to consider her his friend, and having a kind and understanding disposition would never try to take advantage of her occasional weakened state.

I am supposed to relate to the main character. This is preying on the fantasy that an attractive and powerful girl will see what a good, wise friend I can be, open up to me for emotional and physical support, eventually leading to romantic, and finally sexual interactions... She comes to me (and only me) and opens herself to me because of my humility, wisdom, patience, and overall goodness. This story that plays out in the first few chapters of Wizard's First Rule is unrealistic and aggravating. It's an angle that's overused and abused. I suspect it's also alienating to non-male readers.

Why is this same story played out in so many other fantasy novels? As I was approaching the last chapter of Hyperion, I thought the story would finish inoffensively, but then the conclusion of the entire story depended completely on an improbable and unconvincing love story not at unlike the one in Wizard's First Rule.

I concede that not every story needs to be written for all genders. They are fantasy novels after all. Romance novels (for example) are often written and marketed to a female audience. I imagine unrealistic male love interests are common in romance novels.

I've been reading The Name of the Wind by Patrick Rothfuss. It's wonderful. It's imperfect. It's like being in the other world. It's like being drunk. While I'm reading, the current world ceases to exist. I stop noticing words on the page, and the world in the story materializes in front of me. Best of all, this is a novel that gets the love story right. How? Well, the relationship is dysfunctional, doomed, and convincing. The protagonist is in his early teens, awkward, crushed, and incompetent. There are specific things he does that I relate to doing when I was his age, or in my first relationship. Awkwardness, competing interests, and ignored instincts all get in the way of the relationship. Perhaps it's because I've been there that I relate to it so strongly. Perhaps nearly everyone has.

I am optimistic there are more fantasy novels like this one out there waiting to be read.

Connect Handler Example for Simple CORS Requests

For reference, I'm recording an example of handling Simple CORS Requests with some handy connect/express implementation details.

Remember when using webapp.use() with a path as the first argument:

  • All sub-paths of that path are also handled
  • The specified path is striped from the beginning req.url inside request handlers

Notes about the req parameter to request handlers:

  • req objects are instances of node's http.IncomingMessage
  • Your framework may build on top of the IncomingMessage interface. For example, express adds the param method
// hosts whitelist
var coorsAccessOrigins = {
  'http://localhost:3000': true,
  'http://example.com': true,
  'http://charlesholbrow.com': true,
  'http://www.charlesholbrow.com': true
};

// allow simple CORS GET requests to the /dds directory
webApp.use('/dds', function(req, res, next){
  // Don't add access control headers if host is not in whitelist
  if (!coorsAccessOrigins[req.headers.origin]) return next();

  // The origin header implies this is a CORS request.
  // The user-agent (the browser) is unlikely to add the origin
  // header if it doesn't support CORS
  if (!req.headers.origin) return next();

  res.setHeader('Access-Control-Allow-Origin', req.headers.origin);
  res.setHeader('Access-Control-Allow-Methods', 'GET');
  return next();
});

Notice the difference between the origin request header and the host request header.

  • The host request-header specifies the Internet host and port number of the resource being requested
  • The origin request-header indicates that this is a CORS request
// example req.headers object
{
  "host": "localhost:3000",
  "connection": "keep-alive",
  "cache-control": "no-cache",
  "pragma": "no-cache",
  "origin": "http://charles.meteor.com",
  "user-agent": "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_8_5) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/35.0.1916.153 Safari/537.36",
  "accept": "*/*",
  "dnt": "1",
  "referer": "http://charles.meteor.com/",
  "accept-encoding": "gzip,deflate,sdch",
  "accept-language": "en-US,en;q=0.8",
  "x-forwarded-for": "127.0.0.1",
  "x-forwarded-port": "3000",
  "x-forwarded-proto": "http"
}

Cross-Origin Resource Sharing and JSONP: A Simple Explanation

If you are browsing farmville.com and a script downloaded makes an ajax request to facebook.com, this is known as cross-origin resource sharing, or CORS.

When a modern browser encounters a CORS request, it intervenes for security reasons. Browsers distinguish Simple Requests from Non-Simple Requests using a different intervention strategy for each.

Simple Requests

An HTTP request is considered simple if all 3 criteria are met:

  1. The request method is GET, HEAD or POST
  2. the request uses only headers in the following list:
  • Accept
  • Accept-Language
  • Content-Type
  • Content-Language
  1. The value field of the Content-Type header matches one of the following:
  • application/x-www-form-urlencoded
  • multipart/form-data
  • text/plain

For simple requests, the browser adds the Origin header behind the scenes. The request received by our server might look like this:

GET /some/resource
Host: bar.other
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) Gecko/20081130 Minefield/3.1b3pre
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: en-us,en;q=0.5
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Origin: http://foo.example

The server observes the Origin header, and serves back a response. The browser inspects the HTTP Response and looks for the Access-Control-Allow-Origin header.

Access-Control-Allow-Origin: http://bar.example.com

In the example above, the server is indicating that only requests originating from http://bar.example.com are permitted to access the resource. The browser will discard the data in the http response, and throw a JavaScript error indicating that the AJAX request was unsuccessful. Note that wild cards can also be used for the value of Access-Control-Allow-Origin. In the next example, the server is indicating that requests from any origin may be permitted to access the response.

Access-Control-Allow-Origin: *

The Access Control headers hidden from the JavaScript API - they are removed be the browser before exposing the HTTP Response to your JavaScript code.

Non-Simple Requests

For non simple HTTP Requests, the browser employs a different security strategy. Instead of sending an ajax request directly to the other server, it first sends an OPTIONS http request. The headers in the response to the OPTIONS request indicate to the browser if the server is willing to listen to requests originating from other servers.

In our example, facebook.com needs to be configured to respond to OPTIONS requests with a specific header format. These headers indicate to the browser which domains are allowed to make resource requests.

CORS is the modern way to make cross-origin requests -- It's not supported by IE 7 and below. JSONP is another option for making cross origin requests.

JSONP exploits the fact that <script> elements are allowed to make cross-origin GET requests to retrieve script files. A server can return an html document containing a script tag with a cross origin src='www.example.com' attribute. The browser will not interfere with this request.

<script>
var myFunc = function(data){
  console.log(data);
};

// append a script tag to the document. This will trigger a cross-origin GET request.
document.write("<script src='http://facebook.com/example/api/callback=myFunc'>")
</script>

The script returned by Facebook's executes a function that we (hopefully) defined prior to making the request.

// example script returned and run by dynamically adding a script tag
myFunc({
  name: 'Charles',
  id: '123456'
});