bst-matrix-vector
bst-matrix-vector copied to clipboard
Binary Search Tree sparse matrix and vector
Binary Search Tree matrix and vector classes
This implements the sparse matrix and vector classes mentioned in Ewin Tang's paper A quantum-inspired classical algorithm for recommendation systems. I learned of that paper from a blog post by Scott Aaronson.
The data structures are not original to Tang; apparently they were used earlier by Kerenidis and Prakash.
The vector class supports storing w sparse entries in an n-dimensional space in O(w log^2 n) space, reading/writing in O(log^2 n) time, computing the norm of the vector in O(1) time, and sampling the coordinates of a vector, weighted by the square norm of the entries, in O(log^2 n) time.
The matrix class supports similar operations; see Tang's paper for details.