Concept

Worst-case complexity

Related publications (60)

Towards a Theory of Robust Localization against Malicious Beacon Nodes

Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious b ...

IEEE Computer Society2008

Fast spin +-2 spherical harmonics transforms and application in cosmology

Pierre Vandergheynst, Yves Wiaux, Laurent Jacques

A fast and exact algorithm is developed for the spin +-2 spherical harmonics transforms on equi-angular pixelizations on the sphere. It is based on the Driscoll and Healy fast scalar spherical harmonics transform. The theoretical exactness of the transform ...

2007

Algorithms for Interface Synthesis

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a software component is a ﬁnite automaton that speciﬁes the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfac ...

Springer2007

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter ...

Spie-Int Soc Optical Engineering, Po Box 10, Bellingham, Wa 98227-0010 Usa2007

Average case analysis of multichannel thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

2007

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latte ...

2007

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding

Suhas Diggavi

We consider multiple description source coding problem with Gaussian source and mean squared error, for

K=3

descriptions. We obtain an outer bound for the rate region of the problem. We also derive an inner bound for the problem based on successively ref ...

2007

On the Cost of Modularity in Atomic Broadcast

André Schiper, Sergio Mena, Nils Richard Ekwall, Olivier Rütti

Modularity is a desirable property of complex software systems, since it simplifies code reuse, verification, maintenance, etc. However, the use of loosely coupled modules introduces a performance overhead. This overhead is often considered negligible, but ...

2007

Multichannel thresholding with sensing dictionaries

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper shows introduces the use sensing dictionaries for p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We do both a worst case and average case recovery analyses of this ...

2007

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.

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

2007

Asymmetric Gaussian Multiple Descriptions and Asymmetric Multilevel Diversity Coding

Suhas Diggavi

We consider multiple description source coding problem with Gaussian source and mean squared error, for

K=3

descriptions. We obtain an outer bound for the rate region of the problem. We also derive an inner bound for the problem based on successively ref ...

2007