Search

Your search keyword '"ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 )"' showing total 6 results
Start Over Author "ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 )"
6 results on '"ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 )"'

1. A new approach for volume reconstruction in TomoPIV with the alternating direction method of multipliers

Author

Cédric Herzet, Ioana Barbu, Fluid Flow Analysis, Description and Control from Image Sequences (FLUMINANCE), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-15-CE23-0021,BECOSE,Beyond compressive sensing: sparse approximation algorithms for ill-conditioned inverse problems(2016), Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), ANR-15-CE23-0021,BECOSE,Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés(2015), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011), Fluid Flow Analysis, Description and Control from Image Sequences ( FLUMINANCE ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture ( IRSTEA ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), and ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 )

Subjects
Optimization, Mathematical optimization, [ INFO.INFO-TS ] Computer Science [cs]/Signal and Image Processing, Optimization problem, Applied Mathematics, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], TomoPIV, 01 natural sciences, Fast algorithm, Volume reconstruction, 010305 fluids & plasmas, Task (project management), 010309 optics, Noise, Constrained optimization problem, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, 0103 physical sciences, Benchmark (computing), Instrumentation, Engineering (miscellaneous), Mathematics
Abstract

International audience; We adapt and import into the TomoPIV scenery a fast algorithm for solving the volume reconstruction problem. Our approach is based on the reformulation of the volume reconstruction task as a constrained optimization problem and the resort to the " Alternating Directions Method of Multipliers " (ADMM). The inherent primal-dual algorithm is summarized in this article to solve the optimization problem related to the TomoPIV. In particular, the general formulation of the volume reconstruction problem considered in this paper allows to: i) take explicitly into account the level of the noise affecting the data; ii) account for both the nonnegativity and the sparsity of the solution. Experiments on a numerical TomoPIV benchmark show that the proposed framework is a serious contender for the state-of-the-art.

Published
2016

2. Safe screening tests for lasso based on firmly non-expansiveness

Author

Abed Malti, Cédric Herzet, Fluid Flow Analysis, Description and Control from Image Sequences (FLUMINANCE), Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Aboubekr Belkaid - University of Belkaïd Abou Bekr [Tlemcen], INRIA, ANR-13-JS03-0002,GERONIMO,Conception de techniques avancées pour la construction de modèles réduits géophysiques à partir de données images(2013), ANR-15-CE23-0021,BECOSE,Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés(2015), ANR-15-CE23-0021,BECOSE,Beyond compressive sensing: sparse approximation algorithms for ill-conditioned inverse problems(2016), Fluid Flow Analysis, Description and Control from Image Sequences ( FLUMINANCE ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture ( IRSTEA ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 ), Herzet, Cédric, Fondements du numérique - Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés - - BECOSE2015 - ANR-15-CE23-0021 - AAPG2015 - VALID, Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
[ MATH.MATH-OC ] Mathematics [math]/Optimization and Control [math.OC], Screening techniques, Mathematical optimization, [ INFO.INFO-TS ] Computer Science [cs]/Signal and Image Processing, Screening test, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, L1 norm minimization, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], 020206 networking & telecommunications, 02 engineering and technology, State (functional analysis), LASSO, l1-norm minimization, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Lasso (statistics), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, screening techniques, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Projection (set theory), [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Mathematics
Abstract

International audience; This paper focusses on safe screening techniques for the LASSO problem. We derive a new sphere test, coined RFNE, exploiting the firmly non-expansiveness of projection operators. Our test generalizes some methods of the literature but, unlike the latter, exploits approximated primal-dual solutions of the LASSO problem while remaining safe and effective. Our simulation results show that the proposed RFNE test out-performs the best methodology of the state of the art, namely the GAP test derived by Fercoq et al.

Published
2015

3. Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay

Author

Angélique Drémeau, Cédric Herzet, Charles Soussen, Fluid Flow Analysis, Description and Control from Image Sequences (FLUMINANCE), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Automatique de Nancy (CRAN), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), ANR-15-CE23-0021,BECOSE,Beyond compressive sensing: sparse approximation algorithms for ill-conditioned inverse problems(2016), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Institut de Recherche Mathématique de Rennes (IRMAR), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), French Agence Nationale de la Recherche through the BECOSE Project, ANR-15-CE23-0021,BECOSE,Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés(2015), Fluid Flow Analysis, Description and Control from Image Sequences ( FLUMINANCE ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture ( IRSTEA ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance ( Lab-STICC ), École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques ( IBNM ), Université de Brest ( UBO ) -Université européenne de Bretagne ( UEB ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ), Centre de Recherche en Automatique de Nancy ( CRAN ), Université de Lorraine ( UL ) -Centre National de la Recherche Scientifique ( CNRS ), ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 ), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Inria Rennes – Bretagne Atlantique, Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)

