Proximal Operator of Quotient Functions with Application to a Feasibility Problem in Query Optimization

Guido Moerkotte, Martin Montag, Audrey Repetti, Gabriele Steidl

Research output: Contribution to journalArticle

8 Citations (Scopus)

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 Q 1 , the proximity function is just a componentwise shrinkage function which we call q -shrinkage. This is similar to the proximity function of the ¿ 1 -norm which is given by componentwise soft shrinkage. For the maximum of quotients Q ∞ , the proximal function can be computed by first order primal-dual methods involving epigraphical projections.The proximity functions of Q ¿ , ¿ = 1 , ∞ are applied to solve convex problems of the form argmin x Q ¿ ( A x b ) subject to x ¿ 0 , 1 ¿ x ¿ 1 . Such problems are of interest in selectivity estimation for cost-based query optimizers in database management systems.
Original languageEnglish
Pages (from-to)243-255
Number of pages13
JournalJournal of Computational and Applied Mathematics
Volume285
Issue numberC
DOIs
Publication statusPublished - Sep 2015

Fingerprint Dive into the research topics of 'Proximal Operator of Quotient Functions with Application to a Feasibility Problem in Query Optimization'. Together they form a unique fingerprint.

Cite this