Node-Screening Tests For The L0-Penalized Least-Squares Problem

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

Document type :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

DOI :

10.1109/ICASSP43922.2022.9747563

Title :

Node-Screening Tests For The L0-Penalized Least-Squares Problem

Author(s) :

Guyard, Theo [Auteur]
Institut National des Sciences Appliquées - Rennes [INSA Rennes]
Inria Rennes – Bretagne Atlantique
SIMulation pARTiculaire de Modèles Stochastiques [SIMSMART]
Institut de Recherche Mathématique de Rennes [IRMAR]
Herzet, Cédric [Auteur]
SIMulation pARTiculaire de Modèles Stochastiques [SIMSMART]
Elvira, Clément [Auteur]
Institut d'Électronique et des Technologies du numéRique [IETR]

Conference title :

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

City :

Singapore

Country :

Singapour

Start date of the conference :

2022-05-23

Publisher :

IEEE

HAL domain(s) :

Mathématiques [math]/Optimisation et contrôle [math.OC]
Mathématiques [math]/Combinatoire [math.CO]
Informatique [cs]/Traitement du signal et de l'image [eess.SP]

English abstract : [en]

We present a novel screening methodology to safely discard irrelevant nodes within a generic branch-and-bound (BnB) algorithm solving the `0-penalized least-squares problem. Our contribution is a set of two simple tests ...
Show more >We present a novel screening methodology to safely discard irrelevant nodes within a generic branch-and-bound (BnB) algorithm solving the `0-penalized least-squares problem. Our contribution is a set of two simple tests to detect sets of feasible vectors that cannot yield optimal solutions. This allows to prune nodes of the BnB search tree, thus reducing the overall optimization time. One cornerstone of our contribution is a nesting property between tests at different nodes that allowsto implement them with a low computational cost. Our work leverages the concept of safe screening, well known for sparsity-inducing convex problems, and some recent advances in this field for `0-penalized regression problems.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation

Collections :