Faster and still safe: combining screening techniques and structured dictionaries to accelerate the Lasso

Cassio Fraga Dantas (1) , Rémi Gribonval (1)

1 PANAMA - Parcimonie et Nouveaux Algorithmes pour le Signal et la Modélisation Audio

Accelerating the solution of the Lasso problem becomes crucial when scaling to very high dimensional data. In this paper, we propose a way to combine two existing acceleration techniques: safe screening tests, which simplify the problem by eliminating useless dictionary atoms; and the use of structured dictionaries which are faster to operate with. A structured approximation of the true dictionary is used at the initial stage of the optimization, and we show how to define screening tests which are still safe despite the approximation error. In particular, we extend a state-of-the-art screening test, the GAP SAFE sphere test, to this new setting. The practical interest of the proposed methodology is demonstrated by considerable reductions in simulation time.

Mots clés: Lasso; safe screening; sparsity; structured dictionaries

Domaines: Traitement du signal et de l'image [eess.SP]

Cassio Fraga Dantas, Rémi Gribonval. Faster and still safe: combining screening techniques and structured dictionaries to accelerate the Lasso. ICASSP 2018 - IEEE International Conference on Acoustics, Speech and Signal Processing, Apr 2018, Calgary, AB, Canada. pp.4069-4073, ⟨10.1109/ICASSP.2018.8461514⟩. ⟨hal-01706392⟩