I have some data and a method of finding the similarity between any two points, but this method is expensive computationally and I do not need a precise answer as I want to use this matrix for clustering. Are there any known statistical methods for imputing the similarity matrix from a sparse sampling of the similarities?
There are no restrictions on how many I can sample, but the fewer the better. There is also no mandatory method, I am free to sample however I please.
attached is an illustrative example. Ignoring the red cells, how would I impute the white cells given I have a measure of similarity represented by the green cells.