Sunday, March 15, 2015

Finding weighted sums of vectors

Suppose you have a vector that you want to represent as a weighted sum of other vectors. This happens to me all the time. For example, I might have a small part of an image (called a patch), and I want to have a compressed version of it, like when the image gets compressed by JPEG. In that case, the patch is represented as the sum of a bunch of simple patches that look like this:
If I have a simple vertical gradient in the patch, I could give the second basis patch in the first column a weight of 1, and all the others a weight of zero. A more complicated patch would need several of the basis patches to have weights between 0 and 1. But I would almost never need to use any patches except the ones in the upper left hand corner, unless the patch was from a picture of a checkerboard or something.

Another situation where I need to take a weighted sum of a bunch of vectors is in AI programs. Suppose you have a vector that represents an idea, like "childhood," and another vector that represents "old age." Then the vector for "adolesence" would be a sum of the two weighted more heavily toward childhood, and the vector for "adulthood" would be a sum of the two weighted more heavily towards old age.

A third time I needed this was in trying to estimate structure from motion-- trying to guess the shape of an object from the way points on the surface appeared as a camera moved around the object.

Another way of saying it is that I want to represent the vector in a new coordinate system-- a coordinate system whose axes are whatever vectors I choose. Anyway, it's a problem that's come up at least half a dozen times in my career.

If the number of independent vectors you want to sum up exactly matches the number of components in the result, then this problem can be solved by math you might have learned in high school Algebra II. You take all the vectors you want a weighted sum of (call them vec1, vec2, and vec3), and you stack them next to each other to make a matrix (at left.) then you put the goal vector on the right of the equation. The weights are the vector that makes the equation below true:







Weight1 gets applied to vertical vec1, weight2 gets applied to vec2, and so on. This is just a system of linear equations that needs to be solved, and you can do that by taking the inverse of the matrix, and multiplying that inverse by the goal, to get the weights (being careful about left and right multiplication how you do when multiplying by matrices).

The trouble is, you can only take the inverse of a square matrix. In real life, you usually have more or fewer vectors you want to sum than components in the goal vector. If you have too many then they're not going to be independent. If you have too few, the goal vector may not lie in the space spanned by the basis. In that case, you need to do the best you can: get weights so that the weighted sum is as close as possible to the goal vector, but not necessarily exactly equal to it.

Luckily, in 1920, E.H. Moore discovered the right way to do this. In 1955, Roger Penrose independently discovered the same solution, so they call it the "Moore-Penrose pseudoinverse." I don't know much about E.H. Moore, but Roger Penrose is a cool guy. He invented the Penrose aperiodic tiles (he was friends with M.C.Escher), he made up twistors which are the foundation of loop quantum gravity, and he wrote some interesting and controversial books about quantum mechanics in the brain.

I don't really know how the pseudoinverse works-- I learned how to write a program that would converge to the solution in one of my PhD classes, but I've forgotten. But it doesn't matter, you can just use it without knowing how it works. It's very fast in Matlab (it's called 'pinv'), and it gives the weights with no trouble. There's a trick you can do to get non-negative weights, if that's important for your problem (it's called 'lsqnonneg' in Matlab).

Wednesday, January 21, 2015

The Country wherein Art and Science have been Interchanged

In that country, artists play the role of scientists, and natural philosophy is purely the province of the artist. Instead of publishing papers on ways to represent the effect of light on snow in oil paints, each scientist in that country must discover it for himself, or in conversation with friends; and the results are judged largely on popularity among the fashionable, rather than through a rigorous process of review by scientific peers.
Conversely, the artists in that country do not explore their topic of interest (whether it be animals, or weather, or the workings of the mind) through performance and exhibition, but break down art into its simplest components, and publish dry, scholarly missives about some small part of what would more naturally be an artistic whole. Instead of admiring a world-view for its artistic integrity and daring composition, their works are judged solely on technical accuracy. The individual artist generally gains recognition only among other artists in similar fields, and most see their work as part of a much larger collaborative composition.
This has resulted in a strange state of affairs; for their novels are the composition of one author (or at most two) working alone, and each must perform the research needed to build a realistic world on his own. Thus the novels are small, pathetic things, but with a certain charm in their unified viewpoint. Whereas their physics is a vast monstrosity, full of the most carefully checked detail and explored in every ramification, and accurate to the highest degree; but it is a dry thing, and appreciated solely as a tool, rather than for any particular beauty.

Sunday, January 11, 2015

Why Kepler-442b is probably habitable

Last week NASA announced that eight more of the most promising Kepler planetary candidates had been confirmed. The most interesting of these is Kepler-442b. I'll call it 442b for short. It was previously known as KOI-4742.01. The KOI designation includes things that haven't been confirmed as a planet yet.

