could anybody give me some suggestions on solving this least-squares problem?
Find $x\in R^{n}$ that minimize $||Ax||_2$ subject to $||Bx||_2=1$, with $A\in R^{n×n} $ always full rank, $B\in R^{n×n}$ not necessary full rank.
Thanks for your help
Asked
Active
Viewed 149 times
1 Answers
0
The task is to minimize $f(x) = x^\top A^\top Ax$ s.t. $g(x) = x^\top B^\top Bx - 1 = 0$. Lagrange: $$ A^\top\!Ax = \lambda\cdot B^\top\!Bx. $$ $\lambda = 0$ would imply that $x=0$, which is not feasible. So, $\lambda\neq 0$. Hence, $(A^\top A)^{-1}B^\top Bx = \lambda^{-1}x$ so that $\lambda^{-1}$ must be an eigenvalue of $(A^\top A)^{-1}B^\top B$ and $x$ a corresponding eigenvector. From the constraint you also get that $\|Ax\|^2 = \lambda$. So, $\lambda>0$ and $\sqrt{\lambda}$ is the optimal value. Therefore, the minimizers of this problem are the eigenvectors $x$ of $(A^\top A)^{-1}B^\top B$ with $\|Bx\|=1$ corresponding to the largest eigenvalue of $(A^\top A)^{-1}B^\top B$.
By the way, this is not really a least squares problem.
amsmath
- 10,633
-
Thanks for your answer. I just wonder that do you consider when B is not full rank? – Eden Willy Feb 28 '21 at 07:06
-
I assumed this throughout. – amsmath Feb 28 '21 at 07:12
-
Oh, ok. Thank you for suggestion – Eden Willy Feb 28 '21 at 07:14
-
I doubt that the answer is correct. The Lagange (derivative in x) is not what you wrote – NN2 Feb 28 '21 at 08:10
-
It must be $Ax + x^TA =\lambda( Bx +x^TB)$ – NN2 Feb 28 '21 at 08:17
-
@NN2 $Ax + x^TA$ doesn't even make sense. – amsmath Feb 28 '21 at 08:23
-
This kind of problem is quite new to me. Could anyone please explain a bit more on the Lagrange method for this problem. Where the equation comes from? – Eden Willy Feb 28 '21 at 08:24
-
@EdenWilly Lagrange says: If $x^$ is a minimizer of $\min f(x)$ s.t. $g(x)=0$, then there exists $\lambda\in\mathbb R$ such that $\nabla f(x^) = \lambda\cdot\nabla g(x^*)$. – amsmath Feb 28 '21 at 08:27
-
You dont write corectly the derivative! – NN2 Feb 28 '21 at 08:29
-
oh I see, @NN2 is correct for the derivative term. $d/dx(x^TAx)=(A+A^T)x$ – Eden Willy Feb 28 '21 at 08:31
-
@NN2 Yes, I did because I don't differentiate $x^TAx$ but $x^TA^TAx$ and its derivative is $2A^TAx$. – amsmath Feb 28 '21 at 08:32
-
Ok I see now. . – NN2 Feb 28 '21 at 08:38
-
@NN2 Well, then you can upvote my answer again. – amsmath Feb 28 '21 at 08:42
-
Sorry, the answer is locked by the system so I can’t modify that (unless you modify something in your answer) – NN2 Feb 28 '21 at 11:26
-
@amsmath, hi, I have a question, the minimizer of this problem is the eigenvector corresponding to the largest or smallest eigenvalue? – Eden Willy Feb 28 '21 at 12:24
-
@EdenWilly I wrote it: largest. If you understand my answer, then you'll understand why. – amsmath Feb 28 '21 at 16:05
-
@amsmath Oh ok, I got it. Thanks – Eden Willy Mar 01 '21 at 23:32
-
@amsmath Hi, i have a problem when solving this, could you please explain a bit. I try to find the eigenvector corresponding to largest eigenvalue of $(A^TA)^{-1}B^TB$ as the x vector. However, the result cannot satisfy the constraint. How should I solve this? Many thanks – Eden Willy Mar 08 '21 at 11:01
-
In my answer I write "the eigenvectors $x$ of $(A^TA)^{-1}B^TB$ with $|Bx|=1$." If you have found an eigenvector $u$, then $x=|Bu|^{-1}u$ is your minimizer. – amsmath Mar 08 '21 at 11:46
-
Hi @amsmath, I have tried your suggestion but it's still the same, the vector $x$ is equal to $u$. – Eden Willy Mar 09 '21 at 00:39
-
If $x=u$, then $|Bu|^{-1}u = u$, which implies $|Bu|=1$, so $u$ already satisfied the constraint before. – amsmath Mar 14 '21 at 18:28
-
1@amsmath Hi, thank you for your support, I can solve this problem now. – Eden Willy Mar 17 '21 at 14:01