Supervisors info:
ΜΙχάλης Δρακόπουλος Επικ.Καθηγ. (Επιβλέπων), Λ. Ευαγελάτου-Δάλλα Αναπλ. Καθηγ., Σέργιος Θεοδωρίδης Καθηγ.
Summary:
An important branch of Applied Mathematics, which in recent decades experienced
rapid growth and continues to grow at even faster pace, is Optimization Theory.
An interesting application in the field of Informatics and Telecommunications
and particularly in signal transmission and processing, is the representation
of a data signal (sound, image or video) using a sparse vector transformation.
The sparse transformation of the initial signal is used so that the data is
processed and stored in a more economical way, especially since the size of the
data is constantly growing. The mathematical formulation of the problem is how
to solve a linear system of n equations and m unknowns nobtaining only sparse solutions, i.e. solutions to the linear system of
equations containing as many zero coordinates as possible.
The following work consists of two parts. In the beginning we define an
appropriate measure, suitable for the optimization problem. We prove that this
measure defines a metric and not a norm, resulting from the discrete metric
indeed. Because the problem is not solvable for any general matrix structure,
we define the conditions under which one could be suitable. We also use a
different formulation of the problem using a convex approximation of the
original measure and check the equivalence of the problems. In the second part
we take a practical approach of the problem. The problem is in general solved
using a variety of methods, we examine five basic methods. First we make the
three formulations of the problem and analyze the algorithms used in every
case. Finally, we check whether the theoretical results affect the process of
solving the problem in practice and test the quality of algorithmic procedures,
comparing one with another.
Keywords:
Sparse solutions, Underdetermined system of linear equations, Optimization algorithms, Signal processing, Compressed sensing
