Concept

Basis pursuit

Related publications (77)

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.

Near-Optimal Bayesian Localization via Incoherence and Sparsity

Volkan Cevher

This paper exploits recent developments in sparse approximation and compressive sensing to efficiently perform localization in a sensor network. We introduce a Bayesian framework for the localization problem and provide sparse approximations to its optimal ...

2009

Compressive sensing recovery of spike trains using a structured sparsity model

Volkan Cevher

The theory of Compressive Sensing (CS) exploits a well-known concept used in signal compression – sparsity – to design new, efficient techniques for signal acquisition. CS theory states that for a length-N signal x with sparsity level K, M = O(K log(N/K)) ...

2009

Compressed sensing and redundant dictionaries

Pierre Vandergheynst, Karin Schnass

This article extends the concept of it compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic ...

2008

Dictionary preconditioning for greedy algorithms

Pierre Vandergheynst, Karin Schnass

This article presents an alteration of greedy algorithms like thresholding or (Orthogonal) Matching Pursuit which improves their performance in finding sparse signal representations in redundant dictionaries. These algorithms can be split into a sensing an ...

2008

Matching Pursuit with Block Incoherent Dictionaries

Pierre Vandergheynst, Lorenzo Peotta

There has been an intense activity recently in the field of sparse approximations with redundant dictionaries, largely motivated by the practical performances of algorithms such as Matching Pursuit and Basis Pursuit. However, most of the theoretical result ...

2007

Algorithmic aspects of sparse approximations

Philippe Jost

Typical tasks in signal processing may be done in simpler ways or more efficiently if the signals to analyze are represented in a proper way. This thesis deals with some algorithmic problems related to signal approximation, more precisely, in the novel fie ...

EPFL2007

Algorithms and methods for sparse approximation in structured dictionaries

Lorenzo Peotta

In the last decade we observed an increasing interaction between data compression and sparse signals approximations. Sparse approximations are desirable because they compact the energy of the signals in few elements and correspond to a structural simplific ...

EPFL2007

On the Use of A Priori Information for Sparse Signal Approximations

Pierre Vandergheynst, Lorenzo Granai, Oscar Divorra Escoda

Recent results have underlined the importance of incoherence in redundant dictionaries for a good behavior of decomposition algorithms like Matching and Basis Pursuits. However, appropriate dictionaries for a given application may not necessarily be able t ...

2006

Tree-Based Pursuit: Algorithm and Properties

Pascal Frossard, Pierre Vandergheynst, Philippe Jost

This paper proposes a tree-based pursuit algorithm that efficiently trades off complexity and approximation performance for overcomplete signal expansions. Finding the sparsest representation of a signal using a redundant dictionary is, in general, a NP-Ha ...

2006

On the exponential convergence of Matching Pursuits in quasi-incoherent dictionaries

Pierre Vandergheynst, Rémi Gribonval

The purpose of this paper is to extend results by Villemoes and Temlyakov about exponential convergence of Matching Pursuit with some structured dictionaries for ``simple'' functions in finite or infinite dimension. Our results are based on an extension of ...

2006