Frank-Wolfe Algorithm for the Exact Sparse Problem

Farah Cherfaoui (1) , Valentin Emiya (1) , Liva Ralaivola (1, 2) , Sandrine Anthoine (3)

1 QARMA - éQuipe d'AppRentissage de MArseille
2 Criteo [Paris]
3 I2M - Institut de Mathématiques de Marseille

In this paper, we study the properties of the Frank-Wolfe algorithm to solve the \ExactSparse reconstruction problem. We prove that when the dictionary is quasi-incoherent, at each iteration, the Frank-Wolfe algorithm picks up an atom indexed by the support. We also prove that when the dictionary is quasi-incoherent, there exists an iteration beyond which the algorithm converges exponentially fast.

Domains: Computer Science [cs]; Machine Learning [cs.LG]; Computer Science [cs]; Signal and Image Processing

Farah Cherfaoui, Valentin Emiya, Liva Ralaivola, Sandrine Anthoine. Frank-Wolfe Algorithm for the Exact Sparse Problem. iTWIST: international Traveling Workshop on Interactions between low-complexity data models and Sensing Techniques, Nov 2018, Marseille, France. ⟨hal-01881329⟩