publications | Clément Elvira

Preprint(s)

El0ps: An Exact L0-regularized Problems Solver

Théo Guyard, Cédric Herzet, and Clément Elvira

2025

@preprint{guyard2025el0psexactl0regularizedproblems,
  title = {El0ps: An Exact L0-regularized Problems Solver},
  author = {Guyard, Théo and Herzet, Cédric and Elvira, Clément},
  year = {2025},
  hal = {hal-},
}

A Generic Branch-and-Bound Algorithm for \ell_0-Penalized Problems with Supplementary Material

Clément Elvira, Théo Guyard, and Cédric Herzet

2025

arXiv Hal Bib Code

@preprint{elvira2025genericbranchandboundalgorithmell0penalized,
  title = {A Generic Branch-and-Bound Algorithm for $\ell_0$-Penalized Problems with Supplementary Material},
  author = {Elvira, Clément and Guyard, Théo and Herzet, Cédric},
  year = {2025},
  hal = {hal-},
}

International journal papers (6 entries)

One to beat them all: “RYU” – a unifying framework for the construction of safe balls

Thu-Le Tran, Clément Elvira, Hong-Phuong Dang, and 1 more author

Open Journal of Mathematical Optimization, 2025

DOI arXiv Hal Bib

@article{tran2023beat,
  author = {Tran, Thu-Le and Elvira, Cl\'ement and Dang, Hong-Phuong and Herzet, C\'edric},
  title = {One to beat them all: {{\textquotedblleft}RYU{\textquotedblright}} {\textendash} a unifying framework for the construction of safe balls},
  journal = {Open Journal of Mathematical Optimization},
  eid = {7},
  pages = {1--16},
  publisher = {Universit\'e de Montpellier},
  volume = {6},
  year = {2025},
  doi = {10.5802/ojmo.45},
  language = {en},
  url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.45/},
  hal = {hal-04318380},
}

Bayes in action in deep learning and dictionary learning

Julyan Arbel, Hong-Phuong Dang, Clement Elvira, and 3 more authors

ESAIM Proceedings and surveys, Nov 2023

DOI Hal Bib

@article{Arbel2023-yb,
  title = {Bayes in action in deep learning and dictionary learning},
  author = {Arbel, Julyan and Dang, Hong-Phuong and Elvira, Clement and Herzet, Cedric and Naulet, Zacharie and Vladimirova, Mariia},
  journal = {ESAIM Proceedings and surveys},
  doi = {10.1051/proc/202374090},
  publisher = {EDP Sciences},
  volume = {74},
  pages = {90--107},
  month = nov,
  year = {2023},
  hal = {hal-04357371},
}

Safe Rules for the Identification of Zeros in the Solutions of the SLOPE Problem

Clément Elvira and Cédric Herzet

SIAM Journal on Mathematics of Data Science, Mar 2023

DOI arXiv Hal Bib Supp Code

@article{elvira2021safeSLOPE,
  title = {Safe Rules for the Identification of Zeros in the Solutions of the {SLOPE} Problem},
  author = {Elvira, Clément and Herzet, Cédric},
  year = {2023},
  journal = {{SIAM} Journal on Mathematics of Data Science},
  month = mar,
  publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
  volume = {5},
  number = {1},
  pages = {147--173},
  hal = {hal-03400322},
  doi = {10.1137/21m1457631},
}

When does OMP achieve exact recovery with continuous dictionaries?

Clément Elvira, Rémi Gribonval, Charles Soussen, and 1 more author

Applied and Computational Harmonic Analysis, Mar 2021

Abs DOI arXiv Hal Bib

This paper presents new theoretical results on sparse recovery guarantees for a greedy algorithm, Orthogonal Matching Pursuit (OMP), in the context of continuous parametric dictionaries. Here, the continuous setting means that the dictionary is made up of an infinite (potentially uncountable) number of atoms. In this work, we rely on the Hilbert structure of the observation space to express our recovery results as a property of the kernel defined by the inner product between two atoms. Using a continuous extension of Tropp’s Exact Recovery Condition, we identify two key notions of admissible kernel and admissible support that are sufficient to ensure exact recovery with OMP. We exhibit a family of admissible kernels relying on completely monotone functions for which admissibility holds for any support in the one-dimensional setting. For higher dimensional parameter spaces, an additional notion of axis admissibility is shown to be sufficient to ensure a form of delayed recovery. An additional algebraic condition involving a finite subset of (known) atoms further yields exact recovery guarantees. Finally, a coherence-based viewpoint on these results provides recovery guarantees in terms of a minimum separation assumption.
@article{elvira2021, title = {When does OMP achieve exact recovery with continuous dictionaries?}, author = {Elvira, Cl{\'e}ment and Gribonval, R{\'e}mi and Soussen, Charles and Herzet, Cédric}, journal = {Applied and Computational Harmonic Analysis}, volume = {51}, pages = {374 - 413}, year = {2021}, issn = {1063-5203}, doi = {10.1016/j.acha.2020.12.002}, url = {http://www.sciencedirect.com/science/article/pii/S1063520320300841}, hal = {hal-02099464v4}, }
Safe Squeezing for Antisparse Coding

Clément Elvira and Cedric Herzet

IEEE Transactions on Signal Processing, Mar 2020

Abs DOI arXiv Hal Bib PDF Code

Spreading the information over all coefficients of a representation is a desirable property in many applications such as digital communication or machine learning. This so-called antisparse representation can be obtained by solving a convex program involving an l_∞-norm penalty combined with a quadratic discrepancy. In this paper, we propose a new methodology , dubbed safe squeezing, to accelerate the computation of antisparse representation. We describe a test that allows to detect saturated entries in the solution of the optimization problem. The contribution of these entries is compacted into a single vector, thus operating a form of dimensionality reduction. We propose two algorithms to solve the resulting lower dimensional problem. Numerical experiments show the effectiveness of the proposed method to detect the saturated components of the solution and illustrates the induced computational gains in the resolution of the antisparse problem.
@article{elvira2020_TSP, title = {{Safe Squeezing for Antisparse Coding}}, author = {Elvira, Cl{\'e}ment and Herzet, Cedric}, hal = {hal-02368134}, year = {2020}, doi = {10.1109/tsp.2020.2995192}, url = {https://doi.org/10.1109/tsp.2020.2995192}, publisher = {Institute of Electrical and Electronics Engineers ({IEEE})}, pages = {1--1}, journal = {{IEEE} Transactions on Signal Processing}, keywords = {antisparse coding ; safe screening ; scaled projected-gradient algorithm ; Frank-Wolfe algorithm}, }
Bayesian Antisparse Coding

Clément Elvira, Pierre Chainais, and Nicolas Dobigeon

IEEE Transactions on Signal Processing, Apr 2017

Abs DOI arXiv Hal Bib PDF Code

Sparse representations have proven their efficiency in solving a wide class of inverse problems encountered in signal and image processing. Conversely, enforcing the information to be spread uniformly over representation coefficients exhibits relevant properties in various applications such as robust encoding in digital communications. Antisparse regularization can be naturally expressed through an ℓ∞-norm penalty. This paper derives a probabilistic formulation of such representations. Anew probability distribution, referred to as the democratic prior, is first introduced. Its main properties as well as three random variate generators for this distribution are derived. Then this probability distribution is used as a prior to promote antisparsity in a Gaussian linear model, yielding a fully Bayesian formulation of antisparse coding. Two Markov chain Monte Carlo algorithms are proposed to generate samples according to the posterior distribution. The first one is a standard Gibbs sampler. The second one uses Metropolis-Hastings moves that exploit the proximity mapping of the log-posterior distribution. These samples are used to approximate maximum aposteriori and minimum mean square error estimators of both parameters and hyperparameters. Simulations on synthetic data illustrate the performances of the two proposed samplers, for both complete and over-complete dictionaries. All results are compared to the recent deterministic variational FITRA algorithm.
@article{elvira2017_TSP, author = {Elvira, Clément and Chainais, Pierre and Dobigeon, Nicolas}, journal = {IEEE Transactions on Signal Processing}, title = {Bayesian Antisparse Coding}, year = {2017}, volume = {65}, number = {7}, pages = {1660-1672}, keywords = {Bayes methods;Gaussian distribution;Markov processes;Monte Carlo methods;encoding;inverse problems;maximum likelihood estimation;mean square error methods;ℓ∞-norm penalty;Bayesian antisparse coding;Gaussian linear model;Markov chain Monte Carlo algorithm;antisparse regularization;image processing;inverse problem;log-posterior distribution;maximum a posteriori estimator;minimum mean square error estimator;posterior distribution;probability distribution;signal processing;sparse representation;standard Gibbs sampler;Approximation algorithms;Bayes methods;Encoding;Image coding;Monte Carlo methods;Signal processing algorithms;Standards;Democratic distribution;anti-sparse representation;proximal operator}, doi = {10.1109/TSP.2016.2645543}, issn = {1053-587X}, month = apr, hal = {hal-01433706}, }

International conference papers (16 entries)

A New Branch-and-Bound Pruning Framework for \ell_0-Regularized Problems

Guyard Theo, Cédric Herzet, Clément Elvira, and 1 more author

In Proceedings of the 41st International Conference on Machine Learning, 21–27 jul 2024

Abs arXiv Hal Bib PDF Code

We consider the resolution of learning problems involving \ell_0-regularization via Branch-and- Bound (BnB) algorithms. These methods explore regions of the feasible space of the problem and check whether they do not contain solutions through “pruning tests”. In standard implementations, evaluating a pruning test requires to solve a convex optimization problem, which may result in computational bottlenecks. In this paper, we present an alternative to implement pruning tests for some generic family of \ell_0-regularized problems. Our proposed procedure allows the simultaneous assessment of several regions and can be embedded in standard BnB implementations with a negligible computational overhead. We show through numerical simulations that our pruning strategy can improve the solving time of BnB procedures by several orders of magnitude for typical problems encountered in machine-learning applications.
@inproceedings{guyard2024, title = {A New Branch-and-Bound Pruning Framework for $\ell_0$-Regularized Problems}, author = {Theo, Guyard and Herzet, C\'{e}dric and Elvira, Cl\'{e}ment and Arslan, Ayse-Nur}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {48077--48096}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, url = {https://proceedings.mlr.press/v235/theo24a.html}, hal = {}, }

Region-free Safe Screening Tests for \ell 1 -penalized Convex Problems

Cédric Herzet, Clément Elvira, and Hong-Phuong Dang

In 2022 30th European Signal Processing Conference (EUSIPCO), Aug 2022

DOI Hal Bib

@inproceedings{herzet2022Eusipco,
  title = {{Region-free Safe Screening Tests for {\ell} 1 -penalized Convex Problems}},
  author = {Herzet, C{\'e}dric and Elvira, Cl{\'e}ment and Dang, Hong-Phuong},
  url = {https://hal-centralesupelec.archives-ouvertes.fr/hal-03806099},
  booktitle = {2022 30th European Signal Processing Conference ({EUSIPCO})},
  doi = {10.23919/eusipco55093.2022.9909532},
  address = {Belgrade, Serbia},
  year = {2022},
  month = aug,
  keywords = {sparsity ; convex problem ; safe screening},
  hal = {hal-03806099},
}

Safe Peeling for \ell_0-Regularized Least-Squares

Théo Guyard, Gilles Monnoyer, Clément Elvira, and 1 more author

In 2023 31st European Signal Processing Conference (EUSIPCO), Aug 2023

DOI arXiv Hal Bib Supp Code

@inproceedings{GuyardPeeling23,
  author = {Guyard, Théo and Monnoyer, Gilles and Elvira, Clément and Herzet, Cédric},
  booktitle = {2023 31st European Signal Processing Conference (EUSIPCO)},
  title = {Safe Peeling for $\ell_{0}$-Regularized Least-Squares},
  year = {2023},
  volume = {},
  number = {},
  pages = {1748-1752},
  doi = {10.23919/EUSIPCO58844.2023.10290041},
  hal = {hal-04271074},
}

Beyond GAP screening for Lasso by exploiting new dual cutting half-spaces

Thu-Le Tran, Clément Elvira, Hong-Phuong Dang, and 1 more author

In 2022 30th European Signal Processing Conference (EUSIPCO), Aug 2022

DOI arXiv Hal Bib Supp Code

@inproceedings{Le2022HolderDome,
  author = {Tran, Thu-Le and Elvira, Cl{\'e}ment and Dang, Hong-Phuong and Herzet, C{\'e}dric},
  title = {Beyond {GAP} screening for {Lasso}  by exploiting new dual cutting half-spaces},
  year = {2022},
  booktitle = {2022 30th European Signal Processing Conference ({EUSIPCO})},
  doi = {},
  month = aug,
  hal = {hal-03805966},
}

Screen & Relax: Accelerating the resolution of Elastic-net by safe identification of the solution support

Théo Guyard, Cédric Herzet, and Clément Elvira

In ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Aug 2021

DOI arXiv Hal Bib Code

@inproceedings{guyard2021screen,
  title = {Screen \& Relax: Accelerating the resolution of Elastic-net by safe identification of the solution support},
  author = {Guyard, Th{\'e}o and Herzet, C{\'e}dric and Elvira, Cl{\'e}ment},
  booktitle = {ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  pages = {5443-5447},
  year = {2021},
  doi = {10.1109/ICASSP43922.2022.9747412},
  hal = {hal-03462191},
}

Node-screening tests for l0-penalized Least-Squares problem

Théo Guyard, Cédric Herzet, and Clément Elvira

In ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Oct 2021

DOI arXiv Hal Bib Supp Code

@inproceedings{Guyard2021techreport,
  author = {Guyard, Théo and Herzet, Cédric and Elvira, Clément},
  keywords = {Branch-and-bound ; Cardinality constraint ; Sparse approximation ; Continuous relaxation ; Homotopy continuation},
  title = {Node-screening tests for l0-penalized Least-Squares problem},
  booktitle = {ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  month = oct,
  year = {2021},
  pages = {5448-5452},
  doi = {10.1109/ICASSP43922.2022.9747563},
  hal = {hal-03462171},
}

Continuous dictionaries meet low-rank tensor approximations

Clément Elvira, Jérémy E Cohen, Cédric Herzet, and 1 more author

In iTwist 2020 - International Traveling Workshop on Interactions between low-complexity data models and Sensing Techniques, Jun 2020

Hal Bib PDF

@inproceedings{elvira2020_itwist,
  title = {{Continuous dictionaries meet low-rank tensor approximations}},
  author = {Elvira, Cl{\'e}ment and Cohen, J{\'e}r{\'e}my E and Herzet, C{\'e}dric and Gribonval, R{\'e}mi},
  url = {https://hal.archives-ouvertes.fr/hal-02567115},
  booktitle = {{iTwist 2020 - International Traveling Workshop on Interactions between low-complexity data models and Sensing Techniques}},
  address = {Nantes, France},
  pages = {1-3},
  year = {2020},
  month = jun,
  hal = {hal-02567115},
}

BLASTER: An Off-Grid Method for Blind and Regularized\{Acoustic Echoes Retrieval

Diego Di Carlo, Clément Elvira, Antoine Deleforge, and 2 more authors

In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Jun 2020

DOI Hal Bib Code

@inproceedings{elvira2020icassp2,
  title = {{BLASTER: An Off-Grid Method for Blind and Regularized\\ Acoustic Echoes Retrieval}},
  author = {Di Carlo, Diego and Elvira, Cl{\'e}ment and Deleforge, Antoine and Bertin, Nancy and Gribonval, Rémi},
  booktitle = {ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  publisher = {{IEEE}},
  year = {2020},
  doi = {10.1109/ICASSP40776.2020.9054647},
  hal = {hal-02469901},
  pages = {156-160}
}

Short and squeezed: accelerating the computation of antisparse representations with safe squeezing

Clément Elvira and Cédric Herzet

In ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Jun 2020

DOI Hal Bib Code

@inproceedings{elvira2020icassp,
  title = {{Short and squeezed: accelerating the computation of antisparse representations with safe squeezing}},
  author = {Elvira, Cl{\'e}ment and Herzet, Cédric},
  booktitle = {ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  publisher = {{IEEE}},
  year = {2020},
  doi = {10.1109/ICASSP40776.2020.9053156},
  hal = {hal-03070344},
  pages = {5615-5619},
}

Uniform k-step recovery with CMF dictionaries

Clément Elvira, Rémi Gribonval, Cédric Herzet, and 1 more author

In SPARS 2019 - Signal Processing with Adaptive Sparse Structured Representations, Jul 2019

Abs Hal Bib

We present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous parametric dictionaries, i.e., made up of an infinite uncountable number of atoms. We build up a family of dictionaries for which k-step recovery is possible.
@inproceedings{elvira2019spars, title = {{Uniform k-step recovery with CMF dictionaries}}, author = {Elvira, Cl{\'e}ment and Gribonval, R{\'e}mi and Herzet, C{\'e}dric and Soussen, Charles}, booktitle = {{SPARS 2019 - Signal Processing with Adaptive Sparse Structured Representations}}, address = {Toulouse, France}, pages = {1-2}, year = {2019}, month = jul, hal = {hal-02157561}, }

OMP and continuous dictionaries: is k-step recovery possible?

Clément Elvira, Rémi Gribonval, Charles Soussen, and 1 more author

In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2019

Abs DOI Hal Bib PDF

In this work, we present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous parametric dictionaries, i.e., made up of an infinite uncountable number of atoms.We build up a family of dictionaries for which k-step recovery is possible with OMP for 1-dimensional parameters. In higher dimension, algebraic conditions become necessary and will lead us to revisit some well-known k-step discrete analyses. Finally, a toy-example illustrates the level of tightness of our sufficient conditions.

@inproceedings{elvira2019icassp,
  title = {{OMP and continuous dictionaries: is k-step recovery possible?}},
  author = {Elvira, Cl{\'e}ment and Gribonval, R{\'e}mi and Soussen, Charles and Herzet, Cédric},
  url = {https://hal.archives-ouvertes.fr/hal-02049486},
  booktitle = {ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  address = {Brighton, United Kingdom},
  organization = {{IEEE}},
  publisher = {{IEEE}},
  doi = {10.1109/ICASSP.2019.8683617},
  issn = {2379-190X},
  year = {2019},
  pages = {5546-5550},
  month = may,
  keywords = {Index Terms-Sparse representation ; exact recovery ; orthogonal matching pursuit ; continuous dictionaries ; sparse representation ; continuous dictio-naries},
  hal = {hal-02049486},
}

Parameter-free Small Variance Asymptotics for Dictionary Learning

Hong-Phuong Dang and Clément Elvira

In 2019 27th European Signal Processing Conference (EUSIPCO), May 2019

DOI Bib

@inproceedings{dang2019eusipco,
  author = {Dang, Hong-Phuong and Elvira, Clément},
  booktitle = {2019 27th European Signal Processing Conference (EUSIPCO)},
  title = {Parameter-free Small Variance Asymptotics for Dictionary Learning},
  year = {2019},
  volume = {},
  number = {},
  pages = {1-5},
  doi = {10.23919/EUSIPCO.2019.8903025},
}

A case of exact recovery with OMP using continuous dictionaries

Clément Elvira, Rémi Gribonval, Cédric Herzet, and 1 more author

In CS 2018 - 9th International Conference on Curves and Surfaces, Jun 2018

Abs Hal Bib

We present new theoretical results on sparse recovery guarantees for a greedy algorithm, orthogonal matching pursuit (OMP), in the context of continuous dictionaries. Consider a sparse linear combination of atoms from a dictionary parameterized by some real parameters, for example, a combination of shifted versions of a basic waveform as in the context of sparse spike deconvolution. Currently, performance guarantees for greedy algorithms are typically carried out in the discrete setting associated to a grid of atom parameters, and based on, e.g., the coherence of the considered discretized dictionary \cite{tropp2004}. However, such analyses fail to be conclusive for grid-based approaches when the discretization step tends to zero, as the coherence goes to one. Instead, our analysis is directly conducted in the continuous setting. For atoms parametrized by a real parameter that are elements of the (infinite-dimensional) Hilbert space L_2(\mathbb{R}) of square integrable real functions, and such that the inner product between two atoms is the exponential of the negative absolute difference of the corresponding parameters, we show in the noise-free setting that OMP exactly recovers the atom parameters as well as their amplitudes, regardless of the number of distinct atoms. We exhibit a convolutive dictionary of exponentially decaying pulses for which the atoms have an analytic definition while their pairwise inner products have the prescribed form. The established guarantees rely on a proof technique which is the continuous equivalent of Tropp’s Exact Recovery Condition (ERC) \cite{tropp2004}. The proof exploits specific properties of the positive definite kernel between atom parameters defined by the inner product between the corresponding atoms. Future work will aim at characterizing the class of kernels for which such an analysis holds –in particular for higher dimensional parameters– and the compatibility of the guarantees with dimension reduction techniques such as sketching, which would pave the way to provably good greedy algorithms for compressive statistical learning \cite{Gribonval2017}. In light of the existing links between Tropp’s ERC and recovery guarantees for \ell_1 minimization \cite{tropp2006}, an interesting question is whether these guarantees extend to sparse spike recovery with total variation norm minimization \cite{Duval2015,candes2014}.
@inproceedings{elvira2018CS, title = {{A case of exact recovery with OMP using continuous dictionaries}}, author = {Elvira, Cl{\'e}ment and Gribonval, R{\'e}mi and Herzet, Cédric and Soussen, Charles}, booktitle = {{CS 2018 - 9th International Conference on Curves and Surfaces}}, address = {Arcachon, France}, year = {2018}, month = jun, hal = {hal-01937532}, }
Small variance asymptotics and bayesian nonparametrics for dictionary learning

Clement Elvira, Hong-Phuong Dang, and Pierre Chainais

In 2018 26th European Signal Processing Conference (EUSIPCO), Sep 2018

Abs DOI Hal Bib PDF Code

Bayesian nonparametric (BNP) is an appealing framework to infer the complexity of a model along with the parameters. To this aim, sampling or variational methods are often used for inference. However, these methods come with numerical disadvantages for large-scale data. An alternative approach is to relax the probabilistic model into a non-probabilistic formulation which yields a scalable algorithm. One limitation of BNP approaches can be the cost of Monte-Carlo sampling for inference. Small-variance asymptotic (SVA) approaches paves the way to much cheaper though approximate methods for inference by taking benefit from a fruitful interaction between Bayesian models and optimization algorithms. In brief, SVA lets the variance of the noise (or residual error) distribution tend to zero in the optimization problem corresponding to a MAP estimator with finite noise variance for instance. We propose such an SVA analysis of a BNP dictionary learning (DL) approach that automatically adapts the size of the dictionary or the subspace dimension in an efficient way. Numerical experiments illustrate the efficiency of the proposed method.
@inproceedings{elvira2018eusipco, doi = {10.23919/eusipco.2018.8553142}, year = {2018}, month = sep, publisher = {{IEEE}}, author = {Elvira, Clement and Dang, Hong-Phuong and Chainais, Pierre}, title = {Small variance asymptotics and bayesian nonparametrics for dictionary learning}, booktitle = {2018 26th European Signal Processing Conference ({EUSIPCO})}, hal = {hal-01961852}, }
Bayesian nonparametric subspace estimation

Clément Elvira, Pierre Chainais, and Nicolas Dobigeon

In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Mar 2017

Abs DOI Hal Bib PDF

Principal component analysis is a widely used technique to perform dimension reduction. However, selecting a finite number of significant components is essential and remains a crucial issue. Only few attempts have proposed a probabilistic approach to adaptively select this number. This paper introduces a Bayesian nonparametric model to jointly estimate the principal components and the corresponding intrinsic dimension. More precisely, the observations are projected onto a random orthogonal basis which is assigned a prior distribution defined on the Stiefel manifold. Then the factor scores take benefit of an Indian buffet process prior to model the uncertainty related to the number of components. The parameters of interest as well as the nuisance parameters are finally inferred within a fully Bayesian framework via Monte Carlo sampling. The performances of the proposed approach are assessed thanks to experiments conducted on various examples.
@inproceedings{Elvira_IEEE_ICASSP_2017, author = {Elvira, Clément and Chainais, Pierre and Dobigeon, Nicolas}, booktitle = {2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, doi = {10.1109/ICASSP.2017.7952556}, keywords = {Bayes methods;Estimation;Manifolds;Monte Carlo methods;Numerical models;Principal component analysis;Probabilistic logic;Bayesian inference;Indian buffet process;dimension reduction;distribution on the Stiefel manifold}, month = mar, pages = {2247-2251}, title = {Bayesian nonparametric subspace estimation}, year = {2017}, hal = {hal-01687163}, }
Democratic prior for anti-sparse coding

Clément Elvira, Pierre Chainais, and Nicolas Dobigeon

In 2016 IEEE Statistical Signal Processing Workshop (SSP), Jun 2016

Abs DOI Hal Bib PDF Code

Bayesian nonparametric (BNP) is an appealing framework to infer the complexity of a model along with the parameters. To this aim, sampling or variational methods are often used for inference. However, these methods come with numerical disadvantages for large-scale data. An alternative approach is to relax the probabilistic model into a non-probabilistic formulation which yields a scalable algorithm. One limitation of BNP approaches can be the cost of Monte-Carlo sampling for inference. Small-variance asymptotic (SVA) approaches paves the way to much cheaper though approximate methods for inference by taking benefit from a fruitful interaction between Bayesian models and optimization algorithms. In brief, SVA lets the variance of the noise (or residual error) distribution tend to zero in the optimization problem corresponding to a MAP estimator with finite noise variance for instance. We propose such an SVA analysis of a BNP dictionary learning (DL) approach that automatically adapts the size of the dictionary or the subspace dimension in an efficient way. Numerical experiments illustrate the efficiency of the proposed method.
@inproceedings{elvira2016ssp, author = {Elvira, Clément and Chainais, Pierre and Dobigeon, Nicolas}, booktitle = {2016 IEEE Statistical Signal Processing Workshop (SSP)}, title = {Democratic prior for anti-sparse coding}, year = {2016}, pages = {1-4}, keywords = {Markov processes;Monte Carlo methods;inverse problems;probability;signal representation;ℓ∞-norm regularization;Gibbs sampler;anti-sparse coding;complete dictionary;democratic distribution;joint posterior distribution;linear Gaussian inverse problem;probabilistic formulation;probability distribution;proximal Markov chain Monte Carlo algorithm;representation coefficients;Bayes methods;Encoding;Inverse problems;Monte Carlo methods;Peak to average power ratio;Probability density function;Signal processing algorithms;Anti-sparse representation;democratic distribution;inverse problem}, doi = {10.1109/SSP.2016.7551813}, month = jun, hal = {hal-01433632}, }

National conference papers (6 entries)

Une nouvelle méthode d’accélération pour LASSO par élimination sûre de variables

Thu-Le Tran, Clément Elvira, Hong-Phuong Dang, and 1 more author

In Conférence sur l’Apprentissage automatique, Jul 2022

Hal Bib Code

@inproceedings{tran2022cap,
  title = {{Une nouvelle m{\'e}thode d'acc{\'e}l{\'e}ration pour LASSO par {\'e}limination s{\^u}re de variables}},
  author = {Tran, Thu-Le and Elvira, Cl{\'e}ment and Dang, Hong-Phuong and Herzet, C{\'e}dric},
  booktitle = {{Conf{\'e}rence sur l'Apprentissage automatique}},
  address = {Vannes, France},
  year = {2022},
  month = jul,
  keywords = {LASSO ; r{\'e}duction de dimensionalit{\'e} ; {\'e}limination de variables ; safe screening},
  hal = {hal-03806044},
  language = {French},
}

Screen & Relax: Accélérer la résolution du problème" Elastic-Net" par identification du support de la solution

Theo Guyard, Cédric Herzet, and Clément Elvira

In GRETSI 2022-XXVIIIème Colloque Francophone de Traitement du Signal et des Images, Jul 2022

Hal Bib Code

@inproceedings{guyard2022screen,
  title = {Screen \& Relax: Acc{\'e}l{\'e}rer la r{\'e}solution du probl{\`e}me" Elastic-Net" par identification du support de la solution},
  author = {Guyard, Theo and Herzet, C{\'e}dric and Elvira, Cl{\'e}ment},
  booktitle = {GRETSI 2022-XXVIII{\`e}me Colloque Francophone de Traitement du Signal et des Images},
  year = {2022},
  hal = {hal-03778139},
  language = {French},
}

Node-screening pour le problème des moindres carrés avec pénalité L0

Theo Guyard, Cédric Herzet, Clément Elvira, and 1 more author

In GRETSI 2022-XXVIIIème Colloque Francophone de Traitement du Signal et des Images, Jul 2022

Hal Bib PDF Code

@inproceedings{guyard2022node,
  title = {Node-screening pour le probl{\`e}me des moindres carr{\'e}s avec p{\'e}nalit{\'e} L0},
  author = {Guyard, Theo and Herzet, C{\'e}dric and Elvira, Cl{\'e}ment and Arslan, Ay{\c{s}}e Nur},
  booktitle = {GRETSI 2022-XXVIII{\`e}me Colloque Francophone de Traitement du Signal et des Images},
  year = {2022},
  hal = {hal-03784682},
  language = {French},
}

Identification de supports en k etapes avec OMP pour les dictionnaires continus

Clément Elvira, Rémi Gribonval, Charles Soussen, and 1 more author

In GRETSI 2019 - XXVIIème Colloque francophonede traitement du signal et des images, Aug 2019

Abs Hal Bib

Nous présentons de nouveaux résultats concernant les garanties d’identification de support en k étapes pour un algorithme glouton, orthogonal matching pursuit (OMP), pour les dictionnaires continus. Un dictionnaire est dit continu s’il est constitué d’une infinité indénom-brable d’atomes. Nous étudions une famille de dictionnaires paramétrés, appelée CMF (pour completely monotone function), pour laquelle l’identification de support en k étapes est toujours possible lorsque le paramètre est de dimension 1 quels que soient le nombre et le choix des atomes du support. En dimension supérieure, des conditions algébriques deviennent nécessaires et nous amènent à revisiter les analyses classiques du cas discret. Finalement, nous discutons l’implémentation d’une version continue d’OMP.
@inproceedings{elvira2019gretsi, title = {{Identification de supports en k etapes avec OMP pour les dictionnaires continus}}, author = {Elvira, Cl{\'e}ment and Gribonval, R{\'e}mi and Soussen, Charles and Herzet, C{\'e}dric}, url = {https://hal.inria.fr/hal-02157571}, booktitle = {{GRETSI 2019 - XXVII{\`e}me Colloque francophonede traitement du signal et des images}}, address = {Lille, France}, pages = {1-4}, year = {2019}, month = aug, language = {French}, hal = {https://hal.inria.fr/hal-02157571v1}, }
Vers une méthode d’optimisation non paramétrique pour l’apprentissage de dictionnaire en utilisant Small-Variance Asymptotics pour modèle probabiliste

Hong-Phuong Dang, Clément Elvira, and Pierre Chainais

In CAP, Aug 2018

Abs Bib PDF Code

Dans les modèles probabilistes, les méthodes d’échantillonnage et les approximations variationnelles sont souvent utilisées pour l’inférence. Mais ces méthodes passent difficilement à l’échelle. Une alternative consiste à relâcher le modèle probabiliste dans une formulation non probabiliste et utiliser un algorithme évolutif pour résoudre le problème de minimisation associé. Nous proposons une analyse dite de Small-Variance Asymptotics (SVA) du modèle bayésien non paramétrique de type Buffet Indien à deux paramètres qui apprend automatiquement un dictionnaire de taille adaptée. Cette approche s’obtient en faisant tendre la variance de la vraisemblance du modèle vers 0. L’analyse montre une interaction entre les méthodes bayésiennes et optimisation. Les résultats illustrent la pertinence de la méthode proposée.
@inproceedings{dang2018cap, author = {Dang, Hong-Phuong and Elvira, Clément and Chainais, Pierre}, title = { Vers une méthode d'optimisation non paramétrique pour l'apprentissage de dictionnaire en utilisant Small-Variance Asymptotics pour modèle probabiliste}, booktitle = {CAP}, year = {2018}, address = {Rouen}, language = {French}, }
Une formulation bayésienne du codage antiparcimonieux

Clément Elvira, Pierre Chainais, and Nicolas Dobigeon

In Actes du XXVIi‘eme Colloque GRETSI, Aug 2017

Abs Hal Bib PDF Code

Dans un but de robustesse, un codage antiparcimonieux répartit uniformément l’information d’un signal sur toutes les composantes de sa représentation. La recherche d’un tel codage s’exprime naturellement sous la forme d’un problème variationnel impliquant une régularisation de type \ell_∞. Dans cet article une formulation bayésienne du problème est proposée, impliquant une nouvelle loi de probabilité, la loi démocratique, qui pénalise les fortes amplitudes. Cette distribution est choisie comme loi a priori sur les coefficients de représentation, couplée avec une vraisemblance gaussienne. Les estimateurs bayésiens des coefficients de représentation peuvent être approchés à l’aide d’un échantillonneur de Gibbs. Cette méthode passe cependant difficilement à l’échelle et un algorithme de Monte Carlo proximal a été proposé. On discute une nouvelle façon de choisir et régler la loi a priori sur les paramètres de nuisance. Deux simulations numériques permettent de valider le réglage des hyperparamètres et la recherche du paramètre de régularisation.
@inproceedings{elvira2017gretsi, author = {Elvira, Clément and Chainais, Pierre and Dobigeon, Nicolas}, title = {Une formulation bayésienne du codage antiparcimonieux}, booktitle = {Actes du XXVIi`eme Colloque GRETSI}, year = {2017}, address = {Juan-les-Pins, France}, language = {French}, hal = {hal-01691387}, }

Technical reports

Bayesian nonparametric principal component analysis

Clément Elvira, Pierre Chainais, and Nicolas Dobigeon

2017

Abs arXiv Hal Bib

Principal component analysis (PCA) is very popular to perform dimension reduction. The selection of the number of significant components is essential but often based on some practical heuristics depending on the application. Only few works have proposed a probabilistic approach able to infer the number of significant components. To this purpose, this paper introduces a Bayesian nonparametric principal component analysis (BNP-PCA). The proposed model projects observations onto a random orthogonal basis which is assigned a prior distribution defined on the Stiefel manifold. The prior on factor scores involves an Indian buffet process to model the uncertainty related to the number of components. The parameters of interest as well as the nuisance parameters are finally inferred within a fully Bayesian framework via Monte Carlo sampling. A study of the (in-)consistence of the marginal maximum a posteriori estimator of the latent dimension is carried out. A new estimator of the subspace dimension is proposed. Moreover, for sake of statistical significance, a Kolmogorov-Smirnov test based on the posterior distribution of the principal components is used to refine this estimate. The behaviour of the algorithm is first studied on various synthetic examples. Finally, the proposed BNP dimension reduction approach is shown to be easily yet efficiently coupled with clustering or latent factor models within a unique framework.
@techreport{elvira2017preprint, title = {Bayesian nonparametric principal component analysis}, author = {Elvira, Cl{\'e}ment and Chainais, Pierre and Dobigeon, Nicolas}, journal = {arXiv preprint arXiv:1709.05667}, year = {2017}, hal = {hal-01687236/}, }

Supplementary materials: Safe rules for the identification of zeros in the solutions of the SLOPE problem

Clément Elvira and Cédric Herzet

Oct 2021

Bib PDF

@techreport{elvira2021safeSLOPEsuppmat,
  title = {{Supplementary materials: Safe rules for the identification of zeros in the solutions of the SLOPE problem}},
  author = {Elvira, Clément and Herzet, Cédric},
  year = {2021},
  month = oct,
}

A response to “Fast OSCAR and OWL Regression via Safe Screening Rules” by Bao et al.

Clément Elvira and Cédric Herzet

Oct 2021

Technical report

Bib PDF

@techreport{Elvira2021techreport,
  author = {Elvira, Clément and Herzet, Cédric},
  note = {Technical report},
  title = {A response to ``Fast OSCAR and OWL Regression via Safe Screening Rules'' by Bao et al.},
  institution = {},
  month = oct,
  year = {2021},
}

Thesis

Modèles bayésiens pour l’identification de représentations antiparcimonieuses et l’analyse en composantes principales non paramétrique

Clément Elvira

Centrale Lille, Nov 2017

Hal Bib PDF

@phdthesis{elvira2017phdthesis,
  author = {Elvira, Clément},
  title = {Modèles bayésiens pour l’identification de représentations antiparcimonieuses et l’analyse en composantes principales non paramétrique},
  language = {French},
  year = {2017},
  month = nov,
  school = {Centrale Lille},
  address = {Lille, France},
  hal = {tel-01730077v2},
}