I answered this in your thread on shmups:
Depends on your definition of “cheap”, I suppose. The Extron DSC 301 HD works well–deinterlaces, seems to take any line multiplication method you can throw at it–but you can expect to pay $50~$100 (or more) for one, and you’ll end up with slow resolution transitions (3 sec using the HDMI input, 1 sec using an HDMI to VGA converter and using the analogue input).
You could also try any of the HDMI-to-HDMI scalers on Amazon or eBay, but those all seem to fall into the same price range.
Either way, you’ll be spending less than if you bought a new 4K display.