Item

Abstract

We discuss generalized proximity operators (GPO) and their associated generalized projection problems.
On inputs of size n, we show how to efficiently apply GPOs and generalized projections for separable
norms and distance-like functions to accuracy e in O(n log(1/e)) time. We also derive projection algorithms that
run theoretically in O(n log n log(1/e)) time but can for suitable parameter ranges empirically outperform the
O(n log(1/e)) projection method. The proximity and projection tasks are either separable, and solved directly, or
are reduced to a single root-finding step. We highlight that as a byproduct, our analysis also yields an O(n log(1/e))
(weakly linear-time) procedure for Euclidean projections onto the l1;1-norm ball; previously only an O(n log n)
method was known. We provide empirical evaluation to illustrate the performance of our methods, noting that
for the l1;1-norm projection, our implementation is more than two orders of magnitude faster than the previously
known method.