A new ADMM algorithm for the Euclidean median and its application to robust patch regression
This work addresses robust image denoising for applications like computer vision, but it is incremental as it improves upon an existing solver for a specific method.
The paper tackled the problem of computing the Euclidean Median (EM) for robust patch-based image denoising by proposing a novel ADMM algorithm with variable splitting and augmented Lagrangian, resulting in faster convergence compared to an existing solver.
The Euclidean Median (EM) of a set of points $Ω$ in an Euclidean space is the point x minimizing the (weighted) sum of the Euclidean distances of x to the points in $Ω$. While there exits no closed-form expression for the EM, it can nevertheless be computed using iterative methods such as the Wieszfeld algorithm. The EM has classically been used as a robust estimator of centrality for multivariate data. It was recently demonstrated that the EM can be used to perform robust patch-based denoising of images by generalizing the popular Non-Local Means algorithm. In this paper, we propose a novel algorithm for computing the EM (and its box-constrained counterpart) using variable splitting and the method of augmented Lagrangian. The attractive feature of this approach is that the subproblems involved in the ADMM-based optimization of the augmented Lagrangian can be resolved using simple closed-form projections. The proposed ADMM solver is used for robust patch-based image denoising and is shown to exhibit faster convergence compared to an existing solver.