Prox functions

MATLAB function	function	input	assumptions
prox_quadratic	convex quadratic $\alpha \left (\frac{1}{2}x^T A x +b^T x\right )$	$x$ - vector to be projected $\alpha$ - positive scalar $A$ - positive semidefinite matrix $b$ - vector	$A \in {\mathbb S}^n_{+}$
prox_Eulidean_norm^[*]	Euclidean norm $\alpha\\|x\\|$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar	l₂ or Frobenius norm
prox_l1^[*]	l1-norm $\alpha \\|x\\|_1$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar
prox_neg_sum_log^[*]	negative sum of logs $-\alpha \sum_{i=1}^n \log(x_i)$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar	(n- dimension of x)
prox_linf^[*]	l∞-norm $\alpha \\|x\\|_{\infty}$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar
prox_max^[*]	maximum $\alpha \max\{x_1,x_2,\ldots,x_n\}$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar	(n- dimension of x)
prox_Huber^[*]	Huber $H_{\mu}(x) = \left \{ \begin{array}{ll} \frac{1}{2\mu}\\|x\\|^2, & \\|x\\|\leq \mu,\\ \\|x\\|-\mu, & \\|x\\|>\mu.\end{array}\right.$	$x$ - point to be projected (vector/matrix) $\mu$ - positive scalar $\alpha$ - positive scalar	µ>0
prox_sum_k_largest^[*]	sum of k largest values $\alpha \sum_{i=1}^k x_{[i]}$	$x$ - point to be projected (vector/matrix) $k$ - positive integer $\alpha$ - positive scalar	$k \in \{1,2,\ldots,n\}$ (n- dimension of x)
prox_sum_k_largest_abs^[*]	sum of k largest absolute values $\alpha \sum_{i=1}^k \|x_{\langle i \rangle}\|$	$x$ - point to be projected (vector/matrix) $k$ - positive integer $\alpha$ - positive scalar	$k \in \{1,2,\ldots,n\}$ (n- dimension of x)
prox_norm2_linear	l_2-norm of a linear transformation $\alpha \\|Ax\\|_2$	$x$ - vector to be projected $A$ - matrix with a full row rank $\alpha$ - positive scalar	$A$ with full row rank
prox_l1_squared^[*]	squared l₁-norm $\alpha\\|x\\|_1^2$	$x$ - point to be projected (vector/matrix) $\alpha$ - positive scalar
prox_max_eigenvalue	maximum eigenvalue $\alpha \lambda_{\max}(X)$	$X$ - matrix to be projected $\alpha$ - positive scalar	$X$ symmetric
prox_neg_log_det	negative log determinant $-\alpha \log(\det(X))$	$X$ - matrix to be projected $\alpha$ - positive scalar	$X$ symmetric
prox_sum_k_largest_eigenvalues	sum of k largest eigenvalues $\alpha \sum_{i=1}^k \lambda_i(X)$	$X$ - nxn matrix to be projected $k$ - positive integer $\alpha$ - positive scalar	$X$ symmetric $k \in \{1,2,\ldots,n\}$
prox_spectral	spectral norm $\alpha \\|X\\|_{2,2}=\alpha \sigma_1(X)$	$X$ - matrix to be projected $\alpha$ - positive scalar
prox_nuclear	nuclear norm $\alpha \\|X\\|_{S_1}=\alpha \sum_{i=1}^{\min\{m,n\}} \sigma_i(X)$	$X$ - matrix to be projected $\alpha$ - positive scalar
prox_Ky_Fan	Ky Fan norm $\alpha \\|X\\|_{\langle k \rangle}=\alpha \sum_{i=1}^k \sigma_i(X)$	$X$ - mxn matrix to be projected $k$ - positive integer $\alpha$ - positive scalar	$k \in \{1,2,\ldots,\min\{m,n\}\}$

[*] functions marked by [*] operate on mxn matrices in the same way they operate on the corresponding m*n-length column vector.

Remarks:

$\alpha$ is always assumed to be a positive scalar.
"vectors" are always column vectors.
The projection is done w.r.t. either the l₂-norm or the Frobenuis norm.
The underlying inner product is the dot product.
The output is always the projection vector/matrix.

Functions in alphabetical order

prox_Eulidean_norm

prox_Huber

prox_Ky_Fan

prox_linf

prox_l1

prox_l1_squared

prox_max

prox_max_eigenvalue

prox_neg_log_det

prox_neg_sum_log

prox_norm2_linear

prox_nuclear

prox_quadratic

prox_spectral

prox_sum_k_largest

prox_sum_k_largest_abs

prox_sum_k_largest_eigenvalues

prox_quadratic

Usage: prox_quadratic(x,A,b,alpha)

Input:

x - vector to be projected

A - positive semidefinite matrix

b - vector

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha g}(x) = (I + \alpha A)^{-1} (x - \alpha b)$

