Orthogonal projections

MATLAB function	underlying set	input	assumptions
proj_Euclidean_ball^[*]	Euclidean ball $B[c,r]=\{x: \\|x-c\\|\leq r\}$	$x$ - point to be projected (vector/matrix) $c$ - center of the ball (vector/matrix) $r$ - positive radius (positive scalar)	l₂ or Frobenius norm
proj_box^[*]	box ${\rm Box}[\ell,u] = \{ x : \ell \leq x \leq u\}$	$x$ - point to be projected (vector/matrix) $\ell$ - lower bounds (vector/matrix/scalar) $u$ - upper bounds (vector/matrix/scalar)	$\ell \leq u$
proj_affine_set	affine set $\{x: Ax=b\}$	$x$ - column vector to be projected $A$ - mxn matrix $b$ - m-length column vector	$A$ with full row rank
proj_halfspace^[*]	half-space $H_{a,b}^- = \{x: \langle a, x \rangle \leq b\}$	$x$ - point to be projected (vector/matrix) $a$ - vector/matrix $b$ - scalar	$H_{a,b}^{-} \neq \emptyset$
proj_two_halfspaces^[*]	intersection of two half-spaces $H_{a_1,b_1}^- \cap H_{a_2,b_2}^-$ $=\{ x: \langle a_1, x \rangle \leq b_1, \langle a_2,x_2 \rangle \leq b_2 \}$	$x$ - point to be projected (vector/matrix) $a_1$ -vector/matrix $b_1$ - scalar $a_2$ - vector/matrix $b_2$ - scalar	$\{a_1,a_2\}$ linearly independent
proj_Lorentz	Lorentz cone $L^n=\left \{x \in {\mathbb R}^{n+1} : \\|x_{\{1,\ldots,n\}}\\|_2 \leq x_{n+1} \right \}$	$x$ - (n+1)-length column vector to be projected
proj_hyperplane_box^[*]	intersection of a hyperplane and a box $H_{a,b} \cap {\rm Box}[\ell,u]\\=\{x: \langle a,x \rangle =b, \ell \leq x \leq u\}$	$x$ - point to be projected (vector/matrix) $a$ -vector/matrix $b$ - scalar $\ell$ - lower bounds (vector/matrix/scalar) $u$ - upper bounds (vector/matrix/scalar)	$H_{a,b} \cap {\rm Box}[\ell,u]\neq \emptyset$
proj_halfspace_box^[*]	intersection of a halfspace and a box $H_{a,b}^- \cap {\rm Box}[\ell,u] \\= \left \{ x : \langle a, x \rangle \leq b, \ell \leq x \leq u\right \}$	$x$ - point to be projected (vector/matrix) $a$ -vector/matrix $b$ - scalar $\ell$ - lower bounds (vector/matrix/scalar) $u$ - upper bounds (vector/matrix/scalar)	$H_{a,b}^-\cap {\rm Box}[\ell,u] \neq \emptyset$
proj_simplex^[*]	r-simplex $\Delta_n(r)=\{ x : e^T x=r, x \geq 0\}$ r-full simplex $\Delta_n^{+}(r)=\{ x : e^T x\leq r, x \geq 0\}$	$x$ - point to be projected (vector/matrix) $r$ - radius (scalar) eq_flag - a flag that determines whether the projection is onto the r-simplex ('eq') or the r-full simplex ('ineq')	$r>0$
proj_product^[*]	product superlevel set $\{x: \Pi_{i=1}^n x_i \geq r\}$	$x$ - point to be projected (vector/matrix) $r$ - scalar	$r>0$
proj_l1_ball^[*]	l₁ ball $\{x : \\|x\\|_1 \leq r\}$	$x$ - point to be projected (vector/matrix) $r$ - radius	$r>0$
proj_l1ball_box^[*]	intersection of weighted l₁ ball and a box $\{ x: \\|w \odot x\\|_1 \leq r, -u \leq x \leq u\}$	$x$ - point to be projected (vector/matrix) $w$ -weights (vector/matrix) $r$ - radius (scalar) $u$ - bounds (vector/matrix/scalar)	$r,u,w \geq 0$
proj_psd	cone of positive semidefinite matrics (psd cone) ${\mathbb S}^n_+ =\{ X : X \succeq 0\}$	$X$ - matrix to be projected	$X$ symmetric
proj_spectral_box_sym	spectral box (in the set of nxn symmetric matrices) $\{ X \in {\mathbb S}^n: \ell I \preceq X \preceq u I\}$	$X$ - matrix to be projected $\ell$ - lower bound (scalar) $u$ - upper bound (scalar)	$\ell \leq u$ $X$ symmetric
proj_spectral_ball	spectral-norm ball $B_{\\|\cdot\\|_{S_{\infty}}}[0,r] = \{ X : \sigma_1(X) \leq r\}$	$X$ - matrix to be projected $r$ - radius (scalar)	$r>0$
proj_nuclear_ball	nuclear-norm ball $B_{\\|\cdot\\|_{S_1}}[0,r] = \{X: \\|X\\|_{S_1} \leq r\}$	$X$ - matrix to be projected $r$ - radius (scalar)	$r>0$
proj_spectahedron	r-spectahedron $\Upsilon_n(r) = \{ X \in {\mathbb S}^n_+ : {\rm Tr}(X)=r\}$ r-full spectahedron $\Upsilon_n^+(r) = \{ X \in {\mathbb S}^n_+ : {\rm Tr}(X)\leq r\}$	$X$ - symmetric matrix to be projected $r$ - radius (scalar) eq_flag - a flag that determines whether the projection is onto the r-spectahedron ('eq') or the r-full spectahedron ('ineq')	$r>0$ $X$ symmetric

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

