Mike from Nootropic Design (maker of the delightful Defusable Clock) bought a LED matrix from Adafruit and used it to display video from his Android phone, with the help of a SparkFun IOIO board and an Arduino.
I used the OpenCV library to convert the video frames to 16×32 pixel resolution to match the LED matrix. I also constrained the color space of the frames to 12 bit color. That is, each pixel has 4 bits each for red, green, and blue. That means that each pixel can have 16 different brightness levels of red/green/blue, yielding 4096 possible colors. In other words, all of the image processing is performed on the phone because it’s much more powerful than the Arduino.
See the project page for information on how he did it.