0
$\begingroup$

I am stuck with the following problem. Could someone give me some hints? Thanks a lot.

Problem setting: Let $X\in R^{N\times k}$ and $\theta\in R^k$. Now we consider $\hat{\theta} = \arg\min \|X\theta\|^2_2$ with constraint of $\|\theta\|_2=1$. Please solve $\hat{\theta}$.

I have considered the problem as $\hat{\theta} = \arg\min \theta'X'X\theta$ with constraint of $\theta'I \theta = 1$, where we have $I\in R^{k\times k}$.

Now by taking derivative of $\theta'X'X\theta$, we have $2 X'X\theta = 0$ and $\theta'I \theta = 1$. It seems to be a contradiction. Is there any hints for solving the problem? Thanks in advance.

$\endgroup$
  • $\begingroup$ You can't just take the derivative of an objective function in a constrained case like this; you have to employ a Lagrangian method, for instance. Though in this particular case, the result follows from the basic definition of singular values. Is that an acceptable way to solve this, or are they asking you to take a particular approach? $\endgroup$ – Michael Grant Mar 16 '16 at 12:41
  • $\begingroup$ @MichaelGrant Thanks for reply. If we consider the Lagrangian method, it is still weird. Specifically, we have $L=\theta'X'X\theta + \lambda(\theta'\theta-1)$. By taking the derivative of $L$ with respect to $\theta$, we have $2X'X\theta + 2\lambda\theta = 0$. There is no solution for $\theta$?! There is no constraint on the approach for solving the problem. Thanks. $\endgroup$ – aaronyxt Mar 16 '16 at 12:50
  • $\begingroup$ I'm not sure what you mean. There are myriad solutions to that equation. Any $\theta$ in the null space of $X^TX+\lambda I$ will do. $\endgroup$ – Michael Grant Mar 16 '16 at 12:51
  • $\begingroup$ Well, I mean that there is no unique closed-form solution for $\theta$. It seems that the problem setting is problematic if we finally want to have a closed form solution. $\endgroup$ – aaronyxt Mar 16 '16 at 12:56
  • 1
    $\begingroup$ Closed form solutions are overrated. The answer here is that theta is the right singular vector associated with the minimum singular value. $\endgroup$ – Michael Grant Mar 16 '16 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.