Benchmarking of the Simplex Algorithm for Solving Regularized Inverse Problems
The simplex algorithm is the oldest but still one of the most popular optimization algorithms for solving linear programs. In short, it iterates through vertices of the feasible region of the linear program until it reaches a minimum of the cost function. Recently, it was been shown that it can be used to reach an extreme point of the solution set of inverse problems with l1 regularization [1]. This is relevant because these extreme point solutions are guaranteed to be sparse, i.e., they can be expressed with few nonzero coefficients [2]. Different methods can be applied to solve inverse problems with l1 regularization using the simplex, with different tradeoffs in terms of problem dimension, speed and perhaps numerical stability. The goal of this project is to benchmark these different methods in order to quantify the aforementioned tradeoffs. The student should have a strong interest in optimization.
References:
[1] Gupta, Harshit, Julien Fageot, and Michael Unser. "Continuous-Domain Solutions of Linear Inverse Problems with Tikhonov versus Generalized TV Regularization." IEEE Transactions on Signal Processing 66.17 (2018): 4670-4684.
[2] Unser, Michael, Julien Fageot, and Harshit Gupta. “Representer Theorems for Sparsity-Promoting l1 Regularization”, IEEE Transactions on Information Theory 62.9 (2016): 5167-5180.
© 2020 EPFL • webmaster.big@epfl.ch • 12.08.2020