---
abstract: 'Perspective functions arise explicitly or implicitly in various forms in applied mathematics and in statistical data analysis. To date, no systematic strategy is available to solve the associated, typically nonsmooth, optimization problems. In this paper, we fill this gap by showing that proximal methods provide an efficient framework to model and solve problems involving perspective functions. We study the construction of the proximity operator of a perspective function under general assumptions and present important instances in which the proximity operator can be computed explicitly or via straightforward numerical operations. These results constitute central building blocks in the design of proximal optimization algorithms. We showcase the versatility of the framework by designing novel proximal algorithms for state-of-the-art regression and variable selection schemes in high-dimensional statistics.'
author:
- |
    Patrick L. Combettes$^1$ and Christian L. Müller$^2$\
    $\!^1$North Carolina State University\
    Department of Mathematics\
    Raleigh, NC 27695-8205, USA\
    [[](mailto:plc@math.ncsu.edu)]{}\
    $\!^2$Flatiron Institute\
    Simons Foundation\
    New York, NY 10010, USA\
    [[](mailto:cmueller@simonsfoundation.org)]{}
date:  
title: 'Perspective Functions: Proximal Calculus and Applications in High-Dimensional Statistics[^1]'
---

Introduction
============

Perspective functions appear, often implicitly, in various problems in areas as diverse as statistics, control, computer vision, mechanics, game theory, information theory, signal recovery, transportation theory, machine learning, disjunctive optimization, and physics (see the companion paper [@Scda16a] for a detailed account). In the setting of a real Hilbert space ${\ensuremath{{\mathcal G}}}$, the most useful form of a perspective function, first investigated in Euclidean spaces in [@Rock70], is the following.

\[d:perspective\] Let $\varphi\colon{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}$ be a proper lower semicontinuous convex function and let ${\ensuremath{\text{\rm rec}\,}}\varphi$ be its recession function. The perspective of $\varphi$ is $$\label{eevU74gdnx-08l}
\widetilde{\varphi}\colon{\ensuremath{\mathbb{R}}}\times{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon 
(\eta,y)\mapsto
\begin{cases}
\eta\varphi(y/\eta),&\text{if}\;\;\eta>0;\\
({\ensuremath{\text{\rm rec}\,}}\varphi)(y),&\text{if}\;\;\eta=0;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;\eta<0.
\end{cases}$$

Many scientific problems result in minimization problems that involve perspective functions. In statistics, a prominent instance is the modeling of data via “maximum likelihood-type" estimation (or M-estimation) with a so-called concomitant parameter [@Huber1981]. In this context, $\varphi$ is a likelihood function, $\eta$ takes the role of the concomitant parameter, e.g., an unknown scale or location of the assumed parametric distribution, and $y$ comprises unknown regression coefficients. The statistical problem is then to simultaneously estimate the concomitant variable and the regression vector from data via optimization. Another important example in statistics [@Fish25], signal recovery [@Borw96], and physics [@Frie07] is the Fisher information of a function $x\colon{\ensuremath{\mathbb{R}}}^N\to{\ensuremath{\left]0,+\infty\right[}}$, namely $$\label{e:fisher}
\int_{{\ensuremath{\mathbb{R}}}^N}\frac{\|\nabla x(t)\|_2^2}{x(t)}dt,$$ which hinges on the perspective function of the squared Euclidean norm (see [@Scda16a] for further discussion).

In the literature, problems involving perspective functions are typically solved with a wide range of ad-hoc methods. Despite the ubiquity of perspective functions, no systematic structuring framework has been available to approach these problems. The goal of this paper is to fill this gap by showing that they are amenable to solution by proximal methods, which offer a broad array of splitting algorithms to solve complex nonsmooth problems with attractive convergence guarantees [@Livre1; @MaPr16; @Siop15; @Facc03]. The central element in the successful implementation of a proximal algorithm is the ability to compute the proximity operator of the functions present in the optimization problem. We therefore propose a systematic investigation of proximity operators for perspective functions and show that the proximal framework can efficiently solve perspective-function based problems, unveiling in particular new applications in high-dimensional statistics.

In Section \[sec:2\], we introduce basic concepts from convex analysis and review essential properties of perspective function. We then study the proximity operator of perspective functions in Sections \[sec:3\]. We establish a characterization of the proximity operator and then provide examples of computation for concrete instances. Section \[sec:4\] unveils new applications of perspective functions in high-dimensional statistics and demonstrates the flexibility and potency of the proposed framework to both model and solve complex problems in statistical data analysis.

Notation and background {#sec:2}
=======================

Notation and elements of convex analysis
----------------------------------------

Throughout, ${\ensuremath{{\mathcal H}}}$, ${\ensuremath{{\mathcal G}}}$, and ${\ensuremath{{\mathcal K}}}$ are real Hilbert spaces and ${\ensuremath{{\mathcal H}}}\oplus{\ensuremath{{\mathcal G}}}$ denotes their Hilbert direct sum. The symbol $\|\cdot\|$ denotes the norm of a Hilbert space and ${{\langle{{\cdot}\mid{\cdot}}\rangle}}$ the associated scalar product. The closed ball with center $x\in{\ensuremath{{\mathcal K}}}$ and radius $\rho\in{\ensuremath{\left]0,+\infty\right[}}$ is denoted by $B(x;\rho)$.

A function $f\colon{\ensuremath{{\mathcal K}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}$ is proper if ${\ensuremath{\text{\rm dom}\,}}f={\big\{{x\in{\ensuremath{{\mathcal K}}}}~\big |~{f(x)<{\ensuremath{{+\infty}}}}\big\}}\neq{\ensuremath{{\varnothing}}}$, coercive if $\lim_{\|x\|\to{\ensuremath{{+\infty}}}}f(x)={\ensuremath{{+\infty}}}$, and supercoercive if $\lim_{\|x\|\to{\ensuremath{{+\infty}}}}f(x)/\|x\|={\ensuremath{{+\infty}}}$. Denote by $\Gamma_0({\ensuremath{{\mathcal K}}})$ the class of proper lower semicontinuous convex functions from ${\ensuremath{{\mathcal K}}}$ to ${\ensuremath{\left]-\infty,+\infty\right]}}$, and let $f\in\Gamma_0({\ensuremath{{\mathcal K}}})$. The conjugate of $f$ is the function $$\label{e:conj}
f^*\colon{\ensuremath{{\mathcal K}}}\to{\ensuremath{\left[-\infty,+\infty\right]}}\colon u\mapsto\bigg(\sup_{x\in{\ensuremath{{\mathcal K}}}}
{{\langle{{x}\mid{u}}\rangle}}-f(x)\bigg).$$ It also belongs to $\Gamma_0({\ensuremath{{\mathcal K}}})$ and $f^{**}=f$. The subdifferential of $f$ is the set-valued operator $$\label{e:subdiff}
\partial f\colon{\ensuremath{{\mathcal K}}}\to 2^{\ensuremath{{\mathcal K}}}\colon x\mapsto 
{\big\{{u\in{\ensuremath{{\mathcal K}}}}~\big |~{(\forall y\in{\ensuremath{\text{\rm dom}\,}}f)\;\:
{{\langle{{y-x}\mid{u}}\rangle}}+f(x){\ensuremath{\leqslant}}f(y)}\big\}}.$$ We have $$\label{e:subdiff2}
(\forall x\in{\ensuremath{{\mathcal K}}})(\forall u\in{\ensuremath{{\mathcal K}}})\quad
u\in\partial f(x)\quad\Leftrightarrow\quad
x\in\partial f^*(u).$$ Moreover, $$\label{e:subdiff11}
(\forall x\in{\ensuremath{{\mathcal K}}})(\forall u\in{\ensuremath{{\mathcal K}}})\quad
f(x)+f^*(u){\ensuremath{\geqslant}}{{\langle{{x}\mid{u}}\rangle}}$$ and $$\label{e:subdiff12}
(\forall x\in{\ensuremath{{\mathcal K}}})(\forall u\in{\ensuremath{{\mathcal K}}})\quad
u\in\partial f(x)\quad\Leftrightarrow\quad
f(x)+f^*(u)={{\langle{{x}\mid{u}}\rangle}}.$$ If $f$ is Gâteaux differentiable at $x\in{\ensuremath{\text{\rm dom}\,}}f$ with gradient $\nabla f(x)$, then $$\label{e:2384572k}
\partial f(x)=\{\nabla f(x)\}.$$ Let $z\in{\ensuremath{\text{\rm dom}\,}}f$. The recession function of $f$ is $$\label{e4RJ3hjhhjeTr6p9-23a}
(\forall y\in{\ensuremath{{\mathcal K}}})\quad({\ensuremath{\text{\rm rec}\,}}f)(y)=
\sup_{x\in{\ensuremath{\text{\rm dom}\,}}f}\big(f(x+y)-f(y)\big)=\lim_{\alpha\to{\ensuremath{{+\infty}}}}
\frac{f(z+\alpha y)}{\alpha}.$$ The infimal convolution operation is denoted by ${\ensuremath{\mbox{\small$\,\square\,$}}}$. Now let $C$ be a subset of ${\ensuremath{{\mathcal K}}}$. Then $$\label{e:iota}
\iota_C\colon{\ensuremath{{\mathcal K}}}\to\{0,{\ensuremath{{+\infty}}}\}\colon x\mapsto
\begin{cases}
0,&\text{if}\;\;x\in C;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;x\notin C
\end{cases}$$ is the indicator function of $C$, $$\label{e:dictC}
d_C\colon{\ensuremath{{\mathcal K}}}\to{\ensuremath{\left[0,+\infty\right]}}\colon x\mapsto\inf\|C-x\|$$ is the distance function to $C$, and $$\label{e:support}
\sigma_C=\iota_C^*\colon{\ensuremath{{\mathcal K}}}\to{\ensuremath{\left[-\infty,+\infty\right]}}\colon u
\mapsto\sup_{x\in C}{{\langle{{x}\mid{u}}\rangle}}$$ is the support function of $C$. If $C$ is nonempty, closed, and convex then, for every $x\in{\ensuremath{{\mathcal K}}}$, there exists a unique point $P_Cx\in C$, called the projection of $x$ onto $C$, such that $\|x-P_Cx\|=d_C(x)$. We have $$\label{e:kolmogorov}
(\forall x\in{\ensuremath{{\mathcal K}}})(\forall p\in{\ensuremath{{\mathcal K}}})\quad
p=P_Cx\quad\Leftrightarrow\quad\big[\,p\in C\quad\text{and}\quad
(\forall y\in C)\quad{{\langle{{y-p}\mid{x-p}}\rangle}}{\ensuremath{\leqslant}}0\,\big].$$ The normal cone to $C$ is $$\label{e:nc}
N_C=\partial\iota_C\colon{\ensuremath{{\mathcal K}}}\to 2^{\ensuremath{{\mathcal K}}}\colon x\mapsto 
\begin{cases}
{\big\{{u\in{\ensuremath{{\mathcal K}}}}~\big |~{\sup{{\langle{{C-x}\mid{u}}\rangle}}{\ensuremath{\leqslant}}0}\big\}},
&\text{if}\;\;x\in C;\\
{\ensuremath{{\varnothing}}},&\text{otherwise.}
\end{cases}$$ For further background on convex analysis, see [@Livre1; @Rock70].

Proximity operators
-------------------

The proximity operator of $f\in\Gamma_0({\ensuremath{{\mathcal K}}})$ is $$\label{e:jjm1962}
{\ensuremath{\text{\rm prox}}}_f\colon{\ensuremath{{\mathcal K}}}\to{\ensuremath{{\mathcal K}}}\colon x\mapsto
\underset{y\in{\ensuremath{{\mathcal K}}}}{\text{argmin}}
\bigg(f(y)+\frac{1}{2}\|x-y\|^2\bigg).$$ This operator was introduced by Moreau in 1962 [@Mor62b] to model problems in unilateral mechanics. In [@Smms05], it was shown to play an important role in the investigation of various data processing problems, and it has become increasingly prominent in the general area of data analysis [@Banf11; @Wrig12]. We review basic properties and refer the reader to [@Livre1] for a more complete account.

Let $f\in\Gamma_0({\ensuremath{{\mathcal K}}})$. Then $$\label{e:jjm}
(\forall x\in{\ensuremath{{\mathcal K}}})(\forall p\in{\ensuremath{{\mathcal K}}})\quad
p={\ensuremath{\text{\rm prox}}}_{f}x\quad\Leftrightarrow\quad x-p\in\partial f(p).$$ If $C$ is a nonempty closed convex subset of ${\ensuremath{{\mathcal K}}}$, then $$\label{e:jjm4}
{\ensuremath{\text{\rm prox}}}_{f}=P_C.$$ Let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$. The Moreau decomposition of $x\in{\ensuremath{{\mathcal K}}}$ is $$\label{e:jjm3}
x={\ensuremath{\text{\rm prox}}}_{\gamma f}x+\gamma{\ensuremath{\text{\rm prox}}}_{f^*/\gamma}(x/\gamma).$$ The following facts will also be needed.

\[lkIjiiIus3W4-17\] Let $(\Omega,{\EuScript F},\mu)$ be a complete $\sigma$-finite measure space, let $\mathsf{K}$ be a separable real Hilbert space, and let $\psi\in\Gamma_0({\mathsf K})$. Suppose that ${\ensuremath{{\mathcal K}}}=L^2((\Omega,{\EuScript F},\mu);{\mathsf K})$ and that $\mu(\Omega)<{\ensuremath{{+\infty}}}$ or $\psi{\ensuremath{\geqslant}}\psi(0)=0$. Set $$\label{ekIjiiIus3W4-17A}
\begin{array}{lcll}
\Phi\colon&{\ensuremath{{\mathcal K}}}&\to&{\ensuremath{\left]-\infty,+\infty\right]}}\\[2mm]
&x&\mapsto&
\begin{cases}
{\displaystyle\int_\Omega}\psi\big(x(\omega)\big)\mu(d\omega),
&\;\;\text{if}\;\;\psi\circ x\in 
L^1\big((\Omega,{\EuScript F},\mu);{\ensuremath{\mathbb{R}}}\big);\\
{\ensuremath{{+\infty}}},&\;\;\text{otherwise.}
\end{cases}
\end{array}$$ Let $x\in{\ensuremath{{\mathcal K}}}$ and define, for $\mu$-almost every $\omega\in\Omega$, $p(\omega)={\ensuremath{\text{\rm prox}}}_{\psi} x(\omega)$. Then $p={\ensuremath{\text{\rm prox}}}_{\Phi}x$.