Subjects
FOS: Computer and information sciences, Mathematical optimization, Computer Science - Information Theory, MathematicsofComputing_NUMERICALANALYSIS, [ MATH.MATH-IT ] Mathematics [math]/Information Theory [math.IT], 010103 numerical & computational mathematics, 02 engineering and technology, Library and Information Sciences, 01 natural sciences, Sparse vector, Electronic mail, [ INFO.INFO-IT ] Computer Science [cs]/Information Theory [cs.IT], 0202 electrical engineering, electronic engineering, information engineering, Applied mathematics, 0101 mathematics, Mathematics, Mutual coherence, Information Theory (cs.IT), Probabilistic logic, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], 020206 networking & telecommunications, Coherence (statistics), Sparse approximation, Matching pursuit, Computer Science Applications, [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], Algorithm design, Information Systems
Abstract

International audience; We propose extended coherence-based conditions for exact sparse support recovery using orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). Unlike standard uniform guarantees, we embed some information about the decay of the sparse vector coefficients in our conditions. As a result, the standard condition $\mu

Published
2014
Full Text
View/download PDF

4. Sign preservation analysis of orthogonal greedy algorithms

Author

Nguyen, Thi Thanh, Soussen, Charles, Idier, Jérôme, Djermoune, El-Hadi, Centre de Recherche en Automatique de Nancy (CRAN), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des signaux et systèmes (L2S), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire des Sciences du Numérique de Nantes (LS2N), Université de Nantes - Faculté des Sciences et des Techniques, Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Projet ANR BECOSE, ANR-15-CE23-0021,BECOSE,Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés(2015), Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11), Centre National de la Recherche Scientifique (CNRS)-Université de Nantes - Faculté des Sciences et des Techniques, Université de Nantes (UN)-Université de Nantes (UN)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-École Centrale de Nantes (ECN), and ANR-15-CE23-0021,BECOSE,Beyond compressive sensing: sparse approximation algorithms for ill-conditioned inverse problems(2016)

Subjects
Exact Recovery Condition, Non-Negativity, Sparse Non-Negative Least Squares, Orthogonal Least Squares, Orthogonal Matching Pursuit, Mutual Coherence, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Sparse Non-Negative Least Square Problems, Greedy Algorithms, Statistics::Computation
Abstract

We bring a contribution to the exact recovery theory of a non-negative K-sparse vector from noisy linear measurements under the condition mu

Published
2020

5. When does OMP achieve support recovery with continuous dictionaries?

Author

Elvira, Clément, Gribonval, Rémi, Soussen, Charles, Herzet, Cédric, Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio (PANAMA), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE (IRISA-D5), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire des signaux et systèmes (L2S), Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11), SIMulation pARTiculaire de Modèles Stochastiques (SIMSMART), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-AGROCAMPUS OUEST-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and ANR-15-CE23-0021,BECOSE,Beyond compressive sensing: sparse approximation algorithms for ill-conditioned inverse problems(2016)

Subjects
[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [MATH.MATH-RT]Mathematics [math]/Representation Theory [math.RT], Orthogonal Matching Pursuit, continuous dictionaries, sparse representation, exact recovery, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

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.

Published
2019

6. Joint Screening Tests for Lasso

Author

Angélique Drémeau, Cédric Herzet, SIMulation pARTiculaire de Modèles Stochastiques (SIMSMART), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Lab-STICC_ENSTAB_CID_TOMS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), ANR-15-CE23-0021,BECOSE,Au delà de l'échantillonnage compressé : algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés(2015), ANR-13-JS03-0002,GERONIMO,Conception de techniques avancées pour la construction de modèles réduits géophysiques à partir de données images(2013), ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), SIMulation pARTiculaire de Modèles Stochastiques ( SIMSMART ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance ( Lab-STICC ), École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -Université Bretagne Loire ( UBL ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -Université Bretagne Loire ( UBL ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ), ANR-15-CE23-0021,BECOSE,Beyond Compressive Sensing: Sparse approximation algorithms for ill-conditioned inverse problems ( 2016 ), and ANR-13-JS03-0002,GERONIMO,Conception de techniques avancées pour la construction de modèles réduits géophysiques à partir de données images ( 2013 )

Subjects
FOS: Computer and information sciences, Screening test, Computer science, Screening techniques, Machine Learning (stat.ML), 020206 networking & telecommunications, [ SPI.SIGNAL ] Engineering Sciences [physics]/Signal and Image processing, LASSO, 02 engineering and technology, Machine Learning (cs.LG), Set (abstract data type), Computer Science - Learning, l1-norm minimization, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Lasso (statistics), Statistics - Machine Learning, 0202 electrical engineering, electronic engineering, information engineering, Joint (audio engineering), [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Algorithm, [ STAT.ML ] Statistics [stat]/Machine Learning [stat.ML]
Abstract

International audience; This paper focusses on " safe " screening techniques for the LASSO problem. Motivated by the need for low-complexity algorithms, we propose a new approach, dubbed " joint screening test " , allowing to screen a set of atoms by carrying out one single test. The approach is particularized to two different sets of atoms, respectively expressed as sphere and dome regions. After presenting the mathematical derivations of the tests, we elaborate on their relative effectiveness and discuss the practical use of such procedures.

Published
2018

Catalog

Books, media, physical & digital resources
See catalog results