Remarks:

"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

proj_affine_space

proj_box

proj_Euclidean_ball

proj_halfspace

proj_halfspace_box

proj_hyperplane_box

proj_Lorentz

proj_l1_ball

proj_l1ball_box

proj_nuclear_ball

proj_product

proj_psd

proj_simplex

proj_spectahedron

proj_spectral_ball

proj_spectral_box_sym

proj_two_halfspaces

proj_Euclidean_ball

Usage: proj_Euclidean_ball(x,[c],[r])

Input:

x - point to be projected (vector/matrix)

c - center of the ball (vector/matrix) [default c=0]
r - positive radius (positive scalar) [default r=1]

Method: employs the formula

$P_{B[c,r]}(x)=c+\frac{r}{\max\{\|x-c\|,r\}}(x-c)$

Example: project the vector [1;2;3] onto the ball with center [0;0;0] and radius 2

>> proj_Euclidean_ball([1;2;3],zeros(3,1),2)

ans =

0.5345

1.0690

1.6036

If the input is a matrix, then the corresponding norm is the Frobenius norm

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

ans =

1.0000 1.1348 1.2697

1.4045 1.5394 1.6742

The default value of the radius is 1, so there is no need to put it as an input

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

ans =

1.0000 1.1348 1.2697

1.4045 1.5394 1.6742

top of page

proj_box

Usage: proj_box(x,l,u)

Input:

x - point to be projected (vector/matrix)
l - lower bounds (vector/matrix/scalar)

u- upper bounds (vector/matrix/scalar)

Method: employs the formula

$P_{\rm Box[\ell,u]}(x)_i = \min\{\max\{x_i,\ell_i\},u_i\}$

Example: project the vector [1;-1;2] onto the box with lower bounds [0;0;3]and upper bounds [2;3;5]

^{>> proj_box([1;-1;2], [0;0;3], [2;3;5])

ans =

1
0
3}

upper and/or lower bounds may be infinite. The nonnegative orthant of dimension 3, for example, is described by a lower bounds vector [0;0;0] and upper bounds vector of all-infinities.

Thus, to project the vector [-2;2;3]onto the nonnegative orthant, the following should be executed.

>> proj_box([-2;2;3],zeros(3,1),Inf*ones(3,1))

ans =

0

2

