5 papers
A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings
Lorenzo Beretta, Cameron Musco
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mat…
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram +1
We give a reduction from -approximate Earth Mover's Distance (EMD) to -approximate Closest Pair (CP). As a consequence, we improve the fastest kno…
Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri
We revisit the problem of designing sublinear algorithms for estimating the average degree of an -vertex graph. The standard access model for graphs allows for the following que…
Sketched Lanczos uncertainty score: a low-memory summary of the Fisher information
Marco Miani, Lorenzo Beretta, Søren Hauberg
Current uncertainty quantification is memory and compute expensive, which hinders practical uptake. To counter, we develop Sketched Lanczos Uncertainty (SLU): an architecture-agnos…
Multi-Swap -Means++
Lorenzo Beretta, Vincent Cohen-Addad, Silvio Lattanzi +1
The -means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is often the practitioners' choice algorithm for optimizing the popular -means clustering objective and is know…