mobile MAX7219 powering


i want to drive a little LEDmatrix with the MAX7219. Since it's a mobile project I need to power it and the standalone arduino ( with batteries. Since the voltage of the batteries drops over time I need to use a voltage regulator (or maybe you have a solution without one :)). I want to get the maximum lifetime out of the batteries. Which regulator would you recommend? The LT1302 and the MAX 756 look pretty good from my noobieview here :). Any other possible solutions?

I'm going to use 6x4 white LEDs. They suck 20mA. Space for batteries is not (very) limited.