Stable Safe Screening and Structured Dictionaries for Faster $\ell _{1}$ Regularization

View Researcher's Other Codes

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors C. Dantas, R. Gribonval
Journal/Conference Name IEEE Transactions on Signal Processing
Paper Category
Paper Abstract In this paper, we propose a way to combine two acceleration techniques for the $\ell _1$-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.
Date of publication 2018
Code Programming Language Python

Copyright Researcher 2022