Filling In the Blanks

The March issue of Wired magazine has an interesting article about a relatively new method of generating high-quality images from relatively low-quality samples.  The technique, known as compressed sensing or compressed sampling, is in some sense an inversion of the more familiar process of data compression.

Data compression is used in a variety of applications to reduce the size of data, in order to achieve lower storage requirements or lower bandwidth requirements.  All compression techniques rely on the fact that almost all “interesting” sets of data are non-random, and have some significant degree of information redundancy, or entropy.  One type of compression, typically used with text, is lossless, meaning that the original data can be reconstructed with complete fidelity from the compressed version.  The “DEFLATE” method, used in compression software like PKZIP and gzip(1), is an example of a lossless compression method.  Lossy compression methods, on the other hand, accept some inaccuracies in reconstructing the data in exchange for more effective compression.  Often, the type of “loss” that is tolerable is dependent on considerations of human perception. For example, the compression of images using the JPEG standard is done using knowledge of what image features are most important to human vision.  Similarly, compression of audio files into MP3 format relies on knowledge of human hearing.  The lossy compression techniques can be quite effective in reducing data size.  The JPEG file delivered by a digital camera may be only 10 % of the size of the raw image.

The compressed sampling technique essentially arises from asking the following question: “Since in the compressed image we have thrown out most of the original data, is there a way that we can skip recording all of the original, and just grab the important parts that we need to save?”    It turns out that the answer to this question is yes.  If we take a selected random sample of pixels in an image, for example, there are mathematical techniques that we can use to generate a much higher quality image, one very similar to what we would have obtained by capturing the whole image in  the first place.  Essentially, this uses the knowledge that the image data has a significant degree of redundancy to drive a linear programming algorithm to construct the most plausible “original”.  (A more technical description is given in this blog post by Terence Tao, one of the pioneers of the technique.)

Applying all of this to your vacation snapshots may seem a bit over the top, like using a hand grenade to kill a mouse.  But there are circumstances where the technique can be very valuable.  One, pointed out in the Wired article, is using the method to reduce the time required to acquire medical diagnostic images, such as MRIs.  In other cases, the sensors may be deployed remotely, on a spacecraft for example.  Reducing the amount of image data that must be acquired can save battery power and bandwidth, both of which may be scarce resources.  Admittedly, there is something about the technique that seems like getting something for nothing, but it’s just really using mathematical tools to take advantage of what we know about the data we’re trying to collect.

Fixing Problems Requires Finding Them

Toyota’s troubles with reported incidents of unintended acceleration, and its ongoing recall of some of its vehicles, have been a staple of news reports for a few weeks now.  But there is an interesting article in today’s edition of the Washington Post that talks about how the engineering challenge that Toyota faces is manifested in an even more difficult communications and public relations problem.  (That Toyota has not handled the problem particularly well is a different issue.)  Some of the problems that have been reported, as the article points out, may well have been due to operator error — what systems support people sometimes call PEBKAC (Problems Exists Between Keyboard And Chair).  But given the number of reports, it seems plausible, at least, that there is some more fundamental problem.

In essence, a significant part of the problem stems from the very considerable complexity of a modern automobile.  Now, I am not an automotive engineer, but I do have some technical background; and the last car I drove regularly that I was reasonably confident that I understood was a 1967 Volkswagen Beetle.  Contemporary cars have substituted electronically-controlled fuel injection, engine timing, throttles, power steering, and lots more for the simple mechanical devices that I sort of understood.  These vehicles contain dozens of microprocessors, each running thousands of lines of software; a typical modern car contains on the order of 20,000 distinct parts.   That all adds up to a lot of places where things can go wrong.

The process of identifying and fixing a car problem today has become like the process of diagnosing other complex systems: the body, in medicine, or a piece of software.  The first challenge is to be able to make the problem occur:

The only way to credibly figure out why something fails is to attempt to duplicate the failure under observable conditions. This is the engineering method.

Even getting to this stage can be very difficult.  Defects may manifest themselves only under specific and unusual circumstances, or may depend on what software engineers call “race conditions”: variations in the precise timing of a series of events.  Realistically, no matter how thoroughly a system may be tested, it is almost impossible to ensure that no such problems remain:

If you put a lot of parts together to form a complex electromechanical machine and make it talk to itself via software, it can behave, sometimes, in ways you cannot anticipate. It can fail for reasons you cannot anticipate.

Anyone who has used a personal computer is familiar with the problem.  It is the reason, for example, that, years after the software was initially released, Microsoft is still fixing bugs in Windows XP.

Toyota has not helped matters by some of its responses to the problem.  It has insisted from the beginning that the problem was due to either badly-fitted floor mats, or to a defect in the accelerator pedal assembly, and has ruled ot any problem with its electronic throttle control.  To me, this has always seemed a bit suspect, since the nature of the problems in some reports made me think immediately of possible software problems when I first heard of the issue.  If the root cause of the problem is in software, it will probably not be easy to find.

In a sense, we have brought problems like this on ourselves.  We want to have incredibly sophisticated technological goodies, which incorporate thousands of components in very complex relationships, packaged so that we can use them without having to understand how they work.  We have the idea that everything can be made simple, if it is just fitted with the right sort of simple interface.  As Neal Stephenson says in his extended essay, In the Beginning Was the Command Line, this idea would seem bizarre in other contexts:

… imagine that book reviews were written according to the same value system that we apply to user interfaces:  “The writing in this book is marvelously simple-minded and glib; the author glosses over complicated subjects and employs facile generalizations in almost every sentence.  Readers rarely have to think, and are spared all the difficulty and tedium typically involved in reading old-fashioned books.”

At this point, it seems safe to say that neither Toyota nor anyone else really knows what is behind all these reported problems.  It would probably be a good thing, though, for everyone to keep in mind that there are hard problems that arise in the real world; and they cannot be made easy be declaring them so.