By [@Livre1 Proposition 9.32], $\Phi\in\Gamma_0({\ensuremath{{\mathcal K}}})$. Now take $x$ and $p$ in ${\ensuremath{{\mathcal K}}}$. Then it follows from and [@Livre1 Proposition 16.50] that $p(\omega)={\ensuremath{\text{\rm prox}}}_{\Phi}x(\omega)$$\mu$-a.e. $\Leftrightarrow$ $x(\omega)-p(\omega)\in
\partial\psi(p(\omega))$$\mu$-a.e. $\Leftrightarrow$ $x-p\in\partial \Phi(p)$. $\Leftrightarrow$ $p={\ensuremath{\text{\rm prox}}}_{\Phi}x$.

\[lQrs54tGhfnnUjH0-02\] Let $D\neq\{0\}$ be a nonempty closed convex subset of ${\ensuremath{{\mathcal K}}}$, let $x\in{\ensuremath{{\mathcal K}}}$, and let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$. Set $f=\|\cdot\|+\sigma_D$ and $C=\gamma D$. Then $$\label{eQrs54tGhfnnUjH0-02g}
{\ensuremath{\text{\rm prox}}}_{\gamma f}x=
\begin{cases}
0,&\text{if}\;\;d_{C}(x){\ensuremath{\leqslant}}\gamma;\\
\bigg(1-\dfrac{\gamma}{d_C(x)}\bigg)
\big(x-P_{C}x\big),&\text{if}\;\;d_{C}(x)>\gamma.
\end{cases}$$ If, in addition, $D$ is a cone and $K$ denotes its polar cone, then $f=\|\cdot\|+\iota_{K}$ and $$\label{eQrs54tGhfnnUjH0-03g}
{\ensuremath{\text{\rm prox}}}_{\gamma f}x=
\begin{cases}
0,&\text{if}\;\;\|P_{K}x\|{\ensuremath{\leqslant}}\gamma;\\
\bigg(1-\dfrac{\gamma}{\|P_{K}x\|}\bigg)
P_{K}x,&\text{if}\;\;\|P_{K}x\|>\gamma.
\end{cases}$$

Using elementary convex analysis, we obtain $$\label{eQrs54tGhfnnUjH0-02h}
f
=\iota^*_{B(0;1)}+\iota^*_D
=\big(\iota_{B(0;1)}{\ensuremath{\mbox{\small$\,\square\,$}}}\iota_D\big)^*
=\iota_{B(0;1)+D}^*
=\sigma_{B(0;1)+D}.$$ Hence, it follows from and that $$\label{eQrs54tGhfnnUjH0-02i}
{\ensuremath{\text{\rm prox}}}_{\gamma f}x
=x-\gamma{\ensuremath{\text{\rm prox}}}_{f^*/\gamma}(x/\gamma)
=x-\gamma P_{B(0;1)+D}(x/\gamma).$$ However by [@Livre1 Propositions 28.1(ii) and 28.10], $$\label{eQrs54tGhfnnUjH0-02j}
\gamma P_{B(0;1)+D}(x/\gamma)
=P_{B(0;\gamma)+C}\,x=
\begin{cases}
x,&\text{if}\;\;d_{C}(x){\ensuremath{\leqslant}}\gamma;\\
P_{C}x+\gamma\dfrac{x-P_{C}}{d_{C}(x)},
&\text{if}\;\;d_{C}(x)>\gamma.
\end{cases}$$ Upon combining and , we arrive at . Now suppose that, in addition, $D$ is a cone. Then $C=D$, $\sigma_D=\iota_{K}$, and yields ${\ensuremath{\operatorname{Id}}\,}-P_D=P_{K}$. Altogether, reduces to .

Perspective functions
---------------------

We review here some essential properties of perspective functions.

[[@Scda16a]]{} \[levU74gdnx-21\] Let $\varphi\in\Gamma_0({\ensuremath{{\mathcal G}}})$. Then the following hold:

1.  \[levU74gdnx-21ii\] $\widetilde{\varphi}$ is a positively homogeneous function in $\Gamma_0({\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}})$.

2.  \[levU74gdnx-21iii\] Let $C={\big\{{(\mu,u)\in{\ensuremath{\mathbb{R}}}\times{\ensuremath{{\mathcal G}}}}~\big |~{\mu+\varphi^*(u){\ensuremath{\leqslant}}0}\big\}}$. Then $(\widetilde{\varphi})^*=\iota_C$ and $\widetilde{\varphi}=\sigma_C$.

3.  \[levU74gdnx-21iii+\] Let $\eta\in{\ensuremath{\mathbb{R}}}$ and $y\in{\ensuremath{{\mathcal G}}}$. Then $$\label{ekIjiiIus3W9-23x}
    \partial\widetilde{\varphi}(\eta,y)=
    \begin{cases}
    {\big\{{\big(\varphi(y/\eta)-{{\langle{{y}\mid{u}}\rangle}}/\eta,u\big)}~\big |~{u\in\partial\varphi(y/\eta)}\big\}},&\text{if}\;\;\eta>0;\\
    {\big\{{(\mu,u)\in C}~\big |~{\sigma_{{\ensuremath{\text{\rm dom}\,}}\varphi^*}(y)={{\langle{{u}\mid{y}}\rangle}}}\big\}},
    &\text{if}\;\;\eta=0\;\text{and}\;y\neq 0;\\
    C,&\text{if}\;\;\eta=0\;\text{and}\;y=0;\\
    {\ensuremath{{\varnothing}}},&\text{if}\;\;\eta<0.
    \end{cases}$$

4.  \[levU74gdnx-21iv\] Suppose that ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open or that $\varphi$ is supercoercive, let $\eta\in{\ensuremath{\mathbb{R}}}$, and let $y\in{\ensuremath{{\mathcal G}}}$. Then $$\label{ekIjiiIus3W9-23y}
    \partial\widetilde{\varphi}(\eta,y)=
    \begin{cases}
    {\big\{{\big(\varphi(y/\eta)-{{\langle{{y}\mid{u}}\rangle}}/\eta,u\big)}~\big |~{u\in\partial\varphi(y/\eta)}\big\}},&\text{if}\;\;\eta>0;\\
    C,&\text{if}\;\;\eta=0\;\text{and}\;y=0;\\
    {\ensuremath{{\varnothing}}},&\text{otherwise.}
    \end{cases}$$

We refer to the companion paper [@Scda16a] for further properties of perspective functions as well as examples. Here are two important instances of (composite) perspective functions that will play a central role in Section \[sec:4\].

