The above assumption actually is empirical. Frieze et al. [1]} used these similar assumptions to present a sublinear algorithm for seeking low rank approximation. In [2]}, Tang also give a quantum-inspired classical algorithm for recommendation systems by using these similar assumptions. As pointed out in [3]}, [4]}, [5]}, [6]}, there is a low-overhead data structure that satisfies the sampling assumption.
We first describe the data structure for a vector, then a matrix.
