Given a set of Points $p_i\in \Re^d$, I'm looking for the vector $x\in\Re^d$ with $\| x \|=1$ along a line so that minimizes $$\sum_{i}(\|p_i\|^2 - \langle p_i, x\rangle^2)$$
According to the first part of this question the right singular vector corresponding to the largest singular value can be used to do this however I have trouble proving that.
I can prove that it minimizes $$\sum_{i}(\|p_i\|^2 - \langle p_i, x\rangle)$$ So without the squared scalar product since it can be written as $\langle p_i, x\rangle=p_i^Tx$.
$\sum_{i}(p_i^Tx)$ can be written as $\|Ax\|_2^2$ where $A$ contains $p_i^T$ in every row.
And $\|Ax\|_2^2$ is maximized by using the Singular Value decomposition of $A$.
I'm just not sure if it also holds true for the original case
$\sum_{i}(\|p_i\|^2 - \langle p_i, x\rangle^2)$
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ isn't it easier to talk about maximizing $\sum_i \langle p_i,x\rangle^2$ subject to $\| x\|=1$ ? anyway I think it is not an NP-hard problem. $\endgroup$– Dima PasechnikCommented Nov 26, 2019 at 15:25
-
2$\begingroup$ You are maximizing a quadratic form on the unit sphere, this is known as trust region problem. $\endgroup$– Dima PasechnikCommented Nov 26, 2019 at 15:27
-
$\begingroup$ sorry, this question is probably better suited for math.stackexchange since I'm not a professional. Also as @DimaPasechnik wrote, this problem is the same as maximizing $x^TAx$ subject to $\|x\|=1$ where $A=\sum_{i}(p_ip_i^T)$ if I'm not completely wrong. $\endgroup$– Theo SeidelCommented Nov 27, 2019 at 0:27
Add a comment
|