# Least Squares with Euclidean (${L}_{2}$) Norm Constraint

Suppose I have set of samples $(x_i,y_i), 1 \leq i \leq n$. I am interested in solving the following optimization problem: $$\min \sum_{i=1}^n (y_i-a^\top x_i)^2, \quad \text{s.t } \|a\|_{2} = 1.$$

If we assume that $\sum_i x_i x_i^\top$ is invertible, I am wondering if one can prove that the solution to the above optimization problem is $$a^\ast=\frac{\left(\sum_i x_i x_i^\top \right)^{-1} (\sum_i x_i y_i)}{\|\left(\sum_i x_i x_i^\top \right)^{-1} (\sum_i x_i y_i)\|}$$ Does the above solution still hold if we relax the constraint to be $\|a\|_{2} \leq 1$? Assuming that the above solution does not hold, in this inequality constrained case, does running a projected gradient descent guaranteed to find the true minimum since the problem is convex?

• Well of course, what if all of the $y_i$ values are zero? Commented Aug 19, 2017 at 22:43
• The vector you provided, in general, is not a solution. However, I believe the problem might be solvable, under some conditions, using extensions of the well-known $\mathcal{S}$-Lemma, which might help you transform the problem to an equivalent SDP. Commented Aug 20, 2017 at 5:44
• @Alex: Does there exist a closed form solution for this problem? Even considering different cases is fine. Commented Aug 20, 2017 at 14:04
• To the best of my knowledge - no. Commented Aug 21, 2017 at 16:56
• @pikachuchameleon, Could you review my answer?
– Royi
Commented May 10, 2021 at 4:44

I will try to fully solve it later but just think of the following case, what if the Least Squares solution already have an $${L}_{2}$$ norm which is less then 1?

Your solution will scale it and probably will make not the optimal.

So the solution must be composed of 2 cases, 1 if the LS solution obeys the relaxed constraint and the other not.

By the way, your solution, which is basically projection onto the Euclidean Unit Ball, can be the projection step in numerical solution using the Projected Gradient Method.

## My Solution

First, let's rewrite the problem as:

\begin{alignat*}{3} \text{minimize} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & {x}^{T} x \leq 1 \end{alignat*}

The Lagrangian is given by:

$$L \left( x, \lambda \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \frac{\lambda}{2} \left( {x}^{T} x - 1 \right)$$

The KKT Conditions are given by:

\begin{align*} \nabla L \left( x, \lambda \right) = {A}^{T} \left( A x - b \right) + \lambda x & = 0 && \text{(1) Stationary Point} \\ \lambda \left( {x}^{T} x - 1 \right) & = 0 && \text{(2) Slackness} \\ {x}^{T} x & \leq 1 && \text{(3) Primal Feasibility} \\ \lambda & \geq 0 && \text{(4) Dual Feasibility} \end{align*}

From (1) one could see that the optimal solution is given by:

$$\hat{x} = {\left( {A}^{T} A + \lambda I \right)}^{-1} {A}^{T} b$$

Which is basically the solution for Tikhonov Regularization of the Least Squares problem.

Now, from (2) if $$\lambda = 0$$ it means $${x}^{T} x = 1$$ namely $$\left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} = 1$$.

So one need to check the Least Squares solution first.
If $$\left\| {\left( {A}^{T} A \right)}^{-1} {A}^{T} b \right\|_{2} \leq 1$$ then $$\hat{x} = {\left( {A}^{T} A \right)}^{-1} {A}^{T} b$$.

Otherwise, one need to find the optimal $$\hat{\lambda}$$ such that $$\left\| {\left( {A}^{T} A + \lambda I \right)}^{-1} {A}^{T} b \right\| = 1$$.

For $$\lambda \geq 0$$ the function:

$$f \left( \lambda \right) = \left\| {\left( {A}^{T} A + \lambda I \right)}^{-1} {A}^{T} b \right\|$$

Is monotonically descending and bounded below by $$0$$.

Hence, all needed is to find the optimal value by any method by starting at $$0$$.

Basically the methods is solving iteratively Tikhonov Regularized Least Squares problem.

A demo code + solver can be found in my StackExchange Mathematics Q2399321 GitHub Repository.