where

$g(x)=\frac{1}{2}x^T A x+b^Tx$

Example: the prox of the vector [2;3] w.r.t. the quadratic function f with A=[2,1;1,2] and b= [1;-1] is

>> A=[2,1;1,2];b=[1;-1];

>> prox_quadratic([2;3],A,b,1)

ans =

-0.1250

1.3750

top of page

prox_Euclidean_norm

Usage: prox_Euclidean_norm(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \|\cdot\|}(x)=\left ( 1-\frac{\alpha}{\max\{\|x\|,\alpha\}} \right )x$

Example: the prox of the matrix [2,3,1;0,1,4] w.r.t. the function g(x)=norm(x,'fro') is computed the commands

>> A=[2,3,1;0,1,4];

>> prox_Euclidean_norm(A,1)

ans =

1.6408 2.4612 0.8204

0 0.8204 3.2816

top of page

prox_l1

Usage: prox_l1(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \|\cdot\|_1}(x) = ([|x_i|-\alpha]_+ {\rm sign}(x_i))_{i=1}^n$

Example: the prox of the vector [4;2;3] w.r.t. the function g(x)=2*norm(x(:),1) is

>> prox_l1([4;2;3],2)

ans =

2

0

1

top of page

prox_neg_sum_log

Usage: prox_neg_sum_log(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha g}(x) = \left ( \frac{x_i+\sqrt{x_i^2+4 \alpha}}{2} \right )_{i=1}^n, g(x)=- \sum_{i=1}^n \log(x_i)$

Example: the prox of the vector [2;3;1] w.r.t. the function g(x)=-sum(sum(log(x))) is

>> prox_neg_sum_log([2;3;1],1)

ans =

2.4142

3.3028

1.6180

top of page

prox_linf

Usage: prox_linf(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \|\cdot\|_{\infty}}(x)= x-\alpha P_{B_{\|\cdot\|_1}[0,1]}(x/\alpha)$

(utilizes the function proj_l1_ball)

Example: the prox of the vector [1;2;3;4] w.r.t. the function g(x)=2*norm(x(:),Inf) is

>> x=[1;2;3;4];

>> prox_linf(x,2)

ans =

1.0000

2.0000

2.5000

The same result will be obtained if the vector will be reshaped as a 2x2 matrix and then reshaped back to a 4-length column vector

>> X=reshape(x,2,2)

X =

1 3

2 4

>> prox_linf(X,2)

ans =

1.0000 2.5000

2.0000 2.5000

top of page

prox_max

Usage: prox_max(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \max(\cdot)}=x-P_{\Delta_n}(x/\alpha)$

(utilizes the function proj_simplex)

Example: the prox of the vector [1;2;3;4] w.r.t. the function g(x)=max(x(:)) is

>> prox_max([1;2;3;4],1)

ans =

1.0000

2.0000

3.0000

top of page

prox_Huber

Usage: prox_Huber(x,mu,alpha)

Input:

x - point to be projected (vector/matrix)

mu - positive scalar

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha H_{\mu}}(x)=\left ( 1-\frac{\alpha}{\max\{\|x\|,\mu+\alpha\}}\right )x$

Example: the prox of the vector [1;2;3;4] w.r.t. twice Huber function with parameter 3 is

>> prox_Huber([1;2;3;4],3,2)

ans =

0.6349

1.2697

1.9046

2.5394

top of page

prox_sum_k_largest

Usage: prox_sum_k_largest(x,k,alpha)

Input:

x - point to be projected (vector/matrix)

k - positive integer

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha g}(x)=x-\alpha P_{H_{e,k} \cap {\rm Box}[0,e]}(x/\alpha), \; g(x) = \sum_{i=1}^k x_{[i]}$

(utilizes the function
proj_hyperplane_box
)

Example: the prox of the vector [1;2;3;4] w.r.t. the function g(x)=2x_[1]+2x_[2] is

>> prox_sum_k_largest([1;2;3;4],2,2)

ans =

1.0000

1.5000

2.0000

The prox of the vector [1;2;3;4] w.r.t. the function g(x)=3x_[1] is

>> prox_sum_k_largest([1;2;3;4],1,3)

ans =

1.0000

2.0000

Obviously, since x_[1]=max(x), the same result can be obtain using the function prox_max

>> prox_max([1;2;3;4],3)

ans =

1.0000

2.0000

top of page

prox_sum_k_largest_abs

Usage: prox_sum_k_largest_abs(x,k,alpha)

Input:

x - point to be projected (vector/matrix)

k - positive integer

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha g}(x)=x-\alpha P_{B_{\|\cdot\|_1}[0,k] \cap {\rm Box}[-e,e]}(x/\alpha), \; g(x) = \sum_{i=1}^k |x_{\langle i\rangle }|$

