How to express one image in terms of another one
I found an answer which is good-enough for me. As @Stanley Pawlukiewicz has pointed out in the comments, this is hard to do for a general case when there is little correlation between the images. I, however, want to work with real images of actual things in the real world. This means there will be a lot of low frequency components (that's why jpeg compression works). If I now formulate the problem as:
$$
I = U_{s} S  V_{s}'
$$
where $I$ is the matrix representing the image, $U_{s}$ and $V_{s}$ are the matrices of the svd decomposition of the source image, and we are trying to find $S$. Then, the inverse problem (which is the one we actually want to solve) is:
$$
S = U_{s}^{-1}I(V_{s}')^{-1}
$$
This is the easy part (using Matlab, python or otherwise).

I then took a good look at how are the solutions ($S$) to this problem are distributed, and they tend to cluster around the left and upper edge of the S matrix. Therefore, I can approximate S by the subset of S centered around these values. I (slightly arbitrarily) have chosen to use a quarter of a superellipse to set the cutoff value with a nice constant to play with. I can get S down to 10% of its elements and retain most of the broad features of the image, which is all I wanted.

I've put my code up online so you can check it out. Hope this helps someone. :)