\[l:5th\] Let $L\colon{\ensuremath{{\mathcal H}}}\to{\ensuremath{{\mathcal G}}}$ be linear and bounded, let $r\in{\ensuremath{{\mathcal G}}}$, let $u\in{\ensuremath{{\mathcal H}}}$, let $\alpha\in{\ensuremath{\left]0,+\infty\right[}}$, let $\rho\in{\ensuremath{\mathbb{R}}}$, and let $q\in\left]1,{\ensuremath{{+\infty}}}\right[$. Set $$\label{ekIjiiIus3W9-24t}
f\colon{\ensuremath{{\mathcal H}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon x\mapsto
\begin{cases}
{\displaystyle{\frac{\|Lx-r\|^q}{\alpha|{{\langle{{x}\mid{u}}\rangle}}-\rho|^{q-1}}}},
&\text{if}\;\;{{\langle{{x}\mid{u}}\rangle}}>\rho;\\[3mm]
0,&\text{if}\;\;Lx=r\;\;\text{and}\;\;{{\langle{{x}\mid{u}}\rangle}}=\rho;\\
{\ensuremath{{+\infty}}},&\text{otherwise}
\end{cases}$$ and $A\colon{\ensuremath{{\mathcal H}}}\to{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\colon x\mapsto
({{\langle{{x}\mid{u}}\rangle}}-\rho,Lx-r)$. Then $f=[\,\|\cdot\|^q/\alpha]^\sim\circ A\in\Gamma_0({\ensuremath{{\mathcal H}}})$.

This is a special case of [@Scda16a Example 4.2].

[[@Scda16a Example 3.6]]{} \[levU74gdnx-27\] Let $\phi\in\Gamma_0({\ensuremath{\mathbb{R}}})$ be an even function, let $v\in{\ensuremath{{\mathcal G}}}$, let $\delta\in{\ensuremath{\mathbb{R}}}$, and set $$\label{eevU74gdnx-17A}
g\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon (\eta,y)\mapsto
\begin{cases}
\eta\phi(\|y\|/\eta)+{{\langle{{y}\mid{v}}\rangle}}+\delta\eta,&\text{if}\;\;\eta>0;\\
({\ensuremath{\text{\rm rec}\,}}\phi)(\|y\|)+{{\langle{{y}\mid{v}}\rangle}},
&\text{if}\;\;\eta=0;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;\eta<0.
\end{cases}$$ Then $g=[\phi\circ\|\cdot\|+\delta{{\langle{{\cdot}\mid{v}}\rangle}}]^\sim
\in\Gamma_0({\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}})$.

Proximity operator of a perspective function {#sec:3}
============================================

Main result
-----------

We start with a characterization of the proximity operator of a perspective function when ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open.

\[tevU74gdnx-06\] Let $\varphi\in\Gamma_0({\ensuremath{{\mathcal G}}})$, let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, let $\eta\in{\ensuremath{\mathbb{R}}}$, and let $y\in{\ensuremath{{\mathcal G}}}$. Then the following hold:

1.  \[tevU74gdnx-06i\] Suppose that $\eta+\gamma\varphi^*(y/\gamma){\ensuremath{\leqslant}}0$. Then ${\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=(0,0)$.

2.  \[tevU74gdnx-06ii\] Suppose that ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open and that $\eta+\gamma\varphi^*(y/\gamma)>0$. Then $$\label{e:DC2016-03-01a}
    {\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=
    \big(\eta+\gamma\varphi^*(p),y-\gamma p\big),$$ where $p$ is the unique solution to the inclusion $$\label{e:scdaJune2016}
    y\in\gamma p+\big(\eta+\gamma\varphi^*(p)\big)\partial\varphi^*(p).$$ If $\varphi^*$ is differentiable at $p$, then $p$ is characterized by $y=\gamma p+(\eta+\gamma\varphi^*(p))\nabla\varphi^*(p)$.

It follows from Lemma \[levU74gdnx-21\]\[levU74gdnx-21iii\] that $$\label{eqerY76t0k3-10a}
\widetilde{\varphi}=\sigma_C,\quad\text{where}\quad
C={\big\{{(\mu,u)\in{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}}~\big |~{\mu+\varphi^*(u){\ensuremath{\leqslant}}0}\big\}}.$$ Since $\varphi\in\Gamma_0({\ensuremath{{\mathcal G}}})$, we have $\varphi^*\in\Gamma_0({\ensuremath{{\mathcal G}}})$. Therefore, $C$ is a nonempty closed convex set. In turn, we derive from [@Siop07 Proposition 3.2] that ${\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}={\ensuremath{\text{\rm prox}}}_{\sigma_{\gamma C}}$ is a proximal thresholder on $\gamma C$ in the sense that $$\label{e:oulan}
(\forall\eta\in{\ensuremath{\mathbb{R}}})(\forall y\in{\ensuremath{{\mathcal G}}})\quad
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=(0,0)
\quad\Leftrightarrow\quad(\eta,y)\in\gamma C.$$

\[tevU74gdnx-06i\]: By and , $(\forall\eta\in{\ensuremath{\mathbb{R}}})(\forall y\in{\ensuremath{{\mathcal G}}})$ ${\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=(0,0)$ $\Leftrightarrow$ $\eta+\gamma\varphi^*(y/\gamma){\ensuremath{\leqslant}}0$.

\[tevU74gdnx-06ii\]: Set $(\chi,q)={\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)$ and $p=(y-q)/\gamma$. It follows from that $(\chi,q)\in{\ensuremath{\text{\rm dom}\,}}(\gamma\partial\widetilde{\varphi})$ and from that $(\chi,q)\neq(0,0)$. Hence, we deduce from Lemma \[levU74gdnx-21\]\[levU74gdnx-21iv\] that $\chi>0$. Furthermore, we derive from and Lemma \[levU74gdnx-21\]\[levU74gdnx-21iii+\] that $(\chi,q)$ is characterized by $$\label{ekIjiiIus3W9-16a}
\eta-\chi=\gamma\varphi(q/\chi)-{{\langle{{q/\chi}\mid{y-q}}\rangle}}
\quad\text{and}\quad y-q\in\gamma\partial\varphi(q/\chi),$$ i.e., $$\label{ekIjiiIus3W9-17a}
(\eta-\chi)/\gamma=\varphi(q/\chi)-{{\langle{{q/\chi}\mid{p}}\rangle}}
\quad\text{and}\quad p\in\partial\varphi(q/\chi).$$ However, asserts that $$\label{ekIjiiIus3W9-16b}
p\in\partial\varphi(q/\chi)\quad\Leftrightarrow\quad
\varphi(q/\chi)+\varphi^*(p)={{\langle{{q/\chi}\mid{p}}\rangle}}.$$ Hence, we derive from that $\varphi^*(p)=(\chi-\eta)/\gamma$, i.e., $$\label{ekIjiiIus3W9-17b}
\chi=\eta+\gamma\varphi^*(p).$$ Hence, by , $$\label{ekIjiiIus3W9-17c}
p\in\partial\varphi(q/\chi)\quad\Leftrightarrow\quad
q\in\chi\partial\varphi^*(p)\quad\Leftrightarrow\quad
y\in\gamma p+\big(\eta+\gamma\varphi^*(p)\big)\partial\varphi^*(p).$$ Altogether, we have established the characterization –, while the assertion concerning the differentiable case follows from .

\[rkIjiiIus3W6-17\] Here is an alternative proof of Theorem \[tevU74gdnx-06\]. It follows from Lemma \[levU74gdnx-21\]\[levU74gdnx-21iii\] that $$\label{eqerY76t0k3-10A}
\big(\widetilde{\varphi}\big)^*=\iota_C,\quad\text{where}\quad
C={\big\{{(\mu,u)\in{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}}~\big |~{\mu+\varphi^*(u){\ensuremath{\leqslant}}0}\big\}}$$ is a nonempty closed convex set. Hence, using and , we obtain $$\label{eqerY76t0k3-10b}
{\ensuremath{\text{\rm prox}}}_{\gamma \widetilde{\varphi}}(\eta,y)
=(\eta,y)-\gamma{\ensuremath{\text{\rm prox}}}_{\gamma^{-1}\widetilde{\varphi}^*}
\big(\eta/\gamma,y/\gamma\big)
=(\eta,y)-\gamma P_C\big(\eta/\gamma,y/\gamma\big)
=(\eta,y)-P_{\gamma C}\big(\eta,y\big).$$ Now set $(\pi,p)=P_C(\eta/\gamma,y/\gamma)$. We deduce from , , and that $(\pi,p)$ is characterized by $$\label{eevU74gdnx-12a}
\big(\eta/\gamma-\pi,y/\gamma-p\big)\in N_C(\pi,p).$$

\[tevU74gdnx-06i\]: We have $(\eta/\gamma,y/\gamma)\in C$. Hence, $(\pi,p)=(\eta/\gamma,y/\gamma)$ and yields ${\ensuremath{\text{\rm prox}}}_{\gamma \widetilde{\varphi}}(\eta,y)=(0,0)$.

\[tevU74gdnx-06ii\]: Set $h\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\mu,u)\mapsto\mu+\varphi^*(u)$. Then $C={{\ensuremath{{{{\operatorname{lev}}}_{{\ensuremath{\leqslant}}0}}\,}}}h$ and ${\ensuremath{\text{\rm dom}\,}}h={\ensuremath{\mathbb{R}}}\times{\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open. It therefore follows from [@Livre1 Proposition 6.43(ii)] that $$\label{ekIjiiIus3W9-15}
N_{{\ensuremath{\text{\rm dom}\,}}h}(\pi,p)=\{(0,0)\}.$$ Now let $z\in{\ensuremath{\text{\rm dom}\,}}\varphi^*$ and let $\zeta\in\left]{\ensuremath{{-\infty}}},-\varphi^*(z)\right[$. Then $h(\zeta,z)<0$. Therefore, we derive from [@Livre1 Lemma 26.17 and Proposition 16.8] and that $$\begin{aligned}
N_C(\pi,p)
&=
\begin{cases}
N_{{\ensuremath{\text{\rm dom}\,}}h}(\pi,p)\cup{\ensuremath{\text{\rm cone}\,}}\,\partial h(\pi,p),
&\text{if}\;\;\pi+\varphi^*(p)=0;\\
N_{{\ensuremath{\text{\rm dom}\,}}h}(\pi,p),&\text{if}\;\;\pi+\varphi^*(p)<0
\end{cases}\label{e:hj4mB}\\
&=
\begin{cases}
{\ensuremath{\text{\rm cone}\,}}\,\partial h(\pi,p),
&\text{if}\;\;\pi+\varphi^*(p)=0;\\
\{(0,0)\},&\text{if}\;\;\pi+\varphi^*(p)<0
\end{cases}\nonumber\\
&=
\begin{cases}
{\ensuremath{\text{\rm cone}\,}}\big(\{1\}\times\partial\varphi^*(p)\big),
&\text{if}\;\;\pi=-\varphi^*(p);\\
\{(0,0)\},&\text{if}\;\;\pi<-\varphi^*(p).
\label{eevU74gdnx-12b}
\end{cases}\end{aligned}$$ Hence, if $\pi<-\varphi^*(p)$, then yields $(\eta/\gamma-\pi,y/\gamma-p)=(0,0)$ and therefore $(\eta/\gamma,y/\gamma)=(\pi,p)\in C$, which is impossible since $(\eta/\gamma,y/\gamma)\notin C$. Thus, the characterization becomes $$\label{eevU74gdnx-12c}
\pi=-\varphi^*(p)\quad\text{and}\quad
({\ensuremath{\exists\,}}\nu\in{\ensuremath{\left]0,+\infty\right[}})({\ensuremath{\exists\,}}w\in\partial\varphi^*(p))\quad
\big(\eta/\gamma+\varphi^*(p),y/\gamma-p\big)=\nu(1,w)$$ that is, $y\in\gamma p+(\eta+\gamma\varphi^*(p))\partial\varphi^*(p)$.

\[rkIjiiIus3W9-17\] Let $\varphi\in\Gamma_0({\ensuremath{{\mathcal G}}})$ be such that ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open, let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, let $\eta\in{\ensuremath{\mathbb{R}}}$, and let $y\in{\ensuremath{{\mathcal G}}}$ be such that $\eta+\gamma\varphi^*(y/\gamma)>0$. We derive from that $y/\chi-q/\chi\in\partial(\gamma\varphi/\chi)(q/\chi)$ and then from that $q=\chi{\ensuremath{\text{\rm prox}}}_{\gamma\varphi/\chi}(y/\chi)$. Using , we can also write $q=y-{\ensuremath{\text{\rm prox}}}_{\chi\gamma\varphi^*(\cdot/\gamma)}y$. Hence, we deduce from Theorem \[tevU74gdnx-06\] the implicit relation $$\label{ekIjiiIus3W9-17x}
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=
\chi\left(1,{\ensuremath{\text{\rm prox}}}_{\gamma\varphi/\chi}(y/\chi)\right),
\quad\text{where}\quad\chi=\eta+\gamma\varphi^*
\bigg(\frac{{\ensuremath{\text{\rm prox}}}_{\chi\gamma\varphi^*(\cdot/\gamma)}y}{\gamma}
\bigg).$$

The next example is based on distance functions.

\[exevU74gdnx-17a\] Let $\varphi=\phi\circ d_D$, where $D=B(0;1)\subset{\ensuremath{{\mathcal G}}}$ and $\phi\in\Gamma_0({\ensuremath{\mathbb{R}}})$ is an even function such that $\phi(0)=0$ and $\phi^*$ is differentiable on ${\ensuremath{\mathbb{R}}}$. It follows from [@Livre1 Examples 13.3(iv) and 13.23] that $\varphi^*=\|\cdot\|+\phi^*\circ\|\cdot\|$. Note that, since $\varphi$ and $\phi$ are even and satisfy $\varphi(0)=0$ and $\phi(0)=0$, $\varphi^*$ and $\phi^*$ are even and satisfy $\varphi^*(0)=0$ and $\phi^*(0)=0$ as well by [@Livre1 Propositions 13.18 and 13.19]. In turn, $\phi^{*'}(0)=0$ and we therefore derive from [@Livre1 Corollary 16.38(iii) and Example 16.25] that $$\label{e:subnorm}
(\forall u\in{\ensuremath{{\mathcal G}}})\quad\partial\varphi^*(u)=
\begin{cases}
\bigg\{\dfrac{1+\phi^{*'}(\|u\|)}{\|u\|}u\bigg\},
&\text{if}\;\;u\neq 0;\\
B(0;1),&\text{if}\;\;u=0.
\end{cases}$$ We have ${\ensuremath{\text{\rm dom}\,}}\varphi^*={\ensuremath{{\mathcal G}}}$ and, in view of Theorem \[tevU74gdnx-06\]\[tevU74gdnx-06ii\], we need only assume that $\eta+\gamma\varphi^*(y/\gamma)>0$, i.e., $$\label{eevU74gdnx-17a}
\eta+\|y\|+\gamma\phi^*(\|y\|/\gamma)>0.$$ Then and yield $$\label{eevU74gdnx-17b}
\begin{cases}
y=\gamma p+\Big(\eta+\gamma\big(\|p\|+\phi^*(\|p\|)\big)\Big)
\dfrac{1+\phi^{*'}(\|p\|)}{\|p\|}p,&\text{if}\;\;p\neq 0;\\
\|y\|{\ensuremath{\leqslant}}\eta,&\text{if}\;\;p=0.
\end{cases}$$ In view of Remark \[rkIjiiIus3W6-17\], the normal cone to the set $C$ of at $(0,0)$ is $$K={\big\{{(\eta,y)\in{\ensuremath{\left[0,+\infty\right[}}\times{\ensuremath{{\mathcal G}}}}~\big |~{\|y\|{\ensuremath{\leqslant}}\eta}\big\}}.$$ So, for every $(\eta,y)\in K$, $P_C(\eta/\gamma,y/\gamma)=(0,0)$ and ${\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=(\eta,y)$. Now suppose that $(\eta,y)\notin K$. Then $p\neq 0$ and, taking the norm in the upper line of , we obtain $$\label{eevU74gdnx-17c}
\gamma\|p\|+\Big(\eta+\gamma\big(\|p\|+\phi^*(\|p\|)\big)\Big)
\big(1+\phi^{*'}(\|p\|)\big)=\|y\|.$$ Set $$\label{eevU74gdnx-17x}
\psi\colon s\mapsto
s+\bigg(\dfrac{\eta}{\gamma}+s+\phi^*(s)\bigg)
\big(1+\phi^{*'}(s)\big)-\frac{\|y\|}{\gamma}$$ and define $$\label{eevU74gdnx-16x}
\theta\colon s\mapsto{\displaystyle{\frac{1}{2}}}\bigg(
\bigg(\frac{\eta}{\gamma}+s+\phi^*(s)\bigg)^2+s^2\bigg)
-\frac{\|y\|s}{\gamma}.$$ Since $\phi^*$ is convex, $\theta$ is strongly convex and it therefore admits a unique minimizer $t$. Therefore $\psi(t)=\theta'(t)=0$ and $\|p\|=t=\psi^{-1}(\|y\|/\gamma)$ is the unique solution to . In turn, yields $$p=\frac{t}{\|y\|+\gamma\psi(t)}y,$$ and we obtain ${\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)$ via .

Next, we compute the proximity operator of a special case of the perspective function introduced in Lemma \[levU74gdnx-27\].

\[cevU74gdnx-29a\] Let $v\in{\ensuremath{{\mathcal G}}}$, let $\delta\in{\ensuremath{\mathbb{R}}}$, and let $\phi\in\Gamma_0({\ensuremath{\mathbb{R}}})$ be an even function such that $\phi(0)=0$ and $\phi^*$ is differentiable on ${\ensuremath{\mathbb{R}}}$. Define $$\label{eevU74gdnx-13a}
g\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon (\eta,y)\mapsto
\begin{cases}
\eta\phi(\|y\|/\eta)+\delta\eta+{{\langle{{y}\mid{v}}\rangle}},&\text{if}\;\;\eta>0;\\
0,&\text{if}\;\;y=0\;\;\text{and}\;\;\eta=0;\\
{\ensuremath{{+\infty}}},&\text{otherwise.}
\end{cases}$$ Let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, let $\eta\in{\ensuremath{\mathbb{R}}}$, let $y\in{\ensuremath{{\mathcal G}}}$, and set $$\label{eevU74gdnx-15x}
\psi\colon
s\mapsto\bigg(\phi^*(s)+\frac{\eta}{\gamma}-\delta\bigg)
\phi^{*'}(s)+s.$$ Then $\psi$ is invertible. Moreover, if $\eta+\gamma\phi^*(\|y/\gamma-v\|)>\gamma\delta$, set $$\label{eevU74gdnx-13c}
t=\psi^{-1}\big(\|y/\gamma-v\|\big)
\quad\text{and}\quad p=
\begin{cases}
v+\dfrac{t}{\|y-\gamma v\|}(y-\gamma v),
&\text{if}\;\;y\neq\gamma v;\\
v,&\text{if}\;\;y=\gamma v.
\end{cases}$$ Then $$\label{eevU74gdnx-13d}
{\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=
\begin{cases}
\big(\eta+\gamma(\phi^*(t)-\delta),y-\gamma p\big),&\text{if}\;\;
\eta+\gamma\phi^*(\|y/\gamma-v\|)>\gamma\delta;\\
(0,0),&\text{if}\;\;
\eta+\gamma\phi^*(\|y/\gamma-v\|){\ensuremath{\leqslant}}\gamma\delta.
\end{cases}$$

This is a special case of Theorem \[tevU74gdnx-06\] with $\varphi=\phi\circ\|\cdot\|+\delta+{{\langle{{\cdot}\mid{v}}\rangle}}$. Indeed, as shown in [@Scda16a Example 3.6], is a special case of . Hence, we derive from Lemma \[levU74gdnx-27\] that $g=\widetilde{\varphi}\in\Gamma_0({\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}})$. Next, we obtain from [@Livre1 Example 13.7 and Proposition 13.20(iii)] that $$\label{eevU74gdnx-29c}
\varphi^*=\phi^*\circ\|\cdot-v\|-\delta$$ and therefore that $$\label{eevU74gdnx-29t}
\nabla\varphi^*\colon{\ensuremath{{\mathcal G}}}\to{\ensuremath{{\mathcal G}}}\colon z\mapsto
\begin{cases}
\dfrac{\phi^{*'}(\|z-v\|)}{\|z-v\|}(z-v),&\text{if}\;\;z\neq v;\\
0,&\text{if}\;\;z=v.
\end{cases}$$ In view of Theorem \[tevU74gdnx-06\], it remains to assume that $\eta+\gamma\varphi^*(y/\gamma)>0$, i.e., $\eta+\phi^*(\|y/\gamma-v\|)>\gamma\delta$, and to show that the point $(t,p)$ provided by satisfies $$\label{eDACy47Hj-10v}
t=\|p-v\|\quad\text{and}\quad
y=\gamma p+\big(\eta+\gamma\varphi^*(p)\big)\nabla\varphi^*(p).$$ We consider two cases:

-   $y=\gamma v$: Since $\phi$ is an even convex function such that $\phi(0)=0$, $\phi^*$ has the same properties by [@Livre1 Propositions 13.18 and 13.19]. Hence, going back to Remark \[rkIjiiIus3W6-17\], since $\phi^*$ is differentiable, the points that have $(\pi,p)=(\delta,v)$ as a projection onto $C={\big\{{(\mu,u)\in{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}}~\big |~{\mu+\phi^*(\|u-v\|){\ensuremath{\leqslant}}\delta}\big\}}$ are the points on the ray ${\big\{{(\delta+\lambda,v)}~\big |~{\lambda\in{\ensuremath{\left[0,+\infty\right[}}}\big\}}$. Thus, we derive from that $$\begin{gathered}
    \label{eDACy47Hj-10a}
    y=\gamma v\;\Leftrightarrow\;
    P_C(\eta/\gamma,y/\gamma)=(\pi,p)=(\delta,v)
    \;\Leftrightarrow\;\;p=v\Leftrightarrow\;t=0\;\Leftrightarrow\;\\
    {\ensuremath{\text{\rm prox}}}_{\gamma \widetilde{\varphi}}(\eta,y)
    =(\eta,y)-\gamma(\delta,v)=(\eta-\gamma\delta,y-\gamma p).\end{gathered}$$ Since $\phi^*(0)=0$, we recover .

-   $y\neq\gamma v$: As seen in , $p\neq v$. Using and , can be rewritten as $$\label{eevU74gdnx-29d}
    t=\|p-v\|\quad\text{and}\quad y-\gamma v=
    \gamma(p-v)+\frac{\big(\eta+\gamma\phi^*(\|p-v\|)-\gamma\delta\big)
    \phi^{*'}(\|p-v\|)}{\|p-v\|}(p-v),$$ that is, $$\label{eevU74gdnx-29z}
    t=\|p-v\|\quad\text{and}\quad y/\gamma-v=
    \frac{\|p-v\|+\big(\eta/\gamma-\delta+\phi^*(\|p-v\|)\big)
    \phi^{*'}(\|p-v\|)}{\|p-v\|}(p-v).$$ In view of , this is equivalent to $$\label{eevU74gdnx-30b}
    t=\|p-v\|\quad\text{and}\quad y/\gamma-v=
    \frac{\psi(\|p-v\|)}{\|p-v\|}(p-v).$$ Upon taking the norm on both sides of the second equality, we obtain $$\label{eevU74gdnx-30a}
    \psi(t)=\psi(\|p-v\|)=\|y/\gamma-v\|.$$ We note that, since $\phi^*$ is convex, $\psi$ is the derivative of the strongly convex function $$\label{eevU74gdnx-13g}
    \theta\colon s\mapsto\frac{1}{2}\Big(\phi^{*2}(s)+s^2\Big)+
    \bigg(\frac{\eta}{\gamma}-\delta\bigg)\phi^*(s).$$ Consequently, $\psi$ is strictly increasing [@Livre1 Proposition 17.13], hence invertible. It follows that $t=\psi^{-1}(\|y/\gamma-v\|)$. In turn, yields .

\[exevU74gdnx-15a\] Define $$\label{eevU74gdnx-15a}
g\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon (\eta,y)\mapsto
\begin{cases}
-\sqrt{\eta^2-\|y\|^2},&\text{if}\;\;\eta>0\;\;\text{and}\;\;
\|y\|{\ensuremath{\leqslant}}\eta;\\
0,&\text{if}\;\;y=0\;\;\text{and}\;\;\eta=0;\\
{\ensuremath{{+\infty}}},&\text{otherwise,}
\end{cases}$$ let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, let $\eta\in{\ensuremath{\mathbb{R}}}$, let $y\in{\ensuremath{{\mathcal G}}}$, and define $$\label{eevU74gdnx-15y}
\psi\colon s\mapsto\bigg(2+\frac{\eta}{\gamma\sqrt{1+s^2}}\bigg)s.$$ If $\eta+\sqrt{\gamma^2+\|y\|^2}>0$, set $$\label{eevU74gdnx-15i}
p=
\begin{cases}
\dfrac{t}{\|y\|}y,&\text{if}\;\;y\neq 0;\\
0,&\text{if}\;\;y=0,
\end{cases}
\qquad\text{where}\quad
t=\psi^{-1}\bigg(\frac{\|y\|}{\gamma}\bigg).$$ Then $$\label{eevU74gdnx-15d}
{\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=
\begin{cases}
\Big(\eta+\gamma\sqrt{1+t^2},y-\gamma p\Big),&\text{if}\;\;
\eta+\sqrt{\gamma^2+\|y\|^2}>0;\\
(0,0),&\text{if}\;\;
\eta+\sqrt{\gamma^2+\|y\|^2}{\ensuremath{\leqslant}}0.
\end{cases}$$

This is a special case of Corollary \[cevU74gdnx-29a\] with with $\delta=0$, $v=0$, and $$\label{eevU74gdnx-15b}
\phi\colon s\mapsto
\begin{cases}
-\sqrt{1-s^2},&\text{if}\;\;|s|{\ensuremath{\leqslant}}1;\\
{\ensuremath{{+\infty}}},&\text{otherwise.}
\end{cases}$$ It follows from [@Livre1 Example 13.2(vi) and Corollary 13.33] that $\phi^*\colon s\mapsto\sqrt{1+s^2}$. Hence, $\phi^{*'}\colon s\mapsto s/\sqrt{1+s^2}$ and we derive from .

\[exevU74gdnx-10a\] Let $v\in{\ensuremath{{\mathcal G}}}$, let $\delta\in{\ensuremath{\mathbb{R}}}$, let $\alpha\in{\ensuremath{\left]0,+\infty\right[}}$, let $q\in\left]1,{\ensuremath{{+\infty}}}\right[$, and consider the function $$\label{eevU74gdnx-10a}
g\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\eta,y)\mapsto
\begin{cases}
{\displaystyle{\frac{\|y\|^q}{\alpha\eta^{q-1}}}}+\delta\eta+{{\langle{{y}\mid{v}}\rangle}},
&\text{if}\;\;\eta>0; \\
0,&\text{if}\;\;y=0\;\text{and}\;\eta=0;\\
{\ensuremath{{+\infty}}}, &\text{otherwise.}
\end{cases}$$ Let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, set $q^*=q/(q-1)$, set $\varrho=(\alpha(1-1/q^*))^{q^*-1}$, and take $\eta\in{\ensuremath{\mathbb{R}}}$ and $y\in{\ensuremath{{\mathcal G}}}$. If $q^*\gamma^{q^*-1}\eta+\varrho\|y\|^{q^*}>\gamma\delta$ and $y\neq \gamma v$, let $t$ be the unique solution in ${\ensuremath{\left]0,+\infty\right[}}$ to the equation $$\label{eevU74gdnx-10f}
s^{2q^*-1}+\frac{q^*(\eta-\gamma\delta)}{\gamma\varrho}s^{q^*-1}
+\frac{q^*}{\varrho^2}s-\frac{q^*\|y-\gamma v\|}{\gamma\varrho^2}=0$$ and set $$\label{eevU74gdnx-10x}
p=
\begin{cases}
v+\dfrac{t}{\|y-\gamma v\|}(y-\gamma v),
&\text{if}\;\;y\neq\gamma v;\\
v,&\text{if}\;\;y=\gamma v.
\end{cases}$$ Then $$\label{eevU74gdnx-10b}
{\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=
\begin{cases}
\big(\eta+\gamma(\varrho t^{q^*}-\delta)/q^*,y-\gamma p\big),
&\text{if}\;\;q^*\gamma^{q^*-1}\eta+\varrho\|y\|^{q^*}
>\gamma\delta;\\
\big(0,0\big),&\text{if}\;\;q^*\gamma^{q^*-1}\eta+
\varrho\|y\|^{q^*}{\ensuremath{\leqslant}}\gamma\delta.
\end{cases}$$

This is a special case of Corollary \[cevU74gdnx-29a\] with $\phi=|\cdot|^q/\alpha$. Indeed, we derive from [@Livre1 Example 13.2(i) and Proposition 13.20(i)] that $\phi^*=\varrho|\cdot|^{q^*}/q^*$, which implies that – follow from .

\[exevU74gdnx-12a\] Let $v\in{\ensuremath{{\mathcal G}}}$, let $\alpha\in{\ensuremath{\left]0,+\infty\right[}}$, let $\delta\in{\ensuremath{\mathbb{R}}}$, and consider the function $$\label{eevU74gdnx-12x}
g\colon{\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\eta,y)\mapsto
\begin{cases}
{\displaystyle{\frac{\|y\|^2}{\alpha\eta}}}+\delta\eta+{{\langle{{y}\mid{v}}\rangle}},
&\text{if}\;\;\eta>0; \\
0, &\text{if}\;\;y=0\;\text{and}\;\eta=0;\\
{\ensuremath{{+\infty}}}, &\text{otherwise.}
\end{cases}$$ We obtain a special case of Example \[exevU74gdnx-10a\] with $q=q^*=2$. Now let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, and take $\eta\in{\ensuremath{\mathbb{R}}}$ and $y\in{\ensuremath{{\mathcal G}}}$. If $4\gamma\eta+\alpha\|y\|^2{\ensuremath{\leqslant}}2\gamma\delta$, then ${\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=(0,0)$. Suppose that $4\gamma\eta+\alpha\|y\|^2>2\gamma\delta$. First, if $y=\gamma v$, then ${\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=(\eta-\gamma\delta/2,0)$. Next, suppose that $y\neq\gamma v$ and let $t$ be the unique solution in ${\ensuremath{\left]0,+\infty\right[}}$ to the depressed cubic equation $$\label{eevU74gdnx-10p}
s^3+\frac{4\alpha(\eta-\gamma\delta)+8\gamma}{\alpha^2\gamma}s
-\frac{8\|y-\gamma v\|}{\alpha^2\gamma}=0.$$ Then we derive from – that $$\label{eDACy47Hj-13b}
{\ensuremath{\text{\rm prox}}}_{\gamma g}(\eta,y)=
\bigg(\eta+\dfrac{\gamma}{2}\bigg(\dfrac{\alpha
t^{2}}{2}-\delta\bigg),\bigg(1-
\dfrac{\gamma t}{\|y-\gamma v\|}\bigg)(y-\gamma v)\bigg).$$ Note that can be solved explicitly via Cardano’s formula [@Birk77 Chapter 4] to obtain $t$.

We conclude this subsection by investigating integral functions constructed from integrands that are perspective functions.

\[pkIjiiIus3W9-19\] Let $(\Omega,{\EuScript F},\mu)$ be a measure space, let ${\mathsf G}$ be a separable real Hilbert space, and let $\varphi\in\Gamma_0(\mathsf{G})$. Set ${\ensuremath{{\mathcal H}}}=L^2((\Omega,{\EuScript F},\mu);{\ensuremath{\mathbb{R}}})$ and ${\ensuremath{{\mathcal G}}}=L^2((\Omega,{\EuScript F},\mu);\mathsf{G})$, and suppose that $\mu(\Omega)<{\ensuremath{{+\infty}}}$ or $\varphi{\ensuremath{\geqslant}}\varphi(0)=0$. For every $x\in{\ensuremath{{\mathcal H}}}$, set $\Omega_0(x)={\big\{{\omega\in\Omega}~\big |~{x(\omega)=0}\big\}}$ and $\Omega_+(x)={\big\{{\omega\in\Omega}~\big |~{x(\omega)>0}\big\}}$. Define $$\begin{gathered}
\label{e:rodos2016-08-02b}
\Phi\colon{\ensuremath{{\mathcal H}}}\oplus{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon (x,y)\mapsto\\
\begin{cases}
\displaystyle{\int_{\Omega_0(x)}}
\big({\ensuremath{\text{\rm rec}\,}}\varphi\big)\big(y(\omega)\big)\mu(d\omega)\!\!\!&+
\displaystyle{\int_{\Omega_+(x)}}x(\omega)
\varphi\bigg(\dfrac{y(\omega)}{x(\omega)}\bigg)\mu(d\omega),\\[5mm]
&\text{if}\;\;
\begin{cases}
x{\ensuremath{\geqslant}}0\;\:\mu\text{-a.e.}\\
({\ensuremath{\text{\rm rec}\,}}\varphi)(y)1_{\Omega_0(x)}+x\varphi(y/x)1_{\Omega_+(x)}\in 
L^1\big((\Omega,\mathcal{F},\mu);{\ensuremath{\mathbb{R}}}\big);\\[3mm]
\end{cases}\\
{\ensuremath{{+\infty}}},&\text{otherwise.}
\end{cases}\end{gathered}$$ Now let $x\in{\ensuremath{{\mathcal H}}}$ and $y\in{\ensuremath{{\mathcal G}}}$, and set, for $\mu$-almost every $\omega\in\Omega$, $(p(\omega),q(\omega))=
{\ensuremath{\text{\rm prox}}}_{\widetilde{\varphi}} (x(\omega),y(\omega))$. Then ${\ensuremath{\text{\rm prox}}}_{\Phi} (x,y)=(p,q)$.

Set $z=(x,y)$. It follows from Lemma \[levU74gdnx-21\]\[levU74gdnx-21ii\] that $\widetilde{\varphi}\in\Gamma_0({\ensuremath{\mathbb{R}}}\oplus\mathsf{G})$, and [@Scda16a Proposition 5.1] asserts that $\Phi$ is a well-defined function in $\Gamma_0({\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}})$ with $$\label{e:245hg2}
\Phi(z)=\int_{\Omega}\widetilde{\varphi}\big(z(\omega)\big)
\mu(d\omega).$$ Therefore, the result is obtained by applying Lemma \[lkIjiiIus3W4-17\] with $\mathsf{K}={\ensuremath{\mathbb{R}}}\oplus\mathsf{G}$ and ${\ensuremath{{\mathcal K}}}={\ensuremath{{\mathcal H}}}\oplus{\ensuremath{{\mathcal G}}}$.

\[rkIjiiIus3W9-19\] Proposition \[pkIjiiIus3W9-19\] provides a general setting for computing the proximity operators of abstract integral functionals by reducing it to the computation of the proximity operator of the integrand. In particular, by suitably choosing the underlying measure space and the integrand, it provides a framework for computing the proximity operators of the integral function based on perspective functions discussed in [@Scda16a], which include general divergences. For instance, discrete $N$-dimensional divergences are obtained by setting $\Omega=\{1,\ldots,N\}$ and $\mathcal{F}=2^\Omega$, and letting $\mu$ be the counting measure (hence ${\ensuremath{{\mathcal H}}}={\ensuremath{{\mathcal G}}}={\ensuremath{\mathbb{R}}}^N$) and $\mathsf{G}={\ensuremath{\mathbb{R}}}$. While completing the present paper, it has come to our attention that the computation of the proximity operators of discrete divergences has also been recently addressed in [@Pesq16].

Further results {#subsec:further}
---------------

A convenient assumption in Theorem \[tevU74gdnx-06\]\[tevU74gdnx-06ii\] is that ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is open, as it allowed us to rule out the case when $$\label{eQrs54tGhfnnUjH0-09a}
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=(0,q)
\quad\text{and}\quad q\neq 0,$$ and to reduce to using . In general, has the form $N_{{\ensuremath{\text{\rm dom}\,}}h}(\pi,p)=\{0\}\times N_{{\ensuremath{\text{\rm dom}\,}}\varphi^*}p$ and, if ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is simple enough, explicit expressions can still be obtained. To shed more light on the case , consider the scenario in which $q\neq 0$ and ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is closed, and set $p=(y-q)/\gamma$. Then, in view of , yields $(\eta/\gamma,p)\in\partial\widetilde{\varphi}(0,q)$. In turn, we derive from that $$\label{eQrs54tGhfnnUjH0-09b}
\varphi^*(p){\ensuremath{\leqslant}}-\eta/\gamma\quad\text{and}\quad
\sigma_{{\ensuremath{\text{\rm dom}\,}}\varphi^*}(q)={{\langle{{p}\mid{q}}\rangle}}.$$ Thus, $$\label{eQrs54tGhfnnUjH0-09c}
p\in {{\ensuremath{\text{\rm dom}\,}}\varphi^*}\quad\text{and}\quad
(\forall z\in {{\ensuremath{\text{\rm dom}\,}}\varphi^*})\quad
{{\langle{{z-p}\mid{y/\gamma-p}}\rangle}}{\ensuremath{\leqslant}}0,$$ and we infer from that $p=P_{{\ensuremath{\text{\rm dom}\,}}\varphi^*}(y/\eta)$. Therefore, $$\label{eQrs54tGhfnnUjH0-09e}
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=
\big(0,y-\gamma P_{{\ensuremath{\text{\rm dom}\,}}\varphi^*}(y/\eta)\big)=
\big(0,y-P_{\gamma{\ensuremath{\text{\rm dom}\,}}\varphi^*}y\big)$$ and we note that the condition $q\neq 0$ means that $y\notin\gamma\,{{\ensuremath{\text{\rm dom}\,}}\varphi^*}$. We provide below examples in which ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is a simple proper closed subset of ${\ensuremath{{\mathcal G}}}$ and the proximity operator of the perspective function of $\varphi$ can be computed explicitly.

\[exQrs54tGhfnnUjH0-01\] Suppose that $D\neq\{0\}$ is a nonempty closed convex cone in ${\ensuremath{{\mathcal G}}}$ and define $$\label{eQrs54tGhfnnUjH0-03p}
\varphi=\vartheta+\iota_D,\quad\text{where}\quad
\vartheta=\sqrt{1+\|\cdot\|_{{\ensuremath{{\mathcal G}}}}^2}.$$ Since ${\ensuremath{\text{\rm dom}\,}}\vartheta={\ensuremath{{\mathcal G}}}$, we have $\varphi^*=(\vartheta+\iota_D)^*
=\vartheta^*{\ensuremath{\mbox{\small$\,\square\,$}}}\iota_{D^\ominus}$, where $D^\ominus$ is the polar cone of $D$ and (combine [@Livre1 Examples 13.2(vi) and 13.7]) $$\label{eQrs54tGhfnnUjH0-01b}
\vartheta^*\colon{\ensuremath{{\mathcal G}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon u\mapsto
\begin{cases}
-\sqrt{1-\|u\|_{\ensuremath{{\mathcal G}}}^2},&\text{if}\;\;\|u\|_{\ensuremath{{\mathcal G}}}{\ensuremath{\leqslant}}1;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;\|u\|_{\ensuremath{{\mathcal G}}}>1.
\end{cases}$$ Thus, ${\ensuremath{\text{\rm dom}\,}}\varphi^*={\ensuremath{\text{\rm dom}\,}}(\vartheta^*{\ensuremath{\mbox{\small$\,\square\,$}}}\iota_{D^\ominus})
={\ensuremath{\text{\rm dom}\,}}\vartheta^*+{\ensuremath{\text{\rm dom}\,}}\iota_{D^\ominus}=B(0;1)+D^\ominus$ is closed as the sum of two closed convex sets, one of which is bounded. As a result, since $D^\ominus\neq{\ensuremath{{\mathcal G}}}$, $$\label{eQrs54tGhfnnUjH0-03w}
{\ensuremath{\text{\rm dom}\,}}\varphi^*\;\text{is a proper closed subset of}\;{\ensuremath{{\mathcal G}}}.$$ Now set ${\ensuremath{{\mathcal K}}}={\ensuremath{\mathbb{R}}}\oplus{\ensuremath{{\mathcal G}}}$ and $K={\ensuremath{\left[0,+\infty\right[}}\times D$, and let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, $\eta\in{\ensuremath{\mathbb{R}}}$, and $y\in{\ensuremath{{\mathcal G}}}$. Then $\|(\eta,y)\|_{\ensuremath{{\mathcal K}}}=\sqrt{|\eta|^2+\|y\|_{\ensuremath{{\mathcal G}}}^2}$ and, as shown in [@Scda16a Example 3.5], $$\label{eQrs54tGhfnnUjH0-03u}
\widetilde{\varphi}=\|\cdot\|_{\ensuremath{{\mathcal K}}}+\iota_K.$$ Hence, we derive from that $$\label{eQrs54tGhfnnUjH0-03x}
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=
\begin{cases}
(0,0),&\text{if}\;\;\|P_{K}(\eta,y)\|_{\ensuremath{{\mathcal K}}}{\ensuremath{\leqslant}}\gamma;\\[3mm]
\bigg(1-\dfrac{\gamma}{\|P_{K}(\eta,y)\|_{\ensuremath{{\mathcal K}}}}\bigg)
P_{K}(\eta,y),&\text{if}\;\;\|P_{K}(\eta,y)\|_{\ensuremath{{\mathcal K}}}>\gamma.
\end{cases}$$ We thus obtain an explicit expression as soon as $P_K$ is explicit although ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is not open. As an illustration, let $N{\ensuremath{\geqslant}}2$ be an integer, set ${\ensuremath{{\mathcal G}}}={\ensuremath{\mathbb{R}}}^{N-1}$, let $D={\ensuremath{\left[0,+\infty\right[}}^{N-1}$, and denote by $\|\cdot\|_{N}$ the usual $N$-dimensional Euclidean norm. Then $\varphi=\sqrt{1+\|\cdot\|_{N-1}^2}+\iota_D$, $K={\ensuremath{\left[0,+\infty\right[}}^N$, and becomes $$\begin{aligned}
\label{eQrs54tGhfnnUjH0-01e}
{\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)=
\begin{cases}
(0,0),&\text{if}\;\;\|(\eta_+,y_+)\|_N{\ensuremath{\leqslant}}\gamma;\\[3mm]
\bigg(1-\dfrac{\gamma}{\|(\eta_+,y_+)\|_N}\bigg)(\eta_+,y_+),
&\text{if}\;\;\|(\eta_+,y_+)\|_N>\gamma,
\end{cases}\end{aligned}$$ where $\eta_+=\max\{0,\eta\}$ and $y_+$ is defined likewise componentwise.

The second example provides the proximity operator of the perspective function of the Huber function.

\[exQrs54tGhfnnUjH0-09\] Following [@Scda16a Example 3.2], let $\rho\in{\ensuremath{\left]0,+\infty\right[}}$ and consider the perspective function $$\label{ekIjiiIus3W9-24c}
\widetilde{\varphi}\colon{\ensuremath{\mathbb{R}}}^2\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon (\eta,y)\mapsto
\begin{cases}
\rho|y|-\dfrac{\eta\rho^2}{2},&\text{if}\;\;|y|>\eta\rho\;\;
\text{and}\;\;\eta>0;\\
\dfrac{|y|^2}{2\eta},&\text{if}\;\;|y|{\ensuremath{\leqslant}}\eta\rho\;\;
\text{and}\;\;\eta>0;\\
\rho|y|,&\text{if}\;\;\eta=0;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;\eta<0
\end{cases}$$ of the Huber function $$\label{e:rodos2015-08-12}
\varphi\colon{\ensuremath{\mathbb{R}}}\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon y\mapsto
\begin{cases}
\rho|y|-{\displaystyle{\frac{\rho^2}{2}}}, &\text{if}\;\;|y|>\rho;\\[+2mm]
{\displaystyle{\frac{|y|^2}{2}}},&\text{if}\;\;|y|{\ensuremath{\leqslant}}\rho.
\end{cases}$$ Then $\varphi^*=|\cdot|^2/2+\iota_{[-\rho,\rho]}$ and ${\ensuremath{\text{\rm dom}\,}}\varphi^*$ is therefore a proper closed subset of ${\ensuremath{\mathbb{R}}}$. In addition, yields $$C={\big\{{(\mu,u)\in{\ensuremath{\left]-\infty,0\right]}}\times[-\rho,\rho]}~\big |~{\mu+|u|^2/2{\ensuremath{\leqslant}}0}\big\}}.$$ Now let $\eta\in{\ensuremath{\mathbb{R}}}$, let $y\in{\ensuremath{\mathbb{R}}}$, and set $(\chi,q)={\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)$. Then the following hold:

1.  If $\eta+|y|^2/(2\gamma){\ensuremath{\leqslant}}0$ and $|y|{\ensuremath{\leqslant}}\gamma\rho$, then Theorem \[tevU74gdnx-06\]\[tevU74gdnx-06i\] yields $(\chi,q)=(0,0)$.

2.  We have $\chi=0$ $\Leftrightarrow$ $\eta/\gamma{\ensuremath{\leqslant}}-\rho^2/2$. Hence, if $\eta{\ensuremath{\leqslant}}-\gamma\rho^2/2$ and $|y|>\gamma\rho$, yields $(\chi,q)=(0,y-P_{[-\gamma\rho,\gamma\rho]}y)=
    (0,y-\gamma\rho\,{\ensuremath{\text{\rm sign}}}(y))$.

3.  If $\eta>-\gamma\rho^2/2$ and $|y|>\rho\eta+\gamma\rho(1+\rho^2/2)$, then $(\eta/\gamma,y/\gamma)\in(-\rho^2/2,\rho\,{\ensuremath{\text{\rm sign}}}(y))+
    N_C(-\rho^2/2,\rho\,{\ensuremath{\text{\rm sign}}}(y))$ and therefore $P_C(\eta/\gamma,y/\gamma)=(-\rho^2/2,\rho\,{\ensuremath{\text{\rm sign}}}(y))$. Hence, yields $(\chi,q)=(\eta+\gamma\rho^2/2,y-\gamma\rho\,{\ensuremath{\text{\rm sign}}}(y))$.

4.  If $\eta>-\gamma\rho^2/2$ and $|y|{\ensuremath{\leqslant}}\rho\eta+\gamma\rho(1+\rho^2/2)$, then $(\chi,q)={\ensuremath{\text{\rm prox}}}_{\gamma[|\cdot|^2/2]^\sim}(\eta,y)$ is obtained by setting $v=0$, $\delta=0$, and $\alpha=2$ in Example \[exevU74gdnx-12a\].

The last example concerns the Vapnik loss function.

\[exQrs54tGhfnnUjH0-11\] Following [@Scda16a Example 3.4], let $\varepsilon\in{\ensuremath{\left]0,+\infty\right[}}$ and consider the perspective function $$\label{eQrs54tGhfnnUjH0-11c}
\widetilde{\varphi}\colon{\ensuremath{\mathbb{R}}}^2\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\eta,y)\mapsto
\begin{cases}
d_{[-\varepsilon\eta,\varepsilon\eta]}(y),&\text{if}\;\;
\eta{\ensuremath{\geqslant}}0;\\
{\ensuremath{{+\infty}}},&\text{if}\;\;\eta<0
\end{cases}$$ of the Vapnik $\varepsilon$-insensitive loss function [@Vapn00] $$\label{eQrs54tGhfnnUjH0-11d}
\varphi=\text{max}\{|\cdot|-\varepsilon,0\}.$$ We have $\varphi=d_{[-\varepsilon,\varepsilon]}=
\iota_{[-\varepsilon,\varepsilon]}
{\ensuremath{\mbox{\small$\,\square\,$}}}|\cdot|$ and therefore $\varphi^*=\varepsilon|\cdot|+\iota_{[-1,1]}$. Furthermore, becomes $$C={\big\{{(\mu,u)\in{\ensuremath{\left]-\infty,0\right]}}\times[-1,1]}~\big |~{\mu+\varepsilon|u|{\ensuremath{\leqslant}}0}\big\}}.$$ Now let $\eta\in{\ensuremath{\mathbb{R}}}$, let $y\in{\ensuremath{\mathbb{R}}}$, and set $(\chi,q)={\ensuremath{\text{\rm prox}}}_{\gamma\widetilde{\varphi}}(\eta,y)$. Then the following hold:

1.  If $\eta+\varepsilon|y|{\ensuremath{\leqslant}}0$ and $|y|{\ensuremath{\leqslant}}\gamma$, then Theorem \[tevU74gdnx-06\]\[tevU74gdnx-06i\] yields $(\chi,q)=(0,0)$.

2.  We have $\chi=0$ $\Leftrightarrow$ $\eta/\gamma{\ensuremath{\leqslant}}-\varepsilon$. Hence, if $\eta{\ensuremath{\leqslant}}-\gamma\varepsilon$ and $|y|>\gamma$, yields $(\chi,q)=(0,y-P_{[-\gamma,\gamma]}y)=
    (0,y-\gamma\,{\ensuremath{\text{\rm sign}}}(y))$.

3.  If $\eta>-\gamma\varepsilon$ and $|y|>\varepsilon\eta+\gamma(1+\varepsilon^2)$, then $(\eta/\gamma,y/\gamma)\in(-\varepsilon,{\ensuremath{\text{\rm sign}}}(y))+
    N_C(-\varepsilon,{\ensuremath{\text{\rm sign}}}(y))$ and therefore $P_C(\eta/\gamma,y/\gamma)=(-\varepsilon,{\ensuremath{\text{\rm sign}}}(y))$. Hence, yields $(\chi,q)=(\eta+\gamma\varepsilon,y-\gamma\,{\ensuremath{\text{\rm sign}}}(y))$.

4.  If $|y|>-\eta/\varepsilon$ and $\varepsilon\eta{\ensuremath{\leqslant}}|y|{\ensuremath{\leqslant}}\varepsilon\eta+\gamma(1+\varepsilon^2)$, then $P_C(\eta/\gamma,y/\gamma)$ coincides with the projection of $(\eta/\gamma,y/\gamma)$ onto the half-space with outer normal vector $(1,\varepsilon\,{\ensuremath{\text{\rm sign}}}(y))$ and which has the origin on its boundary. As a result, yields $(\chi,q)=((\eta+\varepsilon|y|)/(1+\varepsilon^2),
    \varepsilon(\eta+\varepsilon|y|){\ensuremath{\text{\rm sign}}}(y)/(1+\varepsilon^2))$.

5.  If $\eta{\ensuremath{\geqslant}}0$ and $|y|{\ensuremath{\leqslant}}\varepsilon\eta$, then $P_C(\eta/\gamma,y/\gamma)=(0,0)$ and yields $(\chi,q)=(\eta,y)$.

Applications in high-dimensional statistics {#sec:4}
===========================================

Sections \[sec:2\] and \[sec:3\] provide a unifying framework to model a variety of problems around the notion of a perspective function. By applying the results of Section \[sec:3\] in existing proximal algorithms, we obtain efficient methods to solve complex problems. To illustrate this point, we focus on a specific application area: high-dimensional regression in the statistical linear model.

Penalized linear regression
---------------------------

We consider the standard statistical linear model $$\label{e:linmodel}
z=Xb+\sigma e,$$ where $z=(\zeta_i)_{1{\ensuremath{\leqslant}}i{\ensuremath{\leqslant}}n}\in{\ensuremath{\mathbb{R}}}^n$ is the response, $X\in{\ensuremath{\mathbb{R}}}^{n \times p}$ a design (or feature) matrix, $b=(\beta_j)_{1{\ensuremath{\leqslant}}j{\ensuremath{\leqslant}}p}\in{\ensuremath{\mathbb{R}}}^p$ a vector of regression coefficients, $\sigma\in{\ensuremath{\left]0,+\infty\right[}}$, and $e=(\varepsilon_i)_{1{\ensuremath{\leqslant}}i{\ensuremath{\leqslant}}n}$ the noise vector; each $\varepsilon_i$ is the realization of a random variable with mean zero and variance $1$. Henceforth, we denote by $X_{i:}$ the $i$th row of $X$ and by $X_{:j}$ the $j$th column of $X$. In the high-dimensional setting where $p > n$, a typical assumption about the regression vector $b$ is sparsity. In this scenario, the Lasso [@Tibshirani1996] has become a fundamental tool for variable selection and predictive modeling. It is based on solving the penalized least-squares problem $$\label{e:lasso}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{1}{2n}\|Xb-z\|^2_2+\lambda\|b\|_1 }},$$ where $\lambda\in{\ensuremath{\left[0,+\infty\right[}}$ is a regularization parameter that aims at controlling the sparsity of the solution. The Lasso has strong performance guarantees in terms of support recovery, estimation, and predictive performance if one takes $\lambda\propto\sigma\|X^\top e\|_\infty$. In the high-dimensional setting, two shortcomings of the Lasso are the introduction of bias in the final estimates due to the $\ell^1$ norm and lack of knowledge about the quantity $\sigma$ which necessitates proper tuning of $\lambda$ via model selection strategies that is dependent on $\sigma$. Bias reduction can be achieved by using a properly weighted $\ell^1$ norm, resulting in the adaptive Lasso [@Zhou2006] formulation $$\label{e:alasso}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{1}{2n}\|Xb-z\|^2_2+
\lambda\sum_{j=1}^{p}w_j|\beta_j| }},$$ where the fixed weights $w_j\in{\ensuremath{\left]0,+\infty\right[}}$ are estimated from data. In [@Zhou2006], it was shown that, for suitable choices of $w_j$, the adaptive Lasso produces (asymptotically) unbiased estimates of $b$. One of the first methods to alleviate the $\sigma$-dependency of the Lasso has been the Sqrt-Lasso [@Belloni2011]. The Sqrt-Lasso problem is based on the formulation $$\label{e:sqrtlasso}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{1}{2}\|Xb-z\|_2+
\lambda\|b\|_1 }}.$$ This optimization problem can be cast as second order cone program (SOCP) [@Belloni2011]. The modification of the objective function can be interpreted as an (implicit) scaling of the Lasso objective function by an estimate $\|X b-z\|_2/\sqrt{n}$ of $\sigma$ [@Lederer2015], leading to $$\label{e:sqrtlasso2}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{1}{2\sqrt{n}}\frac{\|Xb-z\|^2_2}
{{\displaystyle{\frac{1}{\sqrt{n}}}}\|Xb-z\|_2}+\lambda\|b\|_1 }}.$$ In [@Belloni2011], it was shown that the tuning parameter $\lambda$ does not depend on $\sigma$ in Sqrt-Lasso.

Alternative approaches rely on the idea of simultaneously and explicitly estimating $b$ and $\sigma$ from the data. The scaled Lasso [@Sun2012], a robust hybrid of ridge and Lasso regression [@Owen07], and the TREX [@Lederer2015] are important instances. In the following, we will show that these estimators are based on perspective functions under the unifying statistical framework of concomitant estimation. We will introduce a novel family of estimators and show how the corresponding optimization problems can be solved using proximal algorithms. In particular, we will derive novel proximal algorithms for solving both the standard TREX and a novel generalized version of the TREX which includes the Sqrt-Lasso as special case.

Penalized concomitant M-estimators
----------------------------------

In statistics, the task of simultaneously estimating a regression vector $b$ and an additional model parameter is referred to as concomitant estimation. In [@Huber1981], Huber introduced a generic method for formulating “maximum likelihood-type" estimators (or M-estimators) with a concomitant parameter from a convex criterion. Using our perspective function framework, we can extend this framework and introduce the class of penalized concomitant M-estimators defined through the convex optimization problem $$\label{e:concom}
{\ensuremath{\underset{\substack{{\sigma\in{\ensuremath{\mathbb{R}}},\,\tau\in{\ensuremath{\mathbb{R}}},\,b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\sum_{i=1}^n\widetilde{\varphi_i}\big(\sigma,X_{i:}b-\zeta_i\big)
+\sum_{j=1}^p\widetilde{\psi}_j\big(\tau,a_j^\top b\big) }},$$ with concomitant variables $\sigma$ and $\tau$ under the assumptions outlined in Theorem \[tevU74gdnx-06\] and in Section \[subsec:further\]. Here, $\varphi_i\in\Gamma_0({\ensuremath{\mathbb{R}}})$, $\psi_j\in\Gamma_0({\ensuremath{\mathbb{R}}})$, and $a_j\in{\ensuremath{\mathbb{R}}}^p$. The terms $\widetilde{\varphi_i}$ are data fitting terms and $\widetilde{\psi}_j$ are penalty terms. A prominent instance of this family of estimators is the scaled Lasso [@Sun2012] formulation $$\label{e:scaledlasso}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p,\,\sigma\in{\ensuremath{\left]0,+\infty\right[}}}}}{\text{minimize}}\;\;\frac{1}{2n}\frac{\|Xb-z\|^2_2}
{\sigma}+\frac{\sigma}{2}+\lambda\|b\|_1 }},$$ which yields estimates equivalent to the Sqrt-Lasso. Here, setting $\varphi_i=|\cdot|^2/(2n)+1/2$ and $\psi_j=\lambda|\cdot|$ leads to the scaled (or concomitant) Lasso formulation (see Lemma \[levU74gdnx-27\], Corollary \[cevU74gdnx-29a\], and [@Ndia16]). Other function choices result in well-known estimators. For instance, taking each ${\varphi_i}$ to be the Huber function (see Example \[exQrs54tGhfnnUjH0-09\]) and each ${\psi_j}$ to be the Berhu (reversed Huber) function recovers the robust Lasso variant, introduced and discussed in [@Owen07]. Setting each $\psi_j=\lambda|w_j \cdot|$ to be a weighted $\ell^1$ component results in the “Huber + adaptive Lasso" estimator, analyzed theoretically in [@Lamb2011]. Note that for the latter two approaches, no dedicated optimization algorithms exist that can solve the corresponding optimization problem with provable convergence guarantees. Combining the proximity operators introduced here with proximal algorithms enables us to design such algorithms. To exemplify this powerful framework we focus next on a particular instance of a penalized concomitant M-estimator, the TREX estimator, and derive proximity operators and proximal algorithms.

Proximal algorithms for the TREX
--------------------------------

The TREX [@Lederer2015] extends Sqrt-Lasso and scaled Lasso by taking into account the unknown noise distribution of $e$. Recalling that a theoretically desirable tuning parameter for the Lasso is $\lambda\propto\sigma\|X^\top e\|_\infty$, the TREX scales the Lasso objective by an estimate of this quantity, namely, $$\begin{aligned}
\label{eq:trex}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{\|Xb-z\|_2^2}{\|X^\top(Xb-z)\|_\infty}
+\alpha\|b\|_1 }}.\end{aligned}$$ The parameter $\alpha>0$ can be set to a constant value ($\alpha=1/2$ being the default choice). In [@Lederer2015], promising statistical results were reported where an approximate version of the TREX, with no tuning of $\alpha$, has been shown to be a valid alternative to the Lasso. A major technical challenge in the TREX formulation is the non-convexity of the optimization problem. In [@Bien2016], this difficulty is overcome by showing that the TREX problem, although non-convex, can be solved by observing that problem can be equivalently expressed as finding the best solution to $2p$ convex problems of the form $$\label{eq:convexTREX}
{\ensuremath{\underset{\substack{{\substack{b\in{\ensuremath{\mathbb{R}}}^p\\ x_j^\top(X b-z)>0}}}}{\text{minimize}}\;\;\frac{\|Xb-z\|^2_2}{\alpha x_j^\top(X b-z)}+\|b\|_1 }},
\quad\text{where}\quad
x_j=s X_{:j},\quad\text{with}\quad s\in\{-1,1\}.$$ Each subproblem can be reformulated as a standard SOCP and numerically solved using generic SOCP solvers [@Bien2016]. Next we show how our perspective function approach allows us to derive proximal algorithms for not only the TREX subproblems and but also for novel generalized versions of the TREX. The proximal algorithms construct a sequence $(b_k)_{k\in{\ensuremath{\mathbb N}}}$ that is guaranteed to converge to a solution to .

### Proximal operators for the TREX subproblem {#subsec:proxTREX}

We first note that the data fitting term of the TREX subproblem is the special case of where ${\ensuremath{{\mathcal H}}}={\ensuremath{\mathbb{R}}}^p$, ${\ensuremath{{\mathcal G}}}={\ensuremath{\mathbb{R}}}^n$, $q=2$, $L=X$, $r=z$, $u=X^\top x_j$, and $\rho=x_j^\top z$. Given $\alpha\in{\ensuremath{\left]0,+\infty\right[}}$, the data fitting term of the TREX subproblem thus assumes the form $$\label{e:lscperspective3}
f_j\colon{\ensuremath{\mathbb{R}}}^p\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon b\mapsto
\begin{cases}
{\displaystyle{\frac{\|X b-z\|_2^2}{\alpha x_j^\top(X b-z)}}},
&\text{if}\;\;x_j^\top(X b-z)>0;\\
0,&\text{if}\;\;X b=z;\\
{\ensuremath{{+\infty}}},&\text{otherwise,}
\end{cases}$$ and the corresponding TREX subproblem is to $$\label{exevU74gdnx-02b}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;f_j(b)+\|b\|_1 }} \,.$$ Now consider the linear transformation $$\label{exevU74gdnx-02a}
M_j\colon{\ensuremath{\mathbb{R}}}^p\to{\ensuremath{\mathbb{R}}}\times{\ensuremath{\mathbb{R}}}^n\colon b\mapsto
\big(x_j^\top X b,X b\big)$$ and introduce $$\label{exevU74gdnx-02c}
g_j\colon{\ensuremath{\mathbb{R}}}\times{\ensuremath{\mathbb{R}}}^n\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\eta,y)\mapsto
\begin{cases}
{\displaystyle{\frac{\|y-z\|_2^2}{\alpha\big(\eta-x_j^\top z\big)}}},
&\text{if}\;\;\eta>x_j^\top z; \\
0,&\text{if}\;\;y=z\;\text{and}\;\eta=x_j^\top z;\\
{\ensuremath{{+\infty}}},&\text{otherwise.}
\end{cases}$$ Then $f_j=g_j\circ M_j$. Upon setting $h=\|\cdot\|_1$, we see that is of the form $$\label{exevU74gdnx-02c2}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;g_j(M_j b)+h( b) }}.$$ Next, we determine the proximity operators ${\ensuremath{\text{\rm prox}}}_{g_j}$ and ${\ensuremath{\text{\rm prox}}}_h$, as only those are needed in modern proximal splitting methods [@MaPr16; @Siop15] to solve . The proximity operator ${\ensuremath{\text{\rm prox}}}_h$ is the standard soft thresholding operator. A formula for ${\ensuremath{\text{\rm prox}}}_{g_j}$ is provided by Example \[exevU74gdnx-12a\] up to a shift by $(x_j^\top z,z)$. Let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$ and let $g$ be as in . Combining Example \[exevU74gdnx-12a\] and [@Livre1 Proposition 23.29(ii)], we obtain, for every $\eta\in{\ensuremath{\mathbb{R}}}$ and every $y\in{\ensuremath{\mathbb{R}}}^n$, $$\begin{aligned}
\label{exevU74gdnx-02f}
{\ensuremath{\text{\rm prox}}}_{\gamma g_j}(\eta,y)
&=(x_j^\top z,z)+{\ensuremath{\text{\rm prox}}}_{\gamma g_j}
\big(\eta-x_j^\top z,y-z\big)\nonumber\\
&=\begin{cases}
\big(\eta+\alpha\gamma\|p\|_2^2/4,y-\gamma p\big),
&\text{if}\;\;
4\gamma(\eta-x_j^\top z)+\alpha\|y-z\|_2^2>0;\\
\big(x_j^\top z,z\big),&\text{if}\;\;
4\gamma(\eta-x_j^\top z)+\alpha\|y-z\|_2^2{\ensuremath{\leqslant}}0,
\end{cases}\end{aligned}$$ where $$\label{eDACy47Hj-13X}
p=
\begin{cases}
\dfrac{t}{\|y-z\|}(y-z),&\text{if}\;\;y\neq z;\\
0,&\text{if}\;\;y= z,
\end{cases}$$ and where $t$ is the unique solution in ${\ensuremath{\left]0,+\infty\right[}}$ to the depressed cubic equation $$\label{eDACy47Hj-13p}
s^{3}+\frac{4\alpha(\eta-x_j^\top z)+8\gamma}{\alpha^2\gamma}s
-\frac{8\|y-z\|}{\alpha^2\gamma}=0.$$

### Proximal operators for generalized TREX estimators {#subsec:proxGTREX}

Thus far, we have shown that the data-fitting function in the TREX subproblem is a special case of . However, the full potential of is revealed by taking a general $q\in\left]1,{\ensuremath{{+\infty}}}\right[$, leading to the composite perspective function $$\label{eevU74gdnx-14a}
f_{j,q}\colon{\ensuremath{\mathbb{R}}}^p\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon b\mapsto
\begin{cases}
{\displaystyle{\frac{\|X b-z\|_2^q}{\alpha \big|x_j^\top(X b-z)\big|^{q-1}}}},
&\text{if}\;\;x_j^\top(X b-z)>0;\\
0,&\text{if}\;\;X b=z;\\
{\ensuremath{{+\infty}}},&\text{otherwise}.
\end{cases}$$ This function is the data fitting term of a generalized TREX subproblem for the corresponding global generalized TREX objective $$\begin{aligned}
\label{eq:gtrex}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;\frac{\|Xb-z\|_2^q}
{\alpha\|X^\top(Xb-z)\|^{q-1}_\infty} + \| b\|_1 }}.\end{aligned}$$ This objective function provides a novel family of generalized TREX estimators, parameterized by $q$. The first important observation is that, in the limiting case $q\to 1$, the generalized TREX estimator collapses to the Sqrt-Lasso . Secondly, particular choices of $q$ allow very efficient computation of proximity operators for the generalized TREX subproblems. Considering the linear transformation $M_j\colon{\ensuremath{\mathbb{R}}}^p\to{\ensuremath{\mathbb{R}}}\times{\ensuremath{\mathbb{R}}}^n\colon b\mapsto
\big(x_j^\top X b,X b\big)$ and introducing $$\label{eevU74gdnx-14d}
g_{j,q}\colon{\ensuremath{\mathbb{R}}}\times{\ensuremath{\mathbb{R}}}^n\to{\ensuremath{\left]-\infty,+\infty\right]}}\colon(\eta,y)\mapsto
\begin{cases}
{\displaystyle{\frac{\|y-z\|_2^q}{\alpha\big|\eta-x_j^\top z\big|^{q-1}}}},
&\text{if}\;\;\eta>x_j^\top z; \\
0,&\text{if}\;\;y=z\;\text{and}\;\eta=x_j^\top z;\\
{\ensuremath{{+\infty}}},&\text{otherwise}
\end{cases}$$ we arrive at $f_{j,q}=g_{j,q}\circ M_j$. Setting $h=\|\cdot\|_1$ the corresponding problem is to $$\label{exk998JuY4-07}
{\ensuremath{\underset{\substack{{b\in{\ensuremath{\mathbb{R}}}^p}}}{\text{minimize}}\;\;g_{j,q}(M_j b)+h( b) }}.$$ The proximity operator ${\ensuremath{\text{\rm prox}}}_{g_{j,q}}$ is provided by Example \[exevU74gdnx-10a\], where $\delta=0$ and $v=0$, up to a shift by $(x_j^\top z,z)$. Let $g$ be the function in and let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$. Set $q^*=q/(q-1)$, set $\varrho=(\alpha(1-1/q^*))^{q^*-1}$, and take $(\eta,y)\in{\ensuremath{\mathbb{R}}}\times{\ensuremath{{\mathcal G}}}$. If $q^*\gamma^{q^*-1}(\eta-x_j^\top z)+\varrho\|y-z\|_2^{q^*}>0$ and $y\neq z$, let $t\in{\ensuremath{\left]0,+\infty\right[}}$ be the unique solution to the polynomial equation $$\label{eevU74gdnx-14f}
s^{2q^*-1}+\frac{q^*(\eta-x_j^\top z)}{\gamma\varrho}s^{q^*-1}
+\frac{q^*}{\varrho^2}s-\frac{q^*\|y-z\|}{\gamma\varrho^2}=0.$$ Set $$\label{eevU74gdnx-14x}
p=
\begin{cases}
\dfrac{t}{\|y-z\|}(y-z),&\text{if}\;\;y\neq z;\\
0,&\text{if}\;\;y= z.\\
\end{cases}$$ Then we derive from Example \[exevU74gdnx-10a\] that $$\label{eevU74gdnx-14h}
{\ensuremath{\text{\rm prox}}}_{\gamma g_{j,q}}(\eta,y)=
\begin{cases}
\big(\eta+\gamma\varrho t^{q^*}/q^*,y-\gamma p\big),
&\text{if}\;\;q^*\gamma^{q^*-1}(\eta-x_j^\top z)
+\varrho\|y-z\|_2^{q^*}>0;\\
\big(x_j^\top z,z\big),&\text{if}\;\;q^*\gamma^{q^*-1}
(\eta-x_j^\top z)+\varrho\|y-z\|_2^{q^*}{\ensuremath{\leqslant}}0.
\end{cases}$$ The key step in the calculation of the proximity operator is to solve efficiently. The solution is explicit for $q=2$, as discussed in Example \[exevU74gdnx-12a\]. For $q=3$, we obtain a quartic equation that can also be solved explicitly. For $q\in{\big\{{(i+1)/i}~\big |~{i\in{\ensuremath{\mathbb N}},\,i{\ensuremath{\geqslant}}2}\big\}}$ is a polynomial with integer exponents and is thus amenable to efficient root finding algorithms. For a general $q$, a one-dimensional line search for convex functions on a bounded interval needs to be performed.

### Douglas-Rachford for generalized TREX subproblems

Problem is a standard composite problem and can be solved via several proximal splitting methods that require only the ability to compute ${\ensuremath{\text{\rm prox}}}_{g_j}$ and ${\ensuremath{\text{\rm prox}}}_{h}$; see [@Siop13] and references therein. For large scale problems, one could also employ recent algorithms that benefit from block-coordinate [@Siop15] or asynchronous block-iterative implementations [@MaPr16], while still guaranteeing the convergence of their sequence $(b_k)_{k\in{\ensuremath{\mathbb N}}}$ of iterates to a solution to the problem. In this section, we focus on a simple implementation based on the Douglas-Rachford splitting method [@Livre1] in the context of the generalized TREX estimation to illustrate the applicability and versatility of the tools presented in Sections \[sec:2\] and \[sec:3\].

Define $F\colon(b,c)\mapsto h(b)+g_{j,q}(c)$ and $G=\iota_V$, where $V$ is the graph of $M_j$, i.e., $V={\big\{{(b,c)\in{\ensuremath{\mathbb{R}}}^p\times{\ensuremath{\mathbb{R}}}^{n+1}}~\big |~{M_jb=c}\big\}}$. Then we can rewrite as $$\label{exevU74gdnx-03a}
{\ensuremath{\underset{\substack{{\boldsymbol{x}=(b,c)\in{\ensuremath{\mathbb{R}}}^p\times{\ensuremath{\mathbb{R}}}^{n+1}}}}{\text{minimize}}\;\;F(\boldsymbol{x})+G(\boldsymbol{x}) }}$$ Let $\gamma\in{\ensuremath{\left]0,+\infty\right[}}$, let $\boldsymbol{y}_0\in{\ensuremath{\mathbb{R}}}^{p+n+1}$, and let $(\mu_k)_{k\in{\ensuremath{\mathbb N}}}$ be a sequence in $\left]0,2\right[$ such that $\inf_{k\in{\ensuremath{\mathbb N}}}\mu_k>0$ and $\sup_{k\in{\ensuremath{\mathbb N}}}\mu_k<2$. The Douglas-Rachford algorithm is $$\label{e:mer-egee07-15}
\begin{array}{l}
\text{for}\;k=0,1,\ldots\\
\left\lfloor
\begin{array}{l}
\boldsymbol{x}_{k}={\ensuremath{\text{\rm prox}}}_{\gamma{G}}\boldsymbol{y}_k\\
\boldsymbol{z}_{k}={\ensuremath{\text{\rm prox}}}_{\gamma{F}}
(2\boldsymbol{x}_{k}-\boldsymbol{y}_k)\\
\boldsymbol{y}_{k+1}=\boldsymbol{y}_k+
\mu_k(\boldsymbol{z}_{k}-\boldsymbol{x}_{k}).
\end{array}
\right.\\[2mm]
\end{array}$$ The sequence $(\boldsymbol{x}_k)_{k\in{\ensuremath{\mathbb N}}}$ is guaranteed to converge to a solution to [@Livre1 Corollary 27.4]. Note that $$\label{e:9hfe6-03e}
{\ensuremath{\text{\rm prox}}}_{F}\colon (b,c)\mapsto({\ensuremath{\text{\rm prox}}}_{h}b,{\ensuremath{\text{\rm prox}}}_{g_{j,q}}c)$$ and, in view of , $$\label{e:9hfe6-03f}
{\ensuremath{\text{\rm prox}}}_{G}\colon (b,c)\mapsto (v,M_jv),
\quad\text{where}\;\;
v=b-M_j^\top\big({\ensuremath{\operatorname{Id}}\,}+M_jM_j^\top\big)^{-1}(M_jb-c)$$ is the projection operator onto $V$. Hence, upon setting $R_j=M_j^\top({\ensuremath{\operatorname{Id}}\,}+M_jM_j^\top)^{-1}$, $\boldsymbol{x}_k=(b_k,c_k)\in{\ensuremath{\mathbb{R}}}^p\times{\ensuremath{\mathbb{R}}}^{n+1}$, $\boldsymbol{y}_k=(x_k,y_k)\in{\ensuremath{\mathbb{R}}}^p\times{\ensuremath{\mathbb{R}}}^{n+1}$, and $\boldsymbol{z}_k=(z_k,t_k)\in{\ensuremath{\mathbb{R}}}^p\times{\ensuremath{\mathbb{R}}}^{n+1}$, we can rewrite as $$\label{e:9hfe6-03g}
\begin{array}{l}
\text{for}\;k=0,1,\ldots\\
\left\lfloor
\begin{array}{l}
q_k=M_jx_k-y_k\\
b_{k}=x_k-R_jq_k\\
c_{k}=M_jb_{k}\\
z_{k}={\ensuremath{\text{\rm prox}}}_{\gamma{h}}(2b_k-x_k)\\
t_{k}={\ensuremath{\text{\rm prox}}}_{\gamma{g_{j,q}}}(2c_k-y_k)\\
x_{k+1}=x_k+\mu_k(z_k-b_k)\\
y_{k+1}=y_k+\mu_k(t_k-c_k).
\end{array}
\right.\\[2mm]
\end{array}$$ Then $(b_k)_{k\in{\ensuremath{\mathbb N}}}$ converges to a solution $b$ to or . Note that the matrix $R_j$ needs to be precomputed only once by inverting a positive definite symmetric matrix.

Numerical illustrations
-----------------------

We illustrate the convergence behavior of the Douglas-Rachford algorithm for TREX problems and the statistical performance of generalized TREX estimators using numerical experiments. All presented algorithms and experimental evaluations are implemented in MATLAB and are available at <http://github.com/muellsen/TREX>. All algorithms are run in MATLAB 2015a on a MacBook Pro with 2.8 GHz Intel Core i7 and 16 GB 1600 MHz DDR3 memory.

### Evaluation of the Douglas-Rachford scheme on TREX subproblems

We first examine the scaling behavior of the Douglas-Rachford scheme for the TREX subproblem on linear regression tasks. We simulate synthetic data according to the linear model with $m=20$ nonzero variables, regression vector $b^{*}=[-1,1,-1,\ldots, 0_{p-m}^\top]^\top$, and feature vectors $X_{i:}\sim N(0,\Sigma)$ with $\Sigma_{ii}=1$ and $\Sigma_{ij}=0.3$, and Gaussian noise $\varepsilon_i\sim
N(0,\sigma^2)$ with $\sigma=1$. Each column $X_{:j}$ is normalized to have norm $\sqrt{n}$. We fix the sample size $n=200$ and consider the dimension $p\in\{20,50,100,200,500,1000,2000\}$. We solve one standard TREX subproblem (for $s\in\{-1,1\}$, $X_{:1}$, $\alpha=0.5$) over $d=20$ random realizations of $X$ and $e$. For the TREX subproblem we consider the proximal Douglas-Rachford algorithm \[e:9hfe6-03g\] with parameters $\mu_k\equiv 1.95$ and $\gamma=70$. We declare that the Douglas-Rachford algorithm has converged at iteration $K$ if $\min\{\|b_{K+1}-b_{K}\|,\|
y_{K+1}-y_{K}\|\}{\ensuremath{\leqslant}}10^{-10}$, resulting in the final estimate $b_K$.

![Left panel: Average wall-clock time (seconds) versus dimension $p$ for solving the TREX subproblems with Douglas-Rachford (DR), SCS, and DR-Sel (Douglas-Rachford with online sign selection). Right panel: Both plots show the first 40 variables of a typical $p=2000$ TREX solution (top for $s=+1$). The $m=20$ first indices are the non-zero indices in $b^{*}$. Insets show the TREX subproblem objective function values for $s={\pm 1}$ and $X_{:1}$, reached by Douglas-Rachford and SCS. DR-Sel selects the correct signed subproblem as verified a posteriori by the minimum function value ($f^\text{(DR)}_{s=1,j=1}=20.1410$ versus $f^\text{(DR)}_{s=-1,j=1}=22.0451$). \[fig:scaling\]](ScalingPlotCut.eps){width="0.75\linewidth"}

In practice, the Douglas-Rachford algorithm for the TREX subproblem can be enhanced by an online sign selection rule (DR-Sel). When a TREX subproblem for fixed $X_{:j}$ is considered, we can solve the problem for $s\in\{-1,1\}$ concurrently for a small number $k_0$ of iterations (standard setting $k_0=50$) and select the signed optimization problem with best progress in terms of objective function value.

We compare the run time scaling and solution quality of Douglas-Rachford and DR-Sel with those of the state-of-the-art Splitting Conic Solver (SCS). SCS is a general-purpose first-order proximal method that provides numerical solutions to several standard classes of optimization problems, including SOCPs and Semidefinite Programs (SDPs). We use SCS in indirect mode [@ODon2016] to solve the SOCP formulation of the TREX subproblem [@Bien2016] with convergence tolerance $10^{-4}$.

The run time scaling results are shown in Figure \[fig:scaling\]. We emphasize that the scaling experiments are not meant to measure absolute algorithmic performance but rather efficiency with respect to optimization formulations that are subsequently solved by proximal algorithms. We observe that SCS with the SOCP formulation of TREX compares favorably with Douglas-Rachford and DR-Sel in low dimensions while, for $p>200$, both Douglas-Rachford variants perform better. DR-Sel outperforms Douglas-Rachford by a factor of $2$ to $4$ and always selects the correct signed subproblem (data not shown). The TREX solutions found by SCS and Douglas-Rachford are close in terms of $\| b^{(DR)}-b^{(SCS)}\|$, with DR typically reaching slightly lower function values than SCS. Values for the first 40 dimensions of a typical solution $b_{K}$ in $p=2000$ dimensions are shown in Figure \[fig:scaling\] (right panels).

### Behavior of generalized TREX estimators

We next study the effect of the exponent $q$ on the statistical behavior of the generalized TREX estimator. We use the synthetic setting outlined in [@Wain2009] to study the phase transition behavior of the different generalized TREX estimators. We generate data from the linear model with $p=64$ and $m=\lceil 0.4 p^{3/4} \rceil$ nonzero variables, regression vector $b^*=[-1,1,-1,\ldots, 0_{p-m}^\top]^\top$, and feature vectors $X_{i:}\sim N(0,\Sigma)$ with $\Sigma_{ii}=1$ and $\Sigma_{ij}=0$ and Gaussian noise $e$ with $\sigma=0.5$. Each column $X_{:j}$ is normalized to have norm $\sqrt{n}$. We define the rescaled sample size according to $ \theta(n, p, m)=n / (2 m \log{(p-m)})$ and consider $\theta(n,p,m)\in\{0.2,0.4,\ldots,1.6\}$. At $\theta(n, p,m)=1$, the probability of exact recovery of the support of $b^*$ is $0.5$ for the (Sqrt)-Lasso with oracle regularization parameter [@Wain2009]. We consider the generalized TREX with different exponents $q\in\{9/8,7/6,3/2,2\}$ and the Sqrt-Lasso as limiting case $q=1$. For all generalized TREX estimators we consider regularization parameters $\alpha\in\{0.1,0.15,\ldots,2\}$. For Sqrt-Lasso we consider the standard regularization path setting outlined in [@Ndia16]. We solve all generalized TREX problems with the Douglas-Rachford scheme using the previously described parameter and convergence settings. We measure the probability of exact support recovery and Hamming distance to the true support over $d=12$ repetitions. We threshold all “numerical zeros" in the generalized TREX solutions vectors at level $0.05$. For all solutions closest to the true support in terms of Hamming distance, we also calculate estimation error $\|b_K-b^*\|_2^2/n$ and prediction error $\|Xb_K-Xb^*\|_2^2/n$. Figure \[fig:phaseTrans\] shows average performance results across all repetitions.

![Top row: Probability (and standard error) of exact support recovery versus rescaled sample size $\theta(n, p, m)$ for generalized TREX with $q\in \{1,9/8,7/6,3/2,2\}$; top right panel: Average Hamming distance to true support. Bottom row: Mean estimation error $\|b_K-b^*\|_2^2/n$ (left panel) and mean prediction error $\|X b_K-X b^*\|_2^2/n$ (right panel). \[fig:phaseTrans\]](PhaseTransProx.eps){width="0.9\linewidth"}

We observe several interesting phenomena for the family of generalized TREX estimators. In terms of exact recovery, the performance is slightly better than predicted by theory (see gray dashed line in Figure \[fig:phaseTrans\] top left panel), with decrease in performance for increasing $q$. This is also consistent with average Hamming distance measurements (top right panel). We observe that generalized TREX oracle solutions (according to the minimum Hamming distance criterion) show best performance in terms of estimation and prediction error for exponents $q\in\{9/8,7/6\}$, followed by $q\in\{3/2,2\}$.

The present numerical experiments highlight the usefulness of the family of generalized TREX estimators for sparse linear regression problems. Further theoretical research is needed to derive asymptotic properties of generalized TREX. A central prerequisite for establishing generalized TREX as statistical estimator is to solve the underlying optimization problem with provable guarantees. We have shown that our perspective function framework along with efficient computation of proximity operators enables this important task in a seamless way.

#### Acknowledgement.

We thank Dr. Jacob Bien for valuable discussions. The Simons Foundation is acknowledged for partial financial support of this research. The work of P. L. Combettes was also partially supported by the CNRS MASTODONS project under grant 2016TABASCO.

[99]{}

H. H. Bauschke and P. L. Combettes, [*Convex Analysis and Monotone Operator Theory in Hilbert Spaces.*]{} Springer, New York, 2011.

A. Belloni, V. Chernozhukov, and L. Wang, Square-root lasso: pivotal recovery of sparse signals via conic programming, [*Biometrika*]{}, vol. 98, pp. 791–806, 2011.

J. Bien, I. Gaynanova, J. Lederer, and C. L. M[ü]{}ller, Non-convex global minimization and false discovery rate control for the TREX, 2016. <http://arxiv.org/abs/1604.06815>

G. Birkhoff and S. Mac Lane, [*A Survey of Modern Algebra,*]{} 4th edition. Macmillan, New York, 1977.

J. M. Borwein, A. S. Lewis, and D. Noll, Maximum entropy reconstruction using derivative information, part 1: Fisher information and convex duality, [*Math. Oper. Res.,*]{} vol. 21, pp. 442–468, 1996.

P. L. Combettes, Systems of structured monotone inclusions: Duality, algorithms, and applications, [*SIAM J. Optim.,*]{} vol. 23, pp. 2420–2447, 2013.

P. L. Combettes, Perspective functions: Properties, constructions, and examples, 2016.\
<https://arxiv.org/abs/1610.01552>

P. L. Combettes and J. Eckstein, Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions, [*Math. Programming,*]{} published online 2016-07-05.

P. L. Combettes and J.-C. Pesquet, Proximal thresholding algorithm for minimization over orthonormal bases, [*SIAM J. Optim.,*]{} vol. 18, pp. 1351–1376, 2007.

P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in *Fixed-Point Algorithms for Inverse Problems in Science and Engineering,* (H. H. Bauschke et al., eds), pp. 185–212. Springer, New York, 2011.

P. L. Combettes and J.-C. Pesquet, Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, [*SIAM J. Optim.,*]{} vol. 25, pp. 1221–1248, 2015.

P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, [*Multiscale Model. Simul.*]{}, vol. 4, pp. 1168–1200, 2005.

M. El Gheche, G. Chierchia, and J.-C. Pesquet, Proximity operators of discrete information divergences, 2016. <https://arxiv.org/pdf/1606.09552v1.pdf>

F. Facchinei and J.-S. Pang, [*Finite-Dimensional Variational Inequalities and Complementarity Problems.*]{} Springer-Verlag, New York, 2003.

R. A. Fisher, Theory of statistical estimation, [*Proc. Cambridge. Philos. Soc.,*]{} vol. 22, pp. 700–725, 1925.

B. R. Frieden and R. A. Gatenby (eds.), [*Exploratory Data Analysis Using Fisher Information.*]{} Springer, New York, 2007.

P. J. Huber, [*Robust Statistics,*]{} 1st ed. Wiley, New York, 1981.

S. Lambert-Lacroix and L. Zwald, Robust regression through the Huber’s criterion and adaptive lasso penalty, [*Electron. J. Stat.,*]{} vol. 5, pp. 1015–1053, 2011.

J. Lederer and C. L. M[ü]{}ller, Don’t fall for tuning parameters: Tuning-free variable selection in high dimensions with the TREX, [*Proc. Twenty-Ninth AAAI Conf. Artif. Intell.*]{}, pp. 2729–2735. AAAI Press, Austin, 2015.

J. J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, [*C. R. Acad. Sci. Paris Sér. A Math.,*]{} vol. 255, pp. 2897–2899, 1962.

E. Ndiaye, O. Fercoq, A. Gramfort, V. Leclère, and J. Salmon, Efficient smoothed concomitant lasso estimation for high dimensional regression, 2016. <https://arxiv.org/pdf/1606.02702v1.pdf>

B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Conic optimization via operator splitting and homogeneous self-dual embedding, [*J. Optim. Theory Appl.,*]{} vol. 169, pp. 1042–1068, 2016.

A. B. Owen, A robust hybrid of lasso and ridge regression, [*Contemp. Math.,*]{} vol. 443, pp. 59–71, 2007.

R. T. Rockafellar, [*Convex Analysis.*]{} Princeton University Press, Princeton, NJ, 1970.

S. Sra, S. Nowozin, and S. J. Wright, [*Optimization for Machine Learning.*]{} MIT Press, Cambridge, MA, 2012.

T. Sun and C. Zhang, Scaled sparse linear regression, [*Biometrika*]{}, vol. 99, pp. 879–898, 2012.

R. Tibshirani, Regression shrinkage and selection via the lasso, [*J. Roy. Stat. Soc.*]{}, vol. B58, pp. 267–288, 1996.

V. N. Vapnik, [*The Nature of Statistical Learning Theory,*]{} 2nd ed. Springer, New York, 2000.

M. J. Wainwright, Sharp thresholds for high-dimensional and noisy sparsity recovery using $\ell_1$-constrained quadratic programming (Lasso), [*IEEE Trans. Inform. Theory*]{}, vol. 55, pp. 2183–2202, 2009.

H. Zou, The adaptive lasso and its oracle properties, [*J. Amer. Stat. Assoc.*]{}, vol. 101, pp. 1418–1429, 2006.

[^1]: Contact author: P. L. Combettes, [[](mailto:plc@math.ncsu.edu)]{}, phone: +1 (919) 515 2671.
