TY - JOUR

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

AU - Moerkotte, Guido

AU - Montag, Martin

AU - Repetti, Audrey

AU - Steidl, Gabriele

PY - 2015/9

Y1 - 2015/9

N2 - 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.

AB - 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.

U2 - 10.1016/j.cam.2015.02.030

DO - 10.1016/j.cam.2015.02.030

M3 - Article

VL - 285

SP - 243

EP - 255

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

IS - C

ER -