In summary, we want to estimate the sum of \(d\)  minimization problems. Even though each of the \(d\)  problems could be solved independently with a linear sketch, we do not want to process \(d\)  linear sketches (as this increases space). In addition, we do not know which of the \(d\)  minimizations will significantly affect the sum; hence, if we only (uniformly) sampled few \(_1, \dots , _t \sim [d]\)  and only processed \(t \ll d\)  sketches along the sampled dimensions, the variance of the estimator may be too large, making it completely useless. The technique we will use was recently developed in [1]}, building on [2]}, [3]}, under the name “\(\ell _p\) -sampling with meta-data.” In this paper, we further develop the ideas, and apply them to sketches for clustering in a simple and modular way. We refer the reader to Remark REF  (following this technical overview), where we expand on the comparison to [1]}.