442b is the only planet in its system we've discovered, though there may be smaller planets or planets with a year longer than 3 years. We wouldn't have been able to detect those other planets in the system, because they haven't crossed their star from our viewpoint yet, and we've only been looking carefully at this star for the past few years. The 'b' designation means it's the first body in the system detected other than the star. The prevailing theory says that it is important for Earthlike planets to have a few gas giants in their system to sweep up asteroids, so that fewer will hit the planet and prevent life from developing, so we'll want to keep watching this star to see if we can see something like Jupiter for that system.

442b orbits an orange star. This is somewhere between a red dwarf star and a yellow star, like our sun. It means the star is smaller and dimmer than the sun. Kepler orbits closer to its star than Earth does to the Sun: its year is only 112.30 days long (this is one value we know very accurately.) This is close enough that the planet gets about two thirds of the amount of sunlight as Earth does. That still seems pretty bad-- Mars gets 44% as much sunlight as Earth does, and it is really cold-- but luckily, 442b is larger than the Earth. Its radius is a third larger than Earth's radius (another value we can measure directly.) Assuming a composition similar to Earth, it would have a mass about 2.3 times that of Earth, and it's surface gravity would be about 1.3 times that of Earth. More gravity means the planet can hold on to a thicker atmosphere, which means greenhouse effects increase the overall heat of the planet. There's a lot of uncertainty in the temperature, so it could be either too cold, too hot, or just right for humans. On the other hand, the poles would be colder and the equator warmer, just like on Earth, so it seems more likely than not there would be somewhere on the planet we could be comfortable. This is why I say 442b is the most interesting of the ones discovered in this batch: there is another planet (Kepler-438b) even closer in size to Earth, but it orbits much closer to its own star, with a year of just 30 days, and since it is larger than Earth and gets more sunlight than Earth, I would expect it to look more like Venus than like Earth. Also, with a 112 day year, you don't have the risk of tidal locking that you did with some of the earlier discovered 'habitable' exoplanets.

On larger worlds, the theory says oceans would tend to take longer to develop, though they would be deeper and last longer.

442b is 1300 light-years away. 

Saturday, September 27, 2014

Life and Machines

I recently read a paper by David Chalmers asking,"Why isn't there more progress in philosophy?" It reminded me of one problem in philosophy that we have pretty much solved: what is the difference between living matter and non-living matter? This was a significant problem for philosophy until the mid-1800s.
There are several differences I can think of:

Living things can move on their own.
Living things can grow.
Living things can reproduce.
Living things can turn food into usable energy.
Living things have purposeful structure down to the microscopic level.
Living things can repair themselves.
Living things can respond to events.
Living things can regulate their internal state.
Living things can communicate.
Living things are optimized for these purposes.

Automata were seen as life-like because they copied the first of these differences, the ability to self-move, and were able to change their behavior at different times.

Later, the ability of engines to "eat" fuel, to regulate themselves with a spinning governor, to respond to changing circumstances, and to communicate their state (for example, with a whistle when the steam is high enough) reminded Samuel Butler of living things, and made the machines more useful.

 The definition of a robot is fuzzy, but it generally means a machine that is more lifelike than the usual sort of machine.

What makes nanotech so useful is that it will be imitating yet more of these properties of life-- reproduction, atomic precision, and self-repair. As we build better and better machines, the gap between living and non-living grows smaller.

One of the most interesting aspects of life is the last on the list-- the purposefulness of its design. When you look at some of the earliest animal life forms, this is less evident. They are more like crystals or simple funguses in their design. Their structures are more dominated by symmetries and repetition and less specialization of parts. Here is Diana Cactiformis, for example, a proto-arthropod:

We now are beginning to understand how purposefulness can be improved through evolution, but there is still a lot to figure out. Why can't we make computer programs that continue to evolve, for example, always getting better and better on their own? Every attempt so far has eventually petered out in its ability to find new solutions.

Sunday, July 20, 2014

harmonograph stereogram

It has been known for over a century that if you adjust the phase slightly on a harmonograph, you can create stereograms. Just allow your eyes to drift or cross slightly so that you see four images, and place two of them on top of each other, so that there are only three. The middle image will be 3D.

Monday, June 16, 2014

The invention of fiction

