Skip to Main content Skip to Navigation
New interface
Journal articles

Stable safe screening and structured dictionaries for faster L1 regularization

Cassio Fraga Dantas 1 Rémi Gribonval 1 
1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio
Inria Rennes – Bretagne Atlantique , IRISA-D5 - SIGNAUX ET IMAGES NUMÉRIQUES, ROBOTIQUE
Abstract : In this paper, we propose a way to combine two acceleration techniques for the L1-regularized least squares problem: safe screening tests, which allow to eliminate useless dictionary atoms; and the use of fast structured approximations of the dictionary matrix. To do so, we introduce a new family of screening tests, termed stable screening, which can cope with approximation errors on the dictionary atoms while keeping the safety of the test (i.e. zero risk of rejecting atoms belonging to the solution support). Some of the main existing screening tests are extended to this new framework. The proposed algorithm consists in using a coarser (but faster) approximation of the dictionary at the initial iterations and then switching to better approximations until eventually adopting the original dictionary. A systematic switching criterion based on the duality gap saturation and the screening ratio is derived. Simulation results show significant reductions in both computational complexity and execution times for a wide range of tested scenarios.
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-01954261
Contributor : Cassio F. Dantas Connect in order to contact the contributor
Submitted on : Thursday, July 4, 2019 - 12:36:27 PM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM

Files

journal3.pdf
Files produced by the author(s)

Identifiers

Relations

  • has part hal-02129219 - Software for reproducible research

Citation

Cassio Fraga Dantas, Rémi Gribonval. Stable safe screening and structured dictionaries for faster L1 regularization. IEEE Transactions on Signal Processing, 2019, 67 (14), pp.3756-3769. ⟨10.1109/TSP.2019.2919404⟩. ⟨hal-01954261v3⟩

Share

Metrics

Record views

211

Files downloads

223