Projection onto the $\ell$2 norm ball is known. Let the norm ball set reads $C = \left\{x \in \mathbb{R}^n: \left\| x - c \right\|_2^2 \leq d^2 \right\}$, where $c \in \mathbb{R}^n$ and $d \in \mathbb{R}$, then the projection onto this norm ball set can be shown as \begin{align} \Pi_{C} \left ( y \right) = c + \frac{d}{\max \left\{\left\| y - c \right\|_2, d \right\}} \left( y - c \right) \ . \end{align}

How to obtain a projection onto the weighted $\ell$2 norm ball, where the set $C = \left\{x \in \mathbb{R}^n: \left\| x - c \right\|_W^2 \leq d^2 \right\}$, where $W$ is a positive definite matrix?

Note: There is an attempt for weighted l2 norm projection, but we don't have the same problem definition (or may be I can't figure out yet how to massage that answer).

My partial attempt:

Following Brian's comments, I have made an attempt. But I am stuck and not able to compute the Lagrange multiplier.

The weighted $\ell$2 projection problem can be expressed as \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & \left\|y-x\right\|_2^2\\ \text{subject to }\quad & \left\|x-c\right\|_W^2 \leq d^2 \end{align}

Forming the Lagrangian: \begin{align*} L\left(x, \lambda\right) &= \left\|y-x\right\|_2^2 + \lambda \left( \left[ (x-c)^T W (x-c) \right]- d^2 \right) . \end{align*}

Then according to the stationarity condition of the KKT conditions, \begin{align*} \frac{\partial L}{\partial x} = 0 \Rightarrow &= -(y - x) + \lambda \left(W (x-c) \right) = 0 \\ &\Leftrightarrow x = \left( I + \lambda W \right)^{-1} \left(\lambda W c + y \right). \end{align*}

Now I am stuck and don't know how to obtain $\lambda$ in closed-form? I thought about considering the complementary slackness of the KKT conditions, but then it becomes too much involved for me. Say $\lambda > 0$, then \begin{align} (x-c)^T W (x-c) = d^2 \ . \end{align} If I plugin $x = \left( I + \lambda W \right)^{-1} \left(\lambda W c + y \right)$ in the above equation, then I don't know how to solve for $\lambda$. If we can't find it in closed-form, then how to obtain this iteratively? How about if $W$ is a diagonal matrix, then can we obtain $\lambda$ in closed-form?

Further attempt: If $W$ is a diagonal matrix, then following the link, $i$th coordinate of $x$ can be written as \begin{align} x_i = \frac{\lambda W_i c_i + y_i}{1 + \lambda W_i} . \end{align}

Now, plugging into the complementary slackness condition such that \begin{align} (x-c)^T W (x-c) &= \|W^{1/2} (x-c)\|^2 = d^2 \\ &\Leftrightarrow \sqrt{W_i} (x_i - c_i) = \pm d \\ &\Leftrightarrow \lambda = \frac{\pm 1}{d \sqrt{W_i}} \left(y_i - c_i \right) - \frac{1}{W_i} \ . \end{align} Is this correct in case of $W$ is a diagonal matrix?

Question: Would $\lambda$ be different for different coordinates of the vector? Hmm, should it not be a constant for all coordinates?

  • $\begingroup$ It's relatively easy to set this up as a constrained optimization problem and apply the Lagrange multiplier method. If your $W$ matrix is diagonal, this simplifies to the case discussed in the question you linked to. Is your $W$ diagonal? If not, then the problem is still relatively easy to solve by iterative schemes. $\endgroup$ Jan 20, 2019 at 3:26
  • $\begingroup$ Thank you Brian. I have made an attempt based on your suggestion (please see above). But I don't know how to obtain $\lambda$ in closed-form even if $W$ is a diagonal matrix. Can you help me how to solve for $\lambda$? Any reference? $\endgroup$
    – user550103
    Jan 20, 2019 at 8:05
  • $\begingroup$ Have you thought what the matrix is doing to space? Specifically to the ball? $\endgroup$
    – Royi
    Jan 24, 2019 at 14:19
  • $\begingroup$ @Royi my impression is that this matrix $W$ are giving different weights to respective coordinates. So, the norm ball may look non-spherical depending on the considered weights. Please correct me if my impression is wrong. $\endgroup$
    – user550103
    Jan 24, 2019 at 14:38
  • $\begingroup$ PSD Matrices has special shapes in space. I think it might assist you with the solution. $\endgroup$
    – Royi
    Jan 24, 2019 at 14:51

1 Answer 1


The objective function is given by:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} & \text{} \\ \text{subject to} \quad & {\left( x - c \right)}^{T} W \left( x - c \right) \leq d \end{align*}$$

Case I - Diagonal Matrix

In this case the matrix $ W $ is diagonal with $ {w}_{ii} \geq 0 $.

Let's assume we know how to solve this.

I could find a simple iterative method to find $ \lambda $ for this case but not a closed form solution. Though I'd guess it is doable. As we can change coordinates to make the Ellipsoid into a Ball and then go back.

Case II - Positive Definite Matrix

In this case the matrix $ W $ a Positive Semi Definite (PSD) Matrix - $ W \succeq 0 $.

Since $ W $ is a PSD matrix it can be written as (Eigen Decomposition):

$$ W = {P}^{T} D P $$

Where $ P $ is Unitary Matrix and $ D $ is Diagonal Matrix with $ {d}_{ii} \geq 0 $.

Then one could rewrite the problem as:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} & \text{} \\ \text{subject to} \quad & {\left( x - c \right)}^{T} {P}^{T} D P \left( x - c \right) \leq d \end{align*}$$

Defining $ v = P x $, $ z = P y $ and $ e = P c $ one could rewrite the problem as:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} & \text{} \\ \text{subject to} \quad & {\left( v - e \right)}^{T} D \left( v - e \right) \leq d \end{align*}$$

Now, since $ P $ is Unitary Matrix which means it preserves the $ {L}_{2} $ norm and is invertible then $ \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} = \frac{1}{2} {\left\| P \left( x - y \right) \right\|}_{2}^{2} = \frac{1}{2} {\left\| v - z \right\|}_{2}^{2} $ and the whole problem becomes:

$$\begin{align*} \arg \min_{v} \quad & \frac{1}{2} {\left\| v - z \right\|}_{2}^{2} & \text{} \\ \text{subject to} \quad & {\left( v - e \right)}^{T} D \left( v - e \right) \leq d \end{align*}$$

Where $ D $ is Diagonal Matrix which is exactly Case I we assume we know how to solve.


I created a MATLAB code to solve the problem (The general).
The code is available at my StackExchange Mathematics Q3079400 GitHub Repository.

  • $\begingroup$ This looks good, Royi. I agree that we need to know if a closed form exists for the diagonal case. +1 $\endgroup$
    – user550103
    Feb 3, 2019 at 12:53
  • $\begingroup$ As I wrote, it is easy to solve with few iterations of Binary Search. The question is if that what you want? I hope @BrianBorchers have a closed form solution for that. $\endgroup$
    – Royi
    Feb 3, 2019 at 16:04
  • 1
    $\begingroup$ Related - math.stackexchange.com/questions/3581340. $\endgroup$
    – Royi
    Apr 26, 2020 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .