Publication

An Adaptive Sublinear-Time Block Sparse Fourier Transform

Résumé

The problem of approximately computing the kk dominant Fourier coefficients of a vector XX 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(klognlog(n/k))O(k\log n\log (n/k)) runtime [Hassanieh \emph{et al.}, STOC'12] and O(klogn)O(k\log n) sample complexity [Indyk \emph{et al.}, FOCS'14]. These results are proved using non-adaptive algorithms, and the latter O(klogn)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 Ω((klog(n/k))/loglogn)\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 (k0,k1)(k_0,k_1)-block sparse model. In this model, signal frequencies are clustered in k0k_0 intervals with width k1k_1 in Fourier space, and k=k0k1k= k_0k_1 is the total sparsity. Signals arising in applications are often well approximated by this model with k0kk_0\ll k. Our main result is the first sparse FFT algorithm for (k0,k1)(k_0, k_1)-block sparse signals with a sample complexity of O(k0k1+k0log(1+k0)logn)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 Ω(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(klogn)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 Ω(k0k1lognk0k1)\Omega(k_0k_1\log \frac{n}{k_0k_1}) samples for the (k0,k1(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.

À 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 (35)
Transformation de Fourier rapide
La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n). Ainsi, pour n = , le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD.
Acquisition comprimée
L'acquisition comprimée (en anglais compressed sensing) est une technique permettant de trouver la solution la plus parcimonieuse d'un système linéaire sous-déterminé. Elle englobe non seulement les moyens pour trouver cette solution mais aussi les systèmes linéaires qui sont admissibles. En anglais, elle porte le nom de Compressive sensing, Compressed Sampling ou Sparse Sampling.
Transformation de Fourier discrète
En mathématiques, la transformation de Fourier discrète (TFD) sert à traiter un signal numérique. Elle constitue un équivalent discret (c'est-à-dire pour un signal défini à partir d'un nombre fini d'échantillons) de la transformation de Fourier (continue) utilisée pour traiter un signal analogique. Plus précisément, la TFD est la représentation spectrale discrète dans le domaine des fréquences d'un signal échantillonné. La transformation de Fourier rapide est un algorithme particulier de calcul de la transformation de Fourier discrète.
Afficher plus
Publications associées (54)

An optimal preconditioned FFT-accelerated finite element solver for homogenization

Till Junge, Ali Falsafi, Martin Ladecký

We generalize and provide a linear algebra-based perspective on a finite element (FE) ho-mogenization scheme, pioneered by Schneider et al. (2017)[1] and Leuschner and Fritzen (2018)[2]. The efficiency of the scheme is based on a preconditioned, well-scale ...
ELSEVIER SCIENCE INC2023

pyFFS: A Python Library for Fast Fourier Series Computation and Interpolation with GPU Acceleration

Martin Vetterli, Paul Hurley, Eric Bezzam, Sepand Kashani, Matthieu Martin Jean-André Simeoni

Fourier transforms are an often necessary component in many computational tasks, and can be computed efficiently through the fast Fourier transform (FFT) algorithm. However, many applications involve an underlying continuous signal, and a more natural choi ...
2022

Multiple Line Outage Detection in Power Systems by Sparse Recovery Using Transient Data

Ping Hu, Feng Liu, Li Ding

Fast and accurate transmission line outage detection can help the central control unit to respond rapidly to better maintain the security and reliability of power systems. It is especially critical in the situation of multiple line outages which is more li ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021
Afficher plus
MOOCs associés (11)
Digital Signal Processing [retired]
The course provides a comprehensive overview of digital signal processing theory, covering discrete time, Fourier analysis, filter design, sampling, interpolation and quantization; it also includes a
Digital Signal Processing
Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By rewo
Digital Signal Processing I
Basic signal processing concepts, Fourier analysis and filters. This module can be used as a starting point or a basic refresher in elementary DSP
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.