Upscaling 1080p Footage to 4k

There are several good algorithms based on teaching artificial intelligence, but they are not for the Adobe Premiere.

Throw me a video, I'll process it.

I really want a good upscaling algorithm as well. I know that sub pixel motion data can be used to estimate finer resolution data, I wish that AE would take this into account when upscaling.

There are a ton of methodologies to employ to "Upscale"; most include adding noise through your Video editor app.  Those don't necessarily help much.  May I assume you'd like to keep at least some of your fine details, even if medium or soft details blur (don't worry about answering, it's rhetorical, as this is the basic method of video compression limited to a single frame context; you'll understand in a moment)?

Video is about frames, which are just photographs.  Lets work with it in this style, shall we?  You'll see why soon.  First, you'll want to render just a single clear frame to an image, and open it in photoshop.  (Huh?)  Yeah, photoshop.  Now lets experiment with this... ...I've found that you can actually define and sharpen edge detail using an edge mask that you overlay as a layer.  This mask, when vectorized can be blown up, blurred slightly, and then overlayed on a blown up image to add some edge detail and finer details in other areas.  How do I make the mask?  There are a lot of methods for turning a photo into a sketch, look them up, experiment a little.  Once you have a basic method down, you want to write it down, so print your history.  At the end you'll want to make the sketch into a black and white image, darken the outlines with one swipe of a large brush burn, then vectorize it.  You'll want to get all this into your history, then circle the good stuff that worked well, and start over.  (WHAT!?) Yeah, you have to start over so you can record this to an action.  Start your recording with all the files closed but the photoshop environment open, and open your file (this is important so don't forget it, it creates the cycle), now you can go through, following your history and do it all again, then vectorize the final image and save it to a folder anywhere but your final one.  Close the file, stop the recording.

Now we move to AE and render out a folder of images (you'll need a big hard drive for this; about 500gb per hour with jpegs), once finished, back to photoshop and in the automation menu under file, you can have the entire folder input through the action to create vectorized masks.  Now you simply create an action that upscales the vector, and then blurs it 2 pixels or so for each blow up.  To 4k, you should blur 8pixels to feather the mask a bit, save the file in place.

Back in AE, you'll take your folder of images and set them up as a 4k comp, they should look smoother and blurred.  Now overlay the image folder of your vector masks in Luminance blend mode or multiply, and see what you get.  You can set the opacity to adjust the effect, then apply your comp into a Premiere sequence.  You may want to add some noise or grain with an effect in AE.  Ta-da, you're done.

Some sequences work better with the blow up after the effects are applied, but most do better before you apply your effects.  Things look cleaner.

Sometimes using a Blow up effect first, before applying the vector mask can get even better results.

It's a longer method, but it gets great results, even at lower bitrates.

Bitrates:

I like to upload at 10-15mb\s because most cheap internet providers run at that speed, limiting the need for long buffering.  Youtube limits 4k to about 35-40mb\s, which is what most cable\optical connections are capable of.  Try making two comps, one with and one without your vector mask, see which looks better.  With more motion, this method gets a bit funky, and you may have to adjust some areas a bit by creating new masks when the motion increases for sustained periods (sports and such).

Another adjusted method is to use highpass filters or the unsharp masking method.  Unsharp mask the photo to sharpen the edges, then set it over itself in Difference mode.  Invert that, make it black and white, and run this vector masking.  It picks up finer edge detail and other noise detail that can be scaled.

IF you have areas of high motion that look weird, find out what frame, then move the vectors to a new folder, open each one, and lighten the areas where the motion is happening, to about a 50%grey.  This will keep the detail but lighter, and smoother.  Usually this fixes the problem in your video, so you can save and move the files back into place.  When you are done, just drop back into AE, then into premiere.

If you don't have access to all these apps with your subscription, look for an effect that will "Sketch" the video, turn that black and white.  Set higher contrast, output that to a folder of images in a vector format, then overlay that on top of a sequence set to 4k, blur it and set it's blend mode to Luminance.  It won't look as good as the full method, but it does remarkably well in a pinch.

If you use Premiere Pro or After Effects there is a plugin for that:

Red Giant | Instant 4K

You can't add pixels where they don't exist, Peter.

If you're taking 1920x1080 pixels and blowing it out to 3840x2160 pixels, it's going to look blurry! You're going from about 2 million pixels to over 8 million. That's stretching it to four times its size!