This is the core misconception, it's not a naive nearest neighbour search.
That's not how single pixel cameras work at all. They use things like coded aperture masks, structured lighting, and take many samples of a scene to reconstruct any possible high resolution image.