Average-Distortion Sketching

Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…