Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Publication

Efficiently Learning Fourier Sparse Set Functions

Mikhail Kapralov, Andreas Krause, Amir Zandieh
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS), 2019
Article de conférence

Résumé

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 set of size n and that are sparse (say k-sparse) in the Fourier domain. This is a wide class, that includes graph and hypergraph cut functions, decision trees and more. Our central contribution is the first algorithm that allows learning functions whose Fourier support only contains low degree (say degree d = o(n)) polynomials using O(kd log n) sample complexity and runtime O(kn log(2) k log n log d). This implies that sparse graphs with k edges can, for the first time, be learned from O(k log n) observations of cut values and in linear time in the number of vertices. Our algorithm can also efficiently learn (sums of) decision trees of small depth. The algorithm exploits techniques from the sparse Fourier transform literature and is easily implementable. Lastly, we also develop an efficient robust version of our algorithm and prove l(2)/l(2) approximation guarantees without any statistical assumptions on the noise.

Official source

https://infoscience.epfl.ch/record/278545?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

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 range, a small number of frequencies, or a few blocks of frequencies i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.

ASSOC COMPUTING MACHINERY2019

Chargement

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 algorithms with

O(k\log n\log (n/k))

runtime [Hassanieh \emph{et al.}, STOC'12] and

O(k\log n)

sample complexity [Indyk \emph{et al.}, FOCS'14]. These results are proved using non-adaptive algorithms, and the latter

O(k\log n)

sample complexity result is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use

\Omega((k\log(n/k))/\log\log n)

samples [Hassanieh \emph{et al.}, STOC'12]. By {\em adaptive}, we mean being able to exploit previous samples in guiding the selection of further samples. This paper revisits the sparse FFT problem with the added twist that the sparse coefficients approximately obey a

(k_0,k_1)

-block sparse model. In this model, signal frequencies are clustered in

k_0

intervals with width

k_1

in Fourier space, and

k= k_0k_1

is the total sparsity. Signals arising in applications are often well approximated by this model with

k_0\ll k

. Our main result is the first sparse FFT algorithm for

(k_0, k_1)

-block sparse signals with a sample complexity of

O^*(k_0k_1 + k_0\log(1+ k_0)\log n)

at constant signal-to-noise ratios, and sublinear runtime. A similar sample complexity was previously achieved in the works on {\em model-based compressive sensing} using random Gaussian measurements, but used

\Omega(n)

runtime. To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the

O(k\log n)

sample complexity bound. Interestingly, the aforementioned model-based compressive sensing result that relies on Gaussian measurements is non-adaptive, whereas our algorithm crucially uses {\em adaptivity} to achieve the improved sample complexity bound. We prove that adaptivity is in fact necessary in the Fourier setting: Any {\em non-adaptive} algorithm must use

\Omega(k_0k_1\log \frac{n}{k_0k_1})

samples for the

(k_0,k_1

)-block sparse model, ruling out improvements over the vanilla sparsity assumption. Our main technical innovation for adaptivity is a new randomized energy-based importance sampling technique that may be of independent interest.

2017

Chargement

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. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Chargement

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Mikhail Kapralov, Amir Zandieh

ASSOC COMPUTING MACHINERY2019

EPFL2019

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 algorithms with

O(k\log n\log (n/k))

runtime [Hassanieh \emph{et al.}, STOC'12] and

O(k\log n)

sample complexity [Indyk \emph{et al.}, FOCS'14]. These results are proved using non-adaptive algorithms, and the latter

O(k\log n)

sample complexity result is essentially the best possible under the sparsity assumption alone: It is known that even adaptive algorithms must use

\Omega((k\log(n/k))/\log\log n)

(k_0,k_1)

-block sparse model. In this model, signal frequencies are clustered in

k_0

intervals with width

k_1

in Fourier space, and

k= k_0k_1

is the total sparsity. Signals arising in applications are often well approximated by this model with

k_0\ll k

. Our main result is the first sparse FFT algorithm for

(k_0, k_1)

-block sparse signals with a sample complexity of

O^*(k_0k_1 + k_0\log(1+ k_0)\log n)

\Omega(n)

runtime. To the best of our knowledge, our result is the first sublinear-time algorithm for model based compressed sensing, and the first sparse FFT result that goes below the

O(k\log n)

\Omega(k_0k_1\log \frac{n}{k_0k_1})

samples for the

(k_0,k_1

2017