Publications by Amir Zandieh | EPFL Graph Search

Fourier Sampling in Signal Processing and Numerical Linear Algebra

This thesis focuses on developing efficient algorithmic tools for processing large datasets. In many modern data analysis tasks, the sheer volume of available datasets far outstrips our abilities to process them. This scenario commonly arises in tasks incl ...

EPFL2020

Oblivious Sketching of High-Degree Polynomial Kernels

Mikhail Kapralov, Amir Zandieh

Kernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalabili ...

ASSOC COMPUTING MACHINERY2020

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Mikhail Kapralov, Amir Zandieh, Navid Nouri

Random binning features, introduced in the seminal paper of Rahimi and Recht '07, are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way to approximate the ...

ADDISON-WESLEY PUBL CO2020

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Mikhail Kapralov, Amir Zandieh

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple" Fourier structure - e.g., those involving frequencies within a bounded r ...

ASSOC COMPUTING MACHINERY2019

Efficiently Learning Fourier Sparse Set Functions

Andreas Krause, Mikhail Kapralov, Amir Zandieh

Learning set functions is a key challenge arising in many domains, ranging from sketching graphs to black-box optimization with discrete parameters. In this paper we consider the problem of efficiently learning set functions that are defined over a ground ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019

An Adaptive Sublinear-Time Block Sparse Fourier Transform

Volkan Cevher, Mikhail Kapralov, Jonathan Mark Scarlett, Amir Zandieh

The problem of approximately computing the

k

dominant Fourier coefficients of a vector

X

quickly, and using few samples in time domain, is known as the Sparse Fourier Transform (sparse FFT) problem. A long line of work on the sparse FFT has resulted in ...

2017

Amir Zandieh

Graph Chatbot

Chat with Graph Search

Fourier Sampling in Signal Processing and Numerical Linear Algebra

Oblivious Sketching of High-Degree Polynomial Kernels

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Efficiently Learning Fourier Sparse Set Functions

An Adaptive Sublinear-Time Block Sparse Fourier Transform

Fourier Sampling in Signal Processing and Numerical Linear Algebra

Efficiently Learning Fourier Sparse Set Functions

Scaling up Kernel Ridge Regression via Locality Sensitive Hashing

Oblivious Sketching of High-Degree Polynomial Kernels

An Adaptive Sublinear-Time Block Sparse Fourier Transform

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms