depends on how small the original is, and in what format. In terms of photography you're always gona lose some in a enlargement, but using something like Genuine Fractals will help upscale while making it 'appear' decent.
As a photographer I had to do that a couple of times.