BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum-inspired low-rank stochastic regression with logarithmic d
 ependence on the dimension - Andras Gilyen\, QuSoft / CWI / University of 
 Amsterdam
DTSTART:20190613T131500Z
DTEND:20190613T141500Z
UID:TALK124123@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:I will present 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 access to input data\, we 
 implement the pseudoinverse of a low-rank matrix and sample from the solut
 ion to the problem Ax=b using fast sampling techniques. We implement the p
 seudo-inverse by finding an approximate singular value decomposition of A 
 via subsampling\, then inverting the singular values. In principle\, the a
 pproach can also be used to apply any desired "smooth" function to the sin
 gular values. Since many quantum algorithms can be expressed as a singular
  value transformation problem\, our result suggests that more low-rank qua
 ntum algorithms can be effectively "dequantised" into classical length-squ
 are sampling algorithms.\n\nJoint work with: Seth Lloyd and Ewin Tang - ht
 tps://arxiv.org/abs/1811.04909
LOCATION:MR13\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR