Lasso-Path and Taut String Algorithm for One-Dimensional Total Variation Regularization
MetadataVis full innførsel
In this thesis, we consider the minimization problem arising from a linear operator equation when applying Tikhonov regularization. In particular, we study the one-dimensional case with total variation penalization. We present two numerical methods for the reconstruction of the original function, both of which give exact results. The first is the taut string algorithm, for which we assume no linear transformation of the data. The second is a modified lasso-path algorithm, derived for the total variation regularization. The thesis focuses on the derivation of these algorithms. The taut string algorithm is of lower complexity than the lasso-path algorithm, but the trade off is that it is only applicable on non-transformed data and only computes the solution for a single regularization parameter. The lasso-path is applicable on all linear transformations, and computes the solution simultaneously for all regularization parameters in a given range. Finally, we test both of the algorithms with a few numerical experiments. We test the taut string algorithm for a block signal, and for moderate amount of noise we are able to reconstruct the signal. We test the lasso-path algorithm on the same block signal for different linear operator equations, in particular for moving averages and for random measurements. In general, when not too much noise is added, we are able to reconstruct the significant jumps of the original signal, although not exactly. For the random matrices, with fewer measurements than unknowns, the problem is more difficult, but we were able to find a good reconstruction if the number of jumps in the original signal were small enough.