3 papers
cs.DS2018
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
András Gilyén, Seth Lloyd, Ewin Tang
We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling…
cs.IR2018
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang
We give a classical analogue to Kerenidis and Prakash's quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups i…
math.CO2017
Factorizations of -Nonnegative Matrices
Sunita Chepuri, Neeraja Kulkarni, Joe Suk +1
A matrix is -nonnegative if all its minors of size or less are nonnegative. We give a parametrized set of generators and relations for the semigroup of -nonnegative $n\ti…