Reporting FAIL

Ouch - I think I've seen more technically-correct articles in InformationWeek. Picking on the details of DCTs and the like is almost beside the point; this piece was lost well before it tried to offer specifics.

Just who, precisely, believed lossless compression of images was "impossible"? It's trivially true that for any given message longer than one bit, there's at least one encoding that compresses it, though it may expand all other messages. (Encode the target message as a single zero bit; encode all other messages as a one bit followed by the original data verbatim. Implementing the decoder is left as an exercise for the reader.)

Even degenerate cases aside, it's clear that there will often be some redundancy in image and other files that can theoretically be exploited by lossless compressors; and when compressing a set of images, the probability of redundancy increases. This is exploitable in practice using good HMM-based entropy-encoders such as bzip2 and ppmd (the BWT used by bzip2 is effectively a simplified HMM), as one or two commentators have already noted.

Conversely, as other commentators have noted, you can't losslessly compress everything, thanks to the pigeonhole principle. Lossless compression is a question of mapping from the original set of messages to a new set, such that the ones you're interested in tend to be on the short end of the range. Ocarina may have found a practical way to improve that mapping somewhat for the messages their customers are interested in; but they haven't violated some mythical law of compression.