In general it is not possible. Unless you know enough about how the image is supposed to look (on a very small scale) you'll just have to guess about what information is missing. This is very difficult.
Your best bet is to go to the Adobe Photoshop official site HTTP://share.studio.adobe.com and download an action that will give you the best possible enlargements. I forget the name of it but its on about the 5 or 6th page and the description tell you what it is. This ACtion is much better than the normal Photoshop BiCubic interpolation.