(utilizes the function
proj_l1ball_box
)

Example: the prox of the vector [1;0;-1;2] w.r.t. the function g(x)=|x_<1>|+|x_<2>| is

>> prox_sum_k_largest_abs([1;0;-1;2],2,1)

ans =

0.5000

0

-0.5000

1.0000

Essentially the same result is obtained (but reshaped as a matrix) if we compute the prox of the matrix [1,0;-1,2] w.r.t. the same function

>> prox_sum_k_largest_abs([1,0;-1,2],2,1)

ans =

0.5000 0

-0.5000 1.0000

the prox of [1;0;-1;2] w.r.t. norm(x,'Inf') can be computed by either prox_sum_k_largeat_abs

prox_sum_k_largest_abs([1;0;-1;2],1,1)

ans =

1

0

-1

1

or by prox_linf

>> prox_linf([1;0;-1;2],1)

ans =

1

0

-1

1

top of page

prox_norm2_linear

Usage: prox_norm2_linear(x,A,alpha)

Input:

x - vector to be projected

A - matrix

alpha - positive scalar

Method: employs the formula

$prox_{\alpha g}(x) = \left \{ \begin{array}{ll} x-A^T (AA^T)^{-1}A x, & \|(AA^T)^{-1}A x\|_2\leq \alpha,\\ x-A^T (AA^T+\lambda^*I)^{-1}A x, & \|(AA^T)^{-1}A x\|_2> \alpha.\end{array}\right.$

where $\lambda^*$ is the unique positive root of the function

$\varphi(\lambda)=\|(AA^T+\lambda I)^{-1}Ax\|_2^2-\alpha^2$

The root is found by bisection.

Example: the prox of the vector [1;2;3] w.r.t. the function

$\sqrt{(x_1-x_2)^2+(x_2-x_3)^2}$

>> prox_norm2_linear([1;2;3],[1,-1,0;0,1,-1],1)

ans =

1.7071

2.0000

2.2929

To compute the prox of [1;2;3] w.r.t. the l₂-norm function we can use prox_norm2_linear and the result is obviously the same as the one produced by prox_Eulidean_norm

>> prox_norm2_linear([1;2;3],eye(3),1)

ans =

0.7327

1.4655

2.1982

>> prox_Euclidean_norm([1;2;3],1)

ans =

0.7327

1.4655

2.1982

top of page

prox_l1_squared

Usage: prox_l1_squared(x,alpha)

Input:

x - point to be projected (vector/matrix)

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\rho g}(x) = \left \{ \begin{array}{ll} \left ( \frac{\lambda_i x_i}{\lambda_i+2 \alpha}\right )_{i=1}^n, & x \neq 0,\\ 0, & x = 0, \end{array} \right. g(x)=\alpha \|x\|_1^2$

where

$\lambda_i = \left [\frac{\sqrt{\alpha}{|x_i|} }{\sqrt{\mu^*}}-2 \alpha\right ]_+$

with $\mu^*$ being any positive root (found by bisection) of the function

$\psi(\mu) = \sum_{i=1}^n \left [\frac{\sqrt{\alpha}{|x_i|} }{\sqrt{\mu}}-2 \alpha \right ]_+-1$

Example: the prox of the matrix [1,2;2,3] (treated as a 4-length column vector) w.r.t. twice the l₁-squared norm function is

>> prox_l1_squared([1,2;2,3],2)

ans =

0 0

0 0.6000

top of page

prox_max_eigenvalue

Usage: prox_max_eigenvalue(X,alpha)

Input:

X - symmetric matrix to be projected

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \lambda_{\max}(\cdot)}(X)=U {\rm diag}(\lambda(X)-\alpha P_{\Delta_n}(\lambda(X)/\alpha)) U^T$

where

$X = U diag(\lambda(X)) U^T$

is a spectral decomposition of X. (utilizes the function proj_simplex )

Example: the prox of the matrix [1,2,0;2,1,2;0,2,1] w.r.t. the maximum eigenvalue function is

>> prox_max_eigenvalue( [1,2,0;2,1,2;0,2,1],1)

ans =

0.7500 1.6464 -0.2500

1.6464 0.5000 1.6464

-0.2500 1.6464 0.7500

top of page

prox_neg_log_det

Usage: prox_neg_log_det(X,alpha)

Input:

X - symmetric matrix to be projected

alpha - positive scalar

Method: employs the formula

${\rm prox}_{-\alpha \log \det (\cdot)}(X)=U {\rm diag} \left ( \frac{\lambda_j(X)+\sqrt{\lambda_j(X)^2+4 \alpha}}{2} \right ) U^T$

where

$X = U diag(\lambda(X)) U^T$

is a spectral decomposition of X.

Example: the prox of the matrix [1,2;2,1] w.r.t. the function f(X)=-logdet(X) is