When you think about it, fiction is a kind of odd concept. The author is telling a lie, and the reader knows it is a lie, but neither one cares. In fact, the book carries a label on it saying "this is a fiction," so no one could accidentally mistake it for the truth. Of course, we're all used to it by now, but there must have been a time when the idea of fiction was invented. People have always told false stories, sometimes outrageous false stories about monsters or magicians, but it used to be the stories were always told as true, perhaps happening in an earlier age when the world was different.
The case of fantastic fiction is what interests me more. With mundane fiction, a story may or may not have happened to some particular person you don't know, but it's easy enough to accept that it might have happened. With fantastic fiction, the rules of the world are different. It is populated by creatures that you have never seen. It takes a real decision to create such an outrageous lie and then tell everyone it is a lie and expect them to still care about it. Doing that must have taken an unusual person, until the world got used to it.
The best person I've ever found to fit this description-- the inventor of extreme fiction (what today might fall in the genres of science fiction and fantasy and magical realism)-- is Lucian of Samosata.
Lucian was born in about 120 AD near the border of Syria and Turkey, and was probably of Semitic heritage. At the time, this was all part of the Roman Empire. He apprenticed to his uncle, the sculptor, but after breaking a pot he decided that making words rather than things was more his line. He traveled widely through the Roman Empire (basically all the countries bordering the Mediterranean in Europe) as a rhetorician, earning his living by giving speeches and as a lawyer. I really get the impression that he lived as an outsider looking in, commenting on the world in ways that made people look at it differently. Maybe a little like Mark Twain, or a stand up comedian.
There are two written works in particular that I find interesting. One of them is called The Liar. It's basically a bunch of guys sitting around telling about incredible things they've seen or heard of. (One of these stories was adapted by Goethe, and (by way of Goethe) Walt Disney, as The Sorcerer's Apprentice.) The narrator is incredulous, wondering, why do people make up these lies? He understands why sometimes people lie to further their own interests. But why tell lies just for the sake of lying? We readers get the satisfaction of feeling smarter than those who believe the story, but the joke is on us, because we are sitting here, reading the lies, because they are just so weird and interesting.
Another, longer work is called A True Story (or, The True History in another translation). It is clearly what we would call science fiction (though the genre wouldn't be invented until the time of Jules Verne and his imitators). Wikipedia lists the following science fiction elements in the story:

  •  travel to outer space
  • encounter with alien life-forms, including the experience of a first encounter event
  • interplanetary warfare and imperialism
  • colonization of planets
  • artificial atmosphere
  • liquid air
  • reflecting telescope
  • motif of giganticism
  • creatures as products of human technology (robot theme)
  • worlds working by a set of alternate 'physical' laws
  • explicit desire of the protagonist for exploration and adventure
In the introduction to the story, Lucian sets out exactly what he is going to do:

"Ctesias,... in his work on India, ... gives details for which he had neither the evidence of his eyes nor of hearsay. Iambulus's Oceanica is full of marvels; the whole thing is a manifest fiction, but at the same time pleasant reading. Many other writers have adopted the same plan, professing to relate their own travels, and describing monstrous beasts, savages, and strange ways of life. The fount and inspiration of their humour is the Homeric Odysseus, entertaining Alcinous's court with his prisoned winds, his men one-eyed or wild or cannibal, his beasts with many heads, and his metamorphosed comrades; the Phaeacians were simple folk, and he fooled them to the top of their bent. 
When I come across a writer of this sort, I do not much mind his lying; the practice is much too well established for that, even with professed philosophers; I am only surprised at his expecting to escape detection. Now I am myself vain enough to cherish the hope of bequeathing something to posterity; I see no reason for resigning my right to that inventive freedom which others enjoy; and, as I have no truth to put on record, having lived a very humdrum life, I fall back on falsehood--but falsehood of a more consistent variety; for I now make the only true statement you are to expect--that I am a liar. This confession is, I consider, a full defence against all imputations. My subject is, then, what I have neither seen, experienced, nor been told, what neither exists nor could conceivably do so. I humbly solicit my readers' incredulity."

This is a remarkable passage. He says, "all these writers have told incredible tales, which are obviously mostly made-up. I'm going to do the same, but I'm going to tell you up front: this is all lies. It's all just for fun, and to make you think." If you're the first person to write fiction, you have to have a paragraph like that, right up front, so that people know what you're doing.

Thursday, May 8, 2014

Hendy's Law

In 1998, Barry Hendy of Kodak Australia pointed out that the number of pixels on a digital camera that you could buy per dollar was growing exponentially. At the time, that would have been about 1000 pixels per dollar. Today, in 2014, you can get roughly 1 million pixels for a dollar (The Vivitar VX137 with a 12.1 megapixel sensor is selling on Amazon Prime for $12.99.) This line has continued exponentially, doubling every 18 months or so, since at least 1994. A camera pixel is a chip component, so you would expect this to track Moore's law more or less. If the trend continues until 2030, you could get a gigapixel for a dollar. At that resolution, you could routinely see the photographer by zooming in on the reflection in the eye of the subject being photographed.

The optics of the Vivitar probably don't support 12.1 megapixels, really-- at 100% zoom level on Photoshop, I expect the image would look very blurry.

Here is a graph Hendy created around 2005. Note that the price is showing only the best deals on pixels per dollar in a new camera at any point in time-- DSLRs have always been more expensive, of course.)