@techreport{6518,
  title = {Generalized Proximity and Projection with Norms and Mixed-norms},
  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.},
  number = {192},
  organization = {Max-Planck-Gesellschaft},
  institution = {Max Planck Institute for Biological Cybernetics, Tübingen, Germany},
  school = {Biologische Kybernetik},
  month = may,
  year = {2010},
  slug = {6518},
  author = {Sra, S.},
  month_numeric = {5}
}