| 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. |
