An overview of sparse convex optimization

Abstract

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. Optimization is seeking values of a variable that leads to an optimal value of the function that is to be optimized. Suppose we have a system of equations where there more unknowns than the equations. This type of system leads to an infinitely many solution. If one has prior knowledge that the solution is sparse this problem can be treated as an optimization problem. In this mini-dissertation we will discuss the convex algorithms for finding sparse solution. We use convex algorithm are chosen since they are relatively easy to implement. The class of methods we will discuss are convex relaxation, greedy algorithms and iterative thresholding. We will then compare this algorithms by applying them to a Sudoku problem.