English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Generalized Proximity and Projection with Norms and Mixed-norms

Sra, S.(2010). Generalized Proximity and Projection with Norms and Mixed-norms (192). Tübingen, Germany: Max Planck Institute for Biological Cybernetics.

Item is

Files

show Files
hide Files
:
MPIK-TR-192_6518[0].pdf (Publisher version), 389KB
Name:
MPIK-TR-192_6518[0].pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Sra, S1, 2, Author              
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s):
 Dates: 2010-05
 Publication Status: Published in print
 Pages: 13
 Publishing info: Tübingen, Germany : Max Planck Institute for Biological Cybernetics
 Table of Contents: -
 Rev. Type: -
 Identifiers: Report Nr.: 192
BibTex Citekey: 6518
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Technical Report of the Max Planck Institute for Biological Cybernetics
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 192 Sequence Number: - Start / End Page: - Identifier: -