Proximal operator of quotient functions with application to a feasibility problem in query optimization

Moerkotte, Guido ; Montag, Martin ; Repetti, Audrey ; Steidl, Gabriele

Additional URL:
Document Type: Article
Year of publication: 2015
The title of a journal, publication series: Journal of Computational and Applied Mathematics
Volume: 285
Page range: 243-255
Place of publication: Amsterdam [u.a.]
Publishing house: North Holland ; Elsevier
ISSN: 0771-050X , 0377-0427
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik III (Moerkotte)
Subject: 004 Computer science, internet
Keywords (English): Proximal operators ; Epigraphical projections ; Primal–dual algorithm ; Alternating direction method of multipliers ; Feasibility problem ; Query optimization in database management systems
Abstract: In this paper we determine the proximity functions of the sum and the maximum of componentwise (reciprocal) quotients of positive vectors. For the sum of quotients, denoted by Q1Q1, the proximity function is just a componentwise shrinkage function which we call qq-shrinkage. This is similar to the proximity function of the ℓ1ℓ1-norm which is given by componentwise soft shrinkage. For the maximum of quotients Q∞Q∞, the proximal function can be computed by first order primal–dual methods involving epigraphical projections. The proximity functions of QνQν, ν=1,∞ν=1,∞ are applied to solve convex problems of the form View the MathML sourceargminxQν(Axb) subject to x≥0x≥0, View the MathML source1⊤x≤1. Such problems are of interest in selectivity estimation for cost-based query optimizers in database management systems.

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item