Solving fused penalty estimation problems via block splitting algorithms

Abstract

We propose a method for solving a penalized estimation problem in which the penalty function is a function of differences between pairs of parameter vectors. In most cases such a penalty function is not separable in terms of the parameter vectors. This undesirable property often makes large scale estimation difficult with the penalty function. To solve the estimation problem in a separable way, we introduce a set of equality constraints that connect each parameter vector to a group of auxiliary variables. These auxiliary variables allow us to reformulate the estimation problem that is separable either in terms of the parameter vectors or in terms of the auxiliary variables. This separable property further facilitates us to solve the problem with an iterative scheme in that tasks within each iteration can be carried out separately in parallel. Our simulation results show that the iterative scheme has advantages over its traditional counterpart in terms of computational time and memory usage. Additional theoretical analysis shows that the iterative scheme can make the objective function approach to the optimal value with a convergence rate?$O(r^{-1})$, where $r$ is the iteration number.