A new ADMM algorithm for the Euclidean median and its application to robust patch regression
The Euclidean Median (EM) of a set of points $\Omega$ in an Euclidean space is the point x minimizing the (weighted) sum of the Euclidean distances of x to the points in $\Omega$. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
DenoisingImage DenoisingregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean $k$-median and $k$-means problems. We propose a new primal-dual algorithm, inspired by the classic algorith…
A Distributed Algorithm for Measure-valued Optimization with Additive Objective
We propose a distributed nonparametric algorithm for solving measure-valued optimization problems with additive objectives. Such problems arise in several contexts in stochastic learning and control including Langevin sa…
Hardness of Approximation of Euclidean $k$-Median
The Euclidean $k$-median problem is defined in the following manner: given a set $\mathcal{X}$ of $n$ points in $\mathbb{R}^{d}$, and an integer $k$, find a set $C \subset \mathbb{R}^{d}$ of $k$ points (called centers) s…
Bregman Alternating Direction Method of Multipliers
The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers …
GPULinking convolutional neural networks with graph convolutional networks: application in pulmonary artery-vein separation
Graph Convolutional Networks (GCNs) are a novel and powerful method for dealing with non-Euclidean data, while Convolutional Neural Networks (CNNs) can learn features from Euclidean data such as images. In this work, we …
3D Medical Imaging SegmentationMedical Image SegmentationPulmonary Artery–Vein ClassificationPulmorary Vessel Segmentation