3

top of page

proj_affine_set

Usage: proj_affine_set(x,A,b)

Input:

x - column vector to be projected
A - mxn matrix
b - m-length column vector

Method: employs the formula

$P_{\{y:Ay=b\}}(x)=x-A^T(AA^T)^{-1}(Ax-b)$

Example: project the vector [1;0;1] on the affine set

$\{(x_1,x_2,x_3)^T : x_1+x_2+x_3=1,x_1=x_2\}$

>> A=[1,1,1;1,-1,0];

>> b=[1;0];

>> proj_affine_set([1;0;1],A,b)

ans =

0.1667

0.6667

top of page

proj_halfspace

Usage: proj_halfspace(x,a,b)

Input:

x - point to be projected (vector/matrix)
a - vector/matrix

b - scalar

Method: employs the formula

$P_{H_{a,b}^-}(x)=x-\frac{[\langle a,x\rangle -b]_+}{\|a\|^2}a$

Example: project the matrix [1,0,5;-4,1,-1] onto the half-space

$\left \{X \in {\mathbb R}^{2,3} : \sum_{i=1}^2 \sum_{j=1}^3 X_{ij} \leq 1\right \}$

>> X=[1,0,5;-4,1,-1];

>> proj_halfspace(X,[1,1,1;1,1,1],1)

ans =

0.8333 -0.1667 4.8333

-4.1667 0.8333 -1.1667

As a sanity check, we can compute the sum of all components in the obtained matrix

>> sum(sum(ans))

ans =

1.0000

top of page

proj_two_halfspaces

Usage: proj_two_halfspaces(x,a1,b1,a2,b2)

Input:

x - point to be projected (vector/matrix)

a1 -vector/matrix
b1 - scalar
a2 - vector/matrix

b2- scalar

Method: Employs the formula