• Why do you solve the problem with inequality constraints?? Commented Aug 21, 2017 at 22:24
• This what @pikachuchameleon asked for as convex relaxation of his problem. You can see when you get exactly ${x}^{T} x$ = 1. If needed you can also see how to get it in any case.
– Royi
Commented Aug 22, 2017 at 4:10
• Hi Royi, I know that your answer to this question is from a long time ago, but I am just curious: (i) Where does your point (2), "Slackness", come from, so why is in this case $\lambda\left( x^{T}x - 1\right) = 0$? (ii) Why does your point (4), "Dual Feasibility", hold? Couldn't we just take the Lagrangian to be $\mathcal L = \frac{1}{2}|| Ax - b ||^{2} - \lambda\dots$, and then (4) would not hold anymore? By the way, your solution for $\hat{x}$ misses a factor of $2$ in front of $\lambda I$.. :) Commented May 9, 2021 at 17:14
• @Hermi, I am not sure I get all your points. Would you open a new question and link it here? I will answer there. Regarding $\lambda$, I fixed it (Though it doesn't change the solution). Thanks for catching it.
– Royi
Commented May 9, 2021 at 18:47
• Fair enough! Please take a look at this one, I tried to expand a bit upon my questions: New Thread Also: The original reason I got to this question was when trying to prove the uniqueness of a very similar problem, if you could take a quick look at it, I would appreciate it: Least-Squares-Problem Commented May 9, 2021 at 21:07

Here is some progress in your solution:

First, note that this problem, in fact, has a solution since the unit sphere is compact and the objective function is continuous. Second, note that the problem is not convex since the restriction $\|a\|=1$ is not affine. On the other hand, the problem is equivalent to

$$min \sum_{i=1}^n(y_i -a^tx_i)^2,\;\; s.t\; \|a\|_2^2-1=0.$$ The advantage of this formulation is that it will make the constraint smooth and will simplify a lot of computation. Since the problem is nonconvex and the LICQ is satisfied at any feasible point, the most we can do is to find all KKT points and choose, among those, the one at which the function $$f(a)= \sum_{i=1}^n (y_i-a^Tx_i)^2$$ attains its minimum value. We proceed as follows:

The lagrangian in this case is

$$L(a,\lambda)= f(a)+\lambda(\|a\|_2^2-1),$$ from which we find that $a$ is KKT iff

$$0= \sum_{i=1}^n-2(y_i-a^Tx_i)x_i +2\lambda a.$$

Now we introduce some notation:

$$X=[x_1,\ldots, x_n],\; A= \sum_{i=1}^{n} x_ix_i^T,\; y= (y_1,\ldots,y_n)^T,\; v=Xy, \; b=A^{-1}v,\; b'=A^{-1}b.$$ Whith this in mind, the KKT condition is just

$$\lambda a= \sum_{i=1}^ny_ix_i -\sum_{i=1}^n(a^tx_i) x_i= Xy- Aa=v-Aa,$$ or equivalently, $$(A+\lambda I)a= v.$$ We only analyze the following case:

$\textbf{Case:}\;-\lambda \notin \sigma(A)$(the set of eigenvalues of A)

Hence $A+\lambda I$ is invertible. Furthermore, its inverse is given by

$$(A+\lambda I)^{-1} =A^{-1} - g(\lambda) A^{-2},$$ where $$g(\lambda)=\frac{\lambda}{1+\lambda \;Tr(A^{-1})}$$ (See this page and this page). So, we have in this case

$$a=(A+\lambda I)^{-1} v= A^{-1}v - g(\lambda) A^{-2}v= b- g(\lambda)b'.$$

But now we use the constraint $\|a\|_2^2=1$ to find $\lambda.$ We should have then

$$\|b\|^2_2- 2g(\lambda)b^Tb' +g^2(\lambda)\|b'\|_2^2=1,$$ from which

$$(\|b'\|_2^2)g^2(\lambda) +(-2b^Tb') g(\lambda)+(\|b\|^2_2-1)=0.$$ The trick now is to note that this is a quadratic equation in $g(\lambda).$ The discriminant of this equation is

$$D= 4((b^Tb')^2- \|b'\|_2^2(\|b\|2^2-1)).$$ If $D<0,$ we conclude that there are not KKT points in this case. Otherwise, we will have

$$g(\lambda)= \frac{b^Tb'+_{-}\sqrt{(b^Tb')^2- \|b'\|_2^2(\|b\|2^2-1)}}{\|b'\|_2^2}.$$

Denote $$r_{+}=\frac{b^Tb'+ \sqrt{(b^Tb')^2- \|b'\|_2^2(\|b\|2^2-1)}}{\|b'\|_2^2},\; r_{-}=\frac{b^Tb'- \sqrt{(b^Tb')^2- \|b'\|_2^2(\|b\|2^2-1)}}{\|b'\|_2^2}$$ This is of course the same as

$$\frac{\lambda}{1+\lambda \;Tr(A^{-1})}= r_{+},r_{-}.$$ From here we find that

$$\lambda_{+}= \frac{r_{+}}{1-r_{+}Tr(A^{-1})} \textrm{ and } \lambda_{-}= \frac{r_{-}}{1-r_{-}Tr(A^{-1}}$$ solve the equation, provided that $r_{+}\neq \frac{1}{Tr(A^{-1})}$ and $r_{-}\neq \frac{1}{Tr(A^{-1})}$ respectively. If one of this cases holds, we miss that solution. In conclusion, the only possible values of $\lambda$ so that the associated $a$ is $KKT$ are as above under the conditions $D\geq 0$ and $r_{+},r_{-}\neq \frac{1}{Tr(A^{-1})}.$

For the remaining case ($-\lambda \in \sigma(A)$) I have some ideas also. However, I don't think that a closed solution is possible. If I have some more time, I will think about it. Hope this helps.

• Really nice. I wrote the KKT and found case which requires 1D optimization for the value of $\lambda$. You went way farther :-).
– Royi
Commented Aug 21, 2017 at 11:53

No, it is pretty much never the solution, so you will not be able to prove that

• Can you give a counter-example or the proof regarding why it might not be the solution? Commented Aug 19, 2017 at 21:22
• @It's easy to create a counter example. Build a Linear System equation where the solution has an euclidean norm which is less than 1. Then your solution won't solve the relaxed problem.
– Royi
Commented Aug 20, 2017 at 5:31