If you want to encode video to PSP format on Linux install ffmpeg and try this:
ffmpeg -i my_home_movie.mpg -f psp -r 29.97 -b 512k -ar 24000 -ab 64k -s 368x208 my_home_movie.mp4
Or if you prefer the other style you can try this:
ffmpeg -i my_home_movie.mpg -f psp -r 29.97 -b 512k -ar 24000 -ab 64k -s 320x240 my_home_movie.mp4
For me the first option is the best. But naturally its up to your taste as to what you prefer and you can muck about with all of the options but these worked well enough for me.