$P_T(x) = \left \{ \begin{array}{ll} x & \alpha\leq 0, \beta \leq 0\\ x-(\beta/\nu) a_2 & \alpha \leq \pi(\beta/\nu), \beta>0\\ x-(\alpha/\nu) a_1 & \beta \leq \pi(\alpha/\nu), \alpha>0\\ x+(\alpha/rho)(\pi a_2-\nu a_1)+(\beta/\rho)(\pi a_1-\mu a_2) & {\rm otherwise}\end{array} \right.$

where

$T = \{x : \langle a_1,x \rangle \leq b_1, \langle a_2, x \rangle \leq b_2\},\alpha = \langle a_1,x \rangle -b_1, \beta = \langle a_2, x \rangle -b_2, \\ \pi = \langle a_1,a_2 \rangle, \mu = \|a_1\|^2, \nu = \|a_2\|^2, \rho = \mu\nu-\pi^2$

Example: project the vector [1;-1;2] onto the following intersection of two half-spaces:

$\left \{ x \in {\mathbb R}^3 : x_1+x_2+x_3 \leq 1, x_2 \geq 0 \right \}$

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

ans =

0

1

top of page

proj_Lorentz

Usage: proj_Lorentz(x)

Input:

x - (n+1)-length column vector to be projected

Method: Employs the formula

$P_{L^n}(x,s) = \left \{ \begin{array}{ll} \left( \frac{\|x\|_2+s}{2\|x\|_2} x, \frac{\|x\|_2+s}{2}\right) & \|x\|_2 \geq |s|,\\ (0,0), & s<\|x\|_2<-s\\ (x,s) & \|x\|_2\leq s\end{array}\right.$

Example: project the vector [2;3;1] onto L²

>> proj_Lorentz([2;3;1])

ans =

1.2774

1.9160

2.3028

top of page

proj_hyperplane_box

Usage:

proj_hyperplane_box(x,a,b,[l],[u])

Input:

x - point to be projected (vector/matrix)
a - vector/matrix
b - scalar

l - lower bounds (vector/matrix/scalar) [default=-Inf]

u - upper bounds (vector/matrix/scalar) [default=Inf]

Method: the projection onto

$C = H_{a,b} \cap {\rm Box}[\ell,u] = \{x \in {\mathbb R}^n : a^T x = b, \ell \leq x \leq u\}$

is computed by the formula

$P_C(x) = P_{{\rm Box}[\ell,u]}(x-\mu^* a),$

where $\mu^*$ is a solution of the equation

$\varphi(\mu)=a^T P_{{\rm Box}[\ell,u]}(x-\mu a)- b$

The root is found by bisection.

Example: To project the matrix [1,-2;3,1] on the set of all 2x2 matrices with equal sums of rows:

$\left \{ \begin{pmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{pmatrix}: x_{11}+x_{12}=x_{21}+x_{22} \right \}$

execute

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

ans =

-0.2500 2.7500

2.2500 0.2500

The same can be accomplished without specifying the lower and upper bounds since these are the default values.

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

ans =

-0.2500 2.7500

2.2500 0.2500

If we add the constraint that all the components are nonnegative and the (1,2)-element is bounded above by 2.7, we can compute the projection by the following command.

>> proj_hyperplane_box([-1,2;3,1],[1,1;-1,-1],0,0,[Inf,2.7;Inf,Inf])

ans =

0 2.6667

2.3333 0.3333

top of page

proj_halfspace_box

Usage:

proj_halfspace_box(x,a,b,[l],[u])

Input:

x - point to be projected (vector/matrix)
a - vector/matrix
b - scalar

l - lower bounds (vector/matrix/scalar) [default=-Inf]

u - upper bounds (vector/matrix/scalar) [default=Inf]

Method: the projection onto

$C=H_{a,b}^{-} \cap {\rm Box}[\ell,u]= \{ x: \langle a, x \rangle \leq b, \ell \leq x \leq u \}$

is computed by the formula

$P_C(x) = P_{{\rm Box}[\ell,u]}(x-\mu^* a),$

where $\mu^*$ is a nonnegative solution of the equation

$\varphi(\mu)=a^T P_{{\rm Box}[\ell,u]}(x-\mu a)- b$

The root is found by bisection.

Example: project the vector [1;2;2;-1] onto the halfspace

$C=\{ x : \Pi_{i=1}^n x_i \geq r\}$

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

ans =

0.5000

1.5000

2.5000

-0.5000

The projection can obviously be computed using the function proj_halfspace

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

ans =

0.5000

1.5000

2.5000

-0.5000

To project (1,2,2,-1)^T onto the set

execute

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

ans =

0.5000

1.5000

2.0000

0

top of page

proj_simplex

Usage:

proj_simplex(x,[r],[flag_eq])

Input:

x - point to be projected (vector/matrix)
r - radius (positive scalar) [default=1]

eq_flag - a flag indicating whether the constraint on the sum is an equality constraint ('eq') or an inequality constraint ('ineq') [default='eq']

Method: calls

proj_hyperplane_box(x,ones(size(x)),r,zeros(size(x))) if flag='eq' or

proj_halfspace_box(x,ones(size(x)),r,zeros(size(x))) if flag='ineq'

Example: project the vector [0;0.5;-0.1] onto the unit simplex

>> proj_simplex([0;0.5;-0.1])

ans =

0.2000

0.7000

0.1000

projecting the same vector onto the unit full simplex gives a different result

>> proj_simplex([0;0.5;-0.1],[],'ineq')

ans =

0

0.5000

0

The projection onto the 2-simplex set is computed as follows

>> proj_simplex([0;0.5;-0.1],2)

ans =

0.5333

1.0333

0.4333

top of page

proj_product

Usage:

proj_product(x,r)

Input:

x - point to be projected (vector/matrix)
r - positive scalar

Method: the projection onto

$C = \{x: \Pi_{i=1}^n x_i \geq r\}$

is computed by the formula

$P_C(x)=\left \{ \begin{array}{ll} x & x\in C\\ \left ( \frac{x_j+\sqrt{x_j^2 +4\lambda^*}}{2}\right)_{j=1}^n & x \notin C \end{array} \right.$

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

$\varphi(\lambda) = \textstyle -\sum_{j=1}^n \log \left ( \frac{x_j+\sqrt{x_j^2+4 \lambda}}{2} \right )+\log \alpha$

The root is found by bisection.

Example: project the vector [2;1;-3] onto the set

$\{ (x_1,x_2,x_3)^T >0 : x_1x_2x_3\geq 1\}$

>> proj_product([2;1;-3],1)

ans =

2.3717

1.5638

0.2696

top of page

proj_l1_ball

Usage:

proj_l1_ball(x,[r])

Input:

x - point to be projected (vector/matrix)
r - radius (positive scalar) [default=1]

Method: calls

sign(x) .* proj_simplex(abs(x),r,'ineq') ;

Example: project the vector [10;-4;5] onto the l₁ unit ball (no need to specify the radius as the default is 1)

>> proj_l1_ball([10;-4;5])

ans =

1

0

Project the same point on the l₁ ball with radius 10

>> proj_l1_ball([10;-4;5],10)

ans =

7

-1

2

The function can also be used on matrices where the l₁ norm means the sum of absolute values of all components of the matrix. To project [1,2,-1;2,1,1] onto the l₁ ball with radius 2 the following should be executed

>> proj_l1_ball([1,2,-1;2,1,1],2)

ans =

0 1 0

1 0 0

top of page

proj_l1ball_box

Usage:

proj_l1ball_box(x,[r],[w],[u])

Input:

x - point to be projected (vector/matrix)
r - radius (positive scalar) [default=1]

w - weights (vector/matrix) [default=vector/matrix of all ones]

u - bounds (vector/matrix/scalar) [defalut=Inf]

Method: the projection onto the set

$C = \left \{ x : \sum_{i} w_i |x_i| \leq r, -u \leq x \leq u \right \}$

is computed by the formula

$P_C(x) = \left \{ \begin{array}{ll} P_{{\rm Box}[-u,u]}(x), & w^T|P_{{\rm Box}[-u,u]}(x)|\leq r,\\ \mathcal{S}_{\lambda^*w,u}(x), & w^T|P_{{\rm Box}[-u,u]}(x)|> r\end{array} \right.$

where

${\mathcal S}_{\lambda w,r}(x)\equiv \left ( \min\{\max\{|x_i|-\lambda w_i,0\},u_i\} {\rm sign}(x_i)\right )_{i=1}^n$

and $\lambda^*$ is a root of the function

$\varphi(\lambda) =w^T | {\mathcal S}_{\lambda w,u}(x)|-r$

Example: project the vector [1;2;-3] onto the unit l₁-norm ball

>> proj_l1ball_box([1;2;-3])

ans =

0

-1

This can also be computed using proj_l1_ball

>> proj_l1_ball([1;2;-3])

ans =

0

-1

The projection of [1;2;-3] onto the set

$\left \{(x_1,x_2,x_3)^T: |x_1|+|x_2|+|x_3|\leq 1, |x_i| \leq 0.5 \right \}$

is computed by

>> proj_l1ball_box([1;2;-3],[],1,0.5)

ans =

0

0.5000

-0.5000

projecting [1;2;-3] onto

$\left \{(x_1,x_2,x_3)^T: |x_1|+|x_2|\leq 0.1, |x_i| \leq 0.5 \right \}$

can be done by

>> proj_l1ball_box([1;2;-3],[1;1;0],0.1,0.5)

ans =

0

0.1000

-0.5000

top of page

proj_psd

Usage:

proj_psd(X)

Input:

X - symmetric matrix to be projected

Method: employs the formula

$X = Udiag([\lambda(x)]_+)U^T$

where

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

is a spectral decomposition of X.

Example: the matrix [1,2;2,1] is not positive semidefinite

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

ans =

-1

3

Projecting it onto the cone of positive semidefinite matrices is done by the command

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

ans =

1.5000 1.5000

The resulting matrix is indeed a positive semidefinite matrix

>> eig(ans)

ans =

0

3.0000

top of page

proj_spectral_box_sym

Usage:

proj_spectral_box_sym(X,l,u)

Input:

X - symmetric matrix to be projected

l - lower bound (scalar)

u - upper bound (scalar)

Method: the projection onto

$C = \{X \in {\mathbb S}^n: \ell I \preceq X \preceq uI\}$

is computed by the formula

$P_C(X)=U {\rm diag}(v) U^T, v = (\min\{\max\{\lambda_i(X),\ell\},u\})_{i=1}^n$

where

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

is a spectral decomposition of X.

Example: the eigenvalues of the matrix [1,2,1;2,1,2;1,2,1] are

>> X=[1,2,1;2,1,2;1,2,1];

>> eig(X)

ans =

-1.3723

-0.0000

4.3723

To project the matrix onto the set of matrices with eigenvalues between -1 and 4, we execute

>> ans=proj_spectral_box_sym(X,-1,4)

ans =

0.9676 1.7408 0.9676

1.7408 1.0648 1.7408

0.9676 1.7408 0.9676

The eigenvalues of the resulting matrix are indeed between -1 and 4

>> eig(ans)

ans =

-1.0000

0.0000

4.0000

top of page

proj_spectral_ball

Usage:

proj_spectral_ball(X,[r])

Input:

X - matrix to be projected

r - radius (positive scalar) [default=1]

Method: employs the formula

$P_{B_{\|\cdot\|_{S_{\infty}}}[0,r]} (X)=U {\rm dg}(v) V^T, v_i=\min\{\sigma_i(X),r\}$

where

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

is a singular value decomposition of X.

Example: the singular values of the matrix [1,2,0;1,-1,1] are

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

>> svd(A)

ans =

2.3268

1.6080

The projection of the matrix onto the spectral ball with radius 2 is

>> proj_spectral_ball(A,2)

ans =

0.9298 1.7105 0.0497

1.0291 -0.8801 0.9794

The singular values of the resulting matrix are indeed smaller or equal to 2

>> svd(ans)

ans =

2.0000

1.6080

top of page

proj_nuclear_ball

Usage:

proj_nuclear_ball(X,[r])

Input:

X - matrix to be projected

r - radius (positive scalar) [default=1]

Method: employs the formula

$P_{B_{\|\cdot\|_{S_1}}[0,r]}(X)=U P_{B_{\|\cdot\|_{1}}[0,r]}({\rm dg}(X))V^T$

where

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

is a singular value decomposition of X.

Example: the singular values of the matrix [1,2,0;1,-1,1] are

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

>> svd(A)

ans =

2.3268

1.6080

The projection of the matrix on the nuclear norm ball with radius 1 is

>> proj_nuclear_ball(A)

ans =

0.2284 0.7558 -0.0997

0.0290 -0.3281 0.1287

As a sanity check, we can observe that the vector of singular values of the projected matrix sums up to 1

>> sum(svd(ans))

ans =

1

top of page

proj_spectahedron

Usage:

proj_spectahedron(x,[r],[flag_eq])

Input:

X - symmetric matrix to be projected
r - radius (positive scalar) [default=1]

eq_flag - a flag indicating whether the constraint on the sum is an equality constraint ('eq') or an inequality constraint ('ineq') [default='eq']

Method: calls

V * diag(proj_simplex(diag(D),r,eq_flad)) * V' ;

where [V,D]=eig(X)

Example: The projection onto the unit-spectahedron of the matrix [1,2,0;2,1,2;0,2,1] is

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

>> proj_spectahedron(A)

ans =

0.2500 0.3536 0.2500

0.3536 0.5000 0.3536

0.2500 0.3536 0.2500

The eigenvalues of the output matrix are, as expected, in the unit-simplex

>> eig(ans)

ans =

-0.0000

0.0000

1.0000

To project the matrix onto the spectahedron with radius 3, execute

>> proj_spectahedron(A,3)

ans =

0.7714 1.0303 0.6857

1.0303 1.4571 1.0303

0.6857 1.0303 0.7714

top of page