Contact: Adrian Jarret (LCAV)
Synopsis: Discover the Frank-Wolfe algorithm for convex optimization with sparse priors, contribute to the development of a fast polyatomic variant, find local maxima on a 2D image, simulate image reconstruction for radio astronomy.
Level: Bachelor – Master (semester project)
Sections: IC
Description: The LASSO problem [1] is a convex optimization problem that helps at finding sparse solutions to an ill-posed linear inverse problem. The Frank-Wolfe algorithm (FW) is an optimization algorithm that can be used to find a solution to the LASSO problem. This algorithm is interesting when applied to the LASSO as it constructs a solution by filling an empty solution, iteratively activating one component at a step. We refer to this mechanism as an atomic method. By doing so, the algorithm is able to produce a sparse solution but also to maintain sparse iterates during the iterations, which is a great interest for two reasons: first, it limits the memory requirement, leading to a scalable algorithm; second, it is in practice a fast solver when the solution is really sparse as it is able to quickly identify the few active degrees of freedom of the proposed solution.
In this context, we have developed a polyatomic variant of the Frank-Wolfe algorithm (PFW), that builds upon the traditional FW method by conserving the same structure, but that is able to place many atoms at each iteration (compared to only one for the initial method). This way, PFW makes the optimization steps more valuable as they gather more information on the candidate solution. It results in a faster algorithm, that is even able to outperform the most popular LASSO solvers in terms of solving time.
However, this algorithm might still be improved. Indeed, in the current version of PFW, the many candidate atoms at each iteration are selected as the highest level sets of the gradient. This strategy then does not place sparse atoms but rather patches as iterative updates of the support of the solution. The goal of this student project would be to develop and test new strategies to estimate the possible candidate atoms at each step. This first idea to try consists in looking for the local maxima of the gradient, in order to shrink each level set patch to a single sparse element. Many more refinements are possible then, which might be considered depending on the progress of the student.
Deliverables:
- Python code that implements the new polyatomic update strategies
- Quantitative and documented study of the performances of the modified solvers, compared to the initial PFW algorithm
- Project report that presents the theoretical context and summarizes the experiments and the findings
Prerequisites:
- Experience in numerical computing and object-oriented programming with Python (Numpy, Matplotlib)
- Experience in collaborative development environment
- Basic knowledge in linear algebra and convex optimization
Type of Work :
- ~80% implementation: Python code, using the common scientific programming libraries and Pyxu [3]
- ~20% theory: inverse problems, optimization, convergence of algorithms
(This repartition might be adapted according to the interests of the student.)
References: