Publications related to Basis pursuit

Sparsest piecewise-linear regression of one-dimensional data

Michaël Unser, Julien René Pierre Fageot, Thomas Jean Debarre, Quentin Alain Denoyelle

We study the problem of one-dimensional regression of data points with total-variation (TV) regularization (in the sense of measures) on the second derivative, which is known to promote piecewise-linear solutions with few knots. While there are efficient a ...

Elsevier2021

The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy

Emmanuel Emilien Louis Soubies, Quentin Alain Denoyelle, Gabriel Peyré

This paper showcases the theoretical and numerical performance of the Sliding Frank-Wolfe, which is a novel optimization algorithm to solve the BLASSO sparse spikes super-resolution problem. The BLASSO is a continuous (i.e. off-the-grid or grid-less) count ...

2020

The Sliding Frank-Wolfe Algorithm for the BLASSO

Emmanuel Emilien Louis Soubies, Quentin Alain Denoyelle, Gabriel Peyré

This paper showcases the Sliding Frank-Wolfe (SFW), which is a novel optimization algorithm to solve the BLASSO sparse spikes super-resolution problem. The BLASSO is the continuous (i.e. off-thegrid or grid-less) counterpart of the well-known `1 sparse reg ...

2019

On Matching Pursuit and Coordinate Descent

Martin Jaggi, Sebastian Urban Stich, Sai Praneeth Reddy Karimireddy, Anant Raj

Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers ...

2018

Low Frequency Sound Field Reconstruction in Non-rectangular Room: A Numerical Validation

Hervé Lissek, Etienne Thierry Jean-Luc Rivet, Vu Thach Pham

Characterization of sound fields in rooms has always been a challenging task. A faithful reconstruction of sound fields in rooms generally would require an impractically high number of microphones. At low frequencies, where sound field can be modeled as a ...

2018

Smoothing technique for nonsmooth composite minimization with linear operator

Volkan Cevher, Van Quang Nguyen

We introduce and analyze an algorithm for the minimization of convex functions that are the sum of differentiable terms and proximable terms composed with linear operators. The method builds upon the recently developed smoothed gap technique. In addition t ...

2017

Learning Data Triage: Linear Decoding Works for Compressive MRI

Volkan Cevher, Yen-Huan Li

The standard approach to compressive sampling considers recovering an unknown deterministic signal with certain known structure, and designing the sub-sampling pattern and recovery algorithm based on the known structure. This approach requires looking for ...

Ieee2016

Convex Optimization Approaches for Blind Sensor Calibration using Sparsity

Rémi Gribonval, Gilles Puy

We investigate a compressive sensing framework in which the sensors introduce a distortion to the measurements in the form of unknown gains. We focus on blind calibration, using measures performed on multiple unknown (but sparse) signals and formulate the ...

Institute of Electrical and Electronics Engineers2014

Metric Learning with Rank and Sparsity Constraints

Volkan Cevher, Baran Gözcü, Bubacarr Bah

Choosing a distance preserving measure or metric is fun- damental to many signal processing algorithms, such as k- means, nearest neighbor searches, hashing, and compressive sensing. In virtually all these applications, the efficiency of the signal process ...

Ieee2014

Sparse Approximation Using M-Term Pursuit and Application in Image and Video Coding

Pascal Frossard, Pierre Vandergheynst, Adel Rahmoune

This paper introduces a novel algorithm for sparse approximation in redundant dictionaries called the M-term pursuit (MTP). This algorithm decomposes a signal into a linear combination of atoms that are selected in order to represent the main signal compon ...

Institute of Electrical and Electronics Engineers2012

Distributed Representation of Geometrically Correlated Images with Compressed Linear Measurements

Pascal Frossard, Vijayaraghavan Thirumalai

The distributed representation of correlated images is an important challenge in applications such as multi-view imaging in camera networks or low complexity video coding. This paper addresses the problem of distributed coding of images whose correlation i ...

Institute of Electrical and Electronics Engineers2012

Fast orthogonal sparse approximation algorithms over local dictionaries

Pierre Vandergheynst, Rémi Gribonval

In this work we present a new greedy algorithm for sparse approximation called LocOMP. LocOMP is meant to be run on local dictionaries made of atoms with much shorter supports than the signal length. This notably encompasses shift-invariant dictionaries an ...

2011

Compressive sensing meets game theory

Volkan Cevher, Sina Jafarpour

We introduce the Multiplicative Update Selector and Estimator (MUSE) algorithm for sparse approximation in under-determined linear regression problems. Given ƒ = Φα* + μ, the MUSE provably and efficiently finds a k-sparse vector α̂ such that ∥Φα̂ − ƒ∥∞ ≤ ∥ ...

IEEE2011

Spread spectrum for compressed sensing techniques in magnetic resonance imaging

Jean-Philippe Thiran, Rolf Gruetter, Pierre Vandergheynst, Dimitri Nestor Alice Van De Ville, Yves Wiaux, Gilles Puy

Magnetic resonance imaging (MRI) probes signals through Fourier measurements. Accelerating the acquisition process is of major interest for various MRI applications. The recent theory of compressed sensing shows that sparse or compressible signals may be r ...

IEEE Signal Process. Soc.2010

Compressed sensing for radio interferometry: spread spectrum imaging techniques

Pierre Vandergheynst, Yves Wiaux, Gilles Puy

We consider the problem of reconstruction of astrophysical signals probed by radio interferometers with baselines bearing a non-negligible component in the pointing direction. The visibilities measured essentially identify with a noisy and incomplete Fouri ...

2009

A low complexity orthogonal matching pursuit for sparse signal approximation with shift-invariant dictionaries

Pierre Vandergheynst, Rémi Gribonval

We propose a variant of Orthogonal Matching Pursuit (OMP), called LoCOMP, for scalable sparse signal approximation. The algorithm is designed for shift- invariant signal dictionaries with localized atoms, such as time-frequency dictionaries, and achieves a ...

2009

Sparsity & [and] dictionaries - algorithms & [and] design

Karin Schnass

With the flood of information available today the question how to deal with high dimensional data/signals, which are cumbersome to handle, to calculate with and to store, is highly important. One approach to reducing this flood is to find sparse signal rep ...

EPFL2009

Geometric Video Approximation Using Weighted Matching Pursuit

Michel Bierlaire, Pierre Vandergheynst, Gianluca Monaci, Oscar Divorra Escoda

In recent years, many works on geometric image representation have appeared in the literature. Geometric video representation has not received such an important attention so far, and only some initial works in the area have been presented. Works on geometr ...

2009

On unifying sparsity and geometry for image-based 3D scene representation

Ivana Tosic

Demand has emerged for next generation visual technologies that go beyond conventional 2D imaging. Such technologies should capture and communicate all perceptually relevant three-dimensional information about an environment to a distant observer, providin ...

EPFL2009

Low bit-rate compression of omnidirectional images

Pascal Frossard, Ivana Tosic

Omnidirectional images represent a special type of images that are captured by vision sensors with a 360-degree field of view. This work targets the compression of such images by taking into account their particular geometry. We first map omnidirectional i ...

2009