>> prox_neg_log_det([1,2;2,1],1)

ans =

1.9604 1.3424

1.3424 1.9604

top of page

prox_sum_k_largest_eigenvalues

Usage: prox_sum_k_largest_eigenvalues(X,k,alpha)

Input:

X - symmetric matrix to be projected

k - positive integer

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha g}(X)=X-\alpha U P_C(\lambda(X)/\alpha)U^T, C = H_{e,k} \cap {\rm Box}[0, e], g(X)=\alpha \sum_{i=1}^k \lambda_i(X)$

where

$X = U diag(\lambda(X)) U^T$

is a spectral decomposition of X. [utilizes the function
proj_hyperplane_box
]

Example: the prox of the matrix [1,2,0;2,1,2;0,2,1] w.r.t. the sum of the first and second eigenvalues is

>> prox_sum_k_largest_eigenvalues([1,2,0;2,1,2;0,2,1],2,1)

ans =

0.2500 1.6464 0.2500

1.6464 0.5000 1.6464

0.2500 1.6464 0.2500

top of page

prox_spectral

Usage: prox_spectral(X,alpha)

Input:

X - matrix to be projected

alpha - positive scalar

Method: employs the formula

$prox_{\alpha g}(X)=X-\alpha U dg(P_{B_{\|\cdot\|_1}[0,1]}(\sigma(X)/\alpha))V^T$

where

$X = U{\rm dg}(\sigma(X))V^T$

is a singular value decomposition of X [utilizes the function
prox_linf
]

Example: the prox of the matrix [1,2,3;4,5,6] w.r.t. the function 2*norm(X,2) is

>> prox_spectral([1,2,3;4,5,6],2)

ans =

0.6688 1.5625 2.4561

3.2092 3.9553 4.7014

top of page

prox_nuclear

Usage: prox_nuclear(X,alpha)

Input:

X - matrix to be projected

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \|\cdot\|_{S_1}}(X)=U {\rm dg}({\rm prox}_{\alpha \|\cdot\|_1}(\sigma(X)))V^T$

where

$X = U{\rm dg}(\sigma(X))V^T$

is a singular value decomposition of X [utilizes the function
prox_l1
]

Example: the prox of the matrix [1,2,3;4,5,6] w.r.t. the nuclear norm is

>> prox_nuclear([1,2,3;4,5,6],1)

ans =

1.4089 1.8613 2.3137

3.3640 4.4441 5.5242

top of page

prox_Ky_Fan

Usage: prox_Ky_Fan(X,k,alpha)

Input:

X - matrix to be projected

k - positive integer

alpha - positive scalar

Method: employs the formula

${\rm prox}_{\alpha \|\cdot\|_{\langle k \rangle}}(X)=X-\alpha U P_C(\sigma(X)/\alpha)V^T, C = B_{\|\cdot\|_1}[0,k] \cap B_{\|\cdot\|_{\infty}}[0,1]$

where

$X = U{\rm dg}(\sigma(X))V^T$

is a singular value decomposition of X [utilizes the function
proj_l1ball_box
]

Example: the prox of the matrix [1,2,3,4;5,6,7,8;9,10,11,12] w.r.t.

$2\sigma_1(X)+2\sigma_2(X)$

>> prox_Ky_Fan([1,2,3,4;5,6,7,8;9,10,11,12],2,2)

ans =

1.9556 2.2518 2.5480 2.8441

4.9028 5.6453 6.3878 7.1303

7.8499 9.0387 10.2276 11.4164

The prox of the same matrix w.r.t. f(X)=max(svd(X)) is

>> prox_Ky_Fan([1,2,3,4;5,6,7,8;9,10,11,12],1,1)

ans =

0.9166 1.9039 2.8913 3.8786

4.7908 5.7591 6.7274 7.6958

8.6651 9.6143 10.5636 11.5129

This is the same result as the prox w.r.t. the spectral norm

>> prox_spectral([1,2,3,4;5,6,7,8;9,10,11,12],1)

ans =

0.9166 1.9039 2.8913 3.8786

4.7908 5.7591 6.7274 7.6958

8.6651 9.6143 10.5636 11.5129

The prox of the matrix w.r.t. the nuclear norm can be computed by either prox_Ky_Fan or prox_nuclear

>> prox_Ky_Fan([1,2,3,4;5,6,7,8;9,10,11,12],3,1)

ans =

1.5682 2.1616 2.7551 3.3485

4.9772 5.8329 6.6885 7.5441

8.3863 9.5041 10.6219 11.7397

>> prox_nuclear([1,2,3,4;5,6,7,8;9,10,11,12],1)

ans =

1.5682 2.1616 2.7551 3.3485

4.9772 5.8329 6.6885 7.5441

8.3863 9.5041 10.6219 11.7397

top of page