Publication

Sketches, metrics and fast algorithms

Related publications (45)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Density Estimation In Rkhs With Application To Korobov Spaces In High Dimensions

Fabio Nobile, Yoshihito Kazashi

A kernel method for estimating a probability density function from an independent and identically distributed sample drawn from such density is presented. Our estimator is a linear combination of kernel functions, the coefficients of which are determined b ...

SIAM PUBLICATIONS2023

Cluster-and-Conquer: When Randomness Meets Graph Locality

Anne-Marie Kermarrec, Olivier Ruas

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

Kernel Density Estimation through Density Constrained Near Neighbor Search

Mikhail Kapralov, Navid Nouri

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1 + epsilon)-approximation to mu := ...

IEEE2020

Scalable and Efficient Comparison-based Search without Features

Matthias Grossglauser, Lucas Maystre, Daniyar Chumbalov

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generate ...

2020

Particle number control for direct simulation Monte-Carlo methodology using kernel estimates

The efficiency of stochastic particle schemes for large scale simulations relies on the ability to preserve a uniform distribution of particles in the whole physical domain. While simple particle split and merge algorithms have been considered previously, ...

2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

Kernel Regression for Graph Signal Prediction in Presence of Sparse Noise

Pascal Frossard, Arun Venkitaraman

In presence of sparse noise we propose kernel regression for predicting output vectors which are smooth over a given graph. Sparse noise models the training outputs being corrupted either with missing samples or large perturbations. The presence of sparse ...

IEEE2019

Covering convex bodies and the Closest Vector Problem

Moritz Andreas Venzin, Márton Naszódi

We present faster algorithms for the approximate Closest Vector Problem under l_p norms ...

2019

When Stuck, Flip a Coin

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Learning heat diffusion graphs

Pascal Frossard, Daniel Kressner, Xiaowen Dong

Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined ...

Ieee-Inst Electrical Electronics Engineers Inc2017