Contact: Adrian Jarret (LCAV)
Synopsis: Comparison of different LASSO solvers for the reconstruction of sparse signals in simulated contexts inspired from radio astronomy.
Level: Bachelor
Sections: IC
Description: The LASSO problem is an optimization problem broadly used nowadays to reconstruct sparse solutions to linear inverse problems. One of the most popular solvers for numerical applications is the Accelerated Proximal Gradient Descent, referred to as APGD. Although this algorithm enjoys very fast convergence rate, the update steps are generic and do not take into account the fact that the solutions of the problem are often sparse. This can lead to expensive and long computations in some practical situations.
When we know that there exists actual sparse solutions to the problems, we would like to use algorithms that exploit this prior knowledge to obtain more efficient reconstruction procedures. For that purpose, we have developed an algorithm called Polyatomic Frank-Wolfe (PFW), that has shown very promising results when sparse solutions of the LASSO are involved. Another candidate algorithm that has been reported to be very efficient in this context is known under the name of Coordinate Descent (CD). We would like to determine how this latter algorithm performs on LASSO problems with sparse solutions, compared to PFW and APGD, regarding execution time and memory requirements.
During this project, the student will have to discover and implement a version of CD for the LASSO problem. She/He will them evaluates the performances compared to the already implemented versions of the other algorithms on simulated setups inspired from radio astronomy problems (coding the simulations will also be part of the project). To do so, the student will rely on the optimization package Pycsou for Python , developed and maintained by the EPFL Center for Imaging in close collaboration with members of the lab.
Depending on the progress of the student, many follow-up tasks can be considered. One of them could be to use the solution of the previously solved LASSO problem as an initial grid-based candidate in order to warm start a subsequent solver for the recovery of the point sources in a continuous-domain, i.e. without any underlying grid. This two-step reconstruction procedure could allow to obtain grid-free solutions faster than running the second algorithm with arbitrary initial candidate.
Deliverables:
- Python code that implements simulations and a CD solver for the LASSO problem, along with quantitative comparisons of the algorithms
- Project report that presents the theoretical context and summarizes the experiments and the findings
Prerequisites:
- Basic knowledge in linear algebra (and functional analysis)
- Basic experience in numerical computing with Python (Numpy, Matplotlib)
- Any experience in (convex) optimization is a plus
Type of Work :
- ~70% implementation: Python coding
- ~30% theory: optimization, inverse problems, reconstruction of Dirac impulses
(This repartition might be adapted according to the interest of the student.)
References: