Hauptnavigation

Pages about teaching are available in German only Zurück zu der Liste der Abschlussarbeiten

Graph induced Fused LASSO Signal Approximators

Title Graph induced Fused LASSO Signal Approximators
Registered On Dec 1, 2015 1:00:00 AM
Finished On Jan 1, 2016 1:00:00 AM
Description In machine learning, bioinformatics or other applied sciences where noisy data has to be processed, sparse regression has become quite popular. A lot of methods are based on optimizing an l1_norm regularizer called LASSO. This work is about the fused LASSO signal approximator (FLSA) given by the structure of a (weighted) graph. We want to find out how the best algorithms for FLSA look like when it comes to big data, from a theoretical and a practical point of view. Therefore we fist study optimality conditions to gain some knowledge about how an optimal solution looks like. It turns out that a dual formulation of the problem has some benefits. Then we describe two iterative approximation methods, one working in the primal and the other in the dual space. Next we focus on exact algorithms, in particular, we seek for possibilities to extend the dynamic programming algorithm for line graphs by Johnson [44] to more general graphs. For tree graphs we describe a new algorithm running in O(n log n) time and provide some good reasons why, for that kind of algorithm, this is an optimal time. Some experiments show that the algorithms indeed work in practice, illustrated by applying FLSA to denoise images. Yet, the proposed maximum gap tree approach is not sufficient alone. In the end we point out some ideas how to go on further: For instance, one could integrate dynamic programming approaches working in the primal to iterative approximations working in the dual space.
Status Abgeschlossen
Thesistype Masterthesis
Topic Machine Learning
Optimization
Assigned To Kuthe, Elias
Second Tutor Lee, Sangkyun