Fast Linear Algebra for Distance Matrices @GoogleTechTalks
Fast Linear Algebra for Distance Matrices  @GoogleTechTalks
Uploaded July 2022 | Updated November 2026, 6 days ago
A Google TechTalk, presented by Sandeep Silwal, 2022/06/21
ABSTRACT: I will talk about some of my recent work on fast algorithms for linear algebraic primitives tailored for distance matrices, a common family of dense matrices arising in many applications. The main upper bound results are linear time algorithms for computing matrix-vector products for some distance functions, including the L1 metric, which only use the underlying dataset, rather than constructing the distance matrix. Efficient matrix-vector products automatically have many downstream applications (think power method or iterative methods), and many recent works have nailed down the complexity of various linear algebraic tasks, such as low-rank approximation, in terms of the number of matrix-vector queries required. The upper bound results are complemented by lower bounds, including a conditional Omega(n^2) lower bound for any algorithm which computes a matrix-vector product for the L_infinity distance matrix on a set of n points, showing a separation between the L1 and L_infinity cases. Time permitting, I will also talk about constructing approximate L2 distance matrices in time faster than the bound implied by the Johnson-Lindenstrauss lemma. This is joint work with Piotr Indyk.

Presented as part of the Google Algorithms, Theory, and Optimization speaker series.

About the Speaker: Sandeep is now a 4th year PhD student at MIT working with Piotr Indyk. He seeks to work in the 'sweet spot' between theory and practice. Recently he has been working in the intersection of ML and classical algorithms to design efficient algorithms for large datasets, as well as using ML to inspire algorithm design.
Fast Linear Algebra for Distance MatricesOn Privacy Implications of Machine UnlearningUnderstanding and Mitigating Copying in Diffusion ModelsPOPri: Private Federated Learning using Preference-Optimized Synthetic Data2023 Blockly Developer Summit Day 2-8: Active STEM with Unruly SplatsGo Meetup April 2025 - Git Bisect and Go Size AnalyzerZürich Go Meetup: Run Go programs on your Raspberry Pi with gokrazy!Leveraging Per-Instance Privacy for Machine Unlearning2023 Blockly Developer Summit Day 2-2: Blockly Themes for AccessibilityGoing Back and Beyond: Emerging (Old) Threats in LLM Privacy and PoisoningWhat Makes Software Work?Introduction to Length-Constrained Expanders and Expander Decompositions
Google TechTalks |

Fast Linear Algebra for Distance Matrices

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER