A new median formula, fast coordinate descent for l1 minimization and applications to source detection.

摘要

ℓ¹ minimization is widely useful in all kinds of problem settings, yet there are interesting open problems and need for development in new applications. This thesis is focus on solving ℓ¹ related optimization problems by using coordinate descent methods. We develop close-forms to obtain solutions for one dimensional subproblems, then adopt suitable sweep pattern to perform the best for specific applications of different ℓ¹ related energy functions. For applications, we are focus on solving ROF (Rudin-Osher-Fatemi) denoising [1] and nonlocal TV denoising [12]. We also worked on compressed sensing problems [27] and the heat source identification problem [49].;In Chapter 1, we develop a simple algorithm for finding the minimizer of the function E(x) = ni=1 wi|x - ai| + F(x), when the wi are nonnegative and F is strictly convex. If F is also differentiablie and F' is bijective, we obtain an explicit formula in terms of a median. Combining with coordinate descent, this enables us to obtain approximate solutions to certain important variational problems arising in image denoising. We also present a generalization with E(x) = J(x) + F(x) for J(x) a convex piecewise differentiable function with a finite number of nondifferentiable points.;In Chapter 2, we propose a fast algorithm for solving Basis Pursuit min u{|u|1 : Au = f} [4], winch has an application to compressed sensing [27]. We design an efficient method for solving the related unconstrained problem min u E(u) = |u|1+lambda|| Au - f|| 22 based on a greedy coordinate descent method. We claim that in combination with a Bregman iterative method [44], our algorithm will achieve a solution with speed and accuracy competitive with some of the leading methods for Basis Pursuit.;The last but not the least, we consider heat source identification problems in Chapter 3. We use the same ℓ0 → ℓ¹ technique from compressed sensing, and combine with the same greedy coordinate descent method from Chapter 2 to recover heat sources. Moreover, we propose an online sampling setting better than random sampling for finding heat sources.