Given a set of points (column vectors) $S = \{p_1, p_2, \cdots, p_n\} \subset \Re^d$, let $A \in \Re^{n \times d}$ be a matrix of which each row is just $p_i^T$. It is easy to find a unit vector $s_1$ such that $$ \sum_{i}(\|p_i\|^2 - \langle p_i, s_1\rangle^2) \tag{1} $$ is minimized. Here, $\langle *, * \rangle$ means inner product and $\|*\|$ is the length of a vector. $\|p_i\|^2 - \langle p_i, s_1\rangle^2$ therefore is the squared perpendicular distance from $p_i$ to the line specified by $s_1$. Facts in linear algebra tell that $s_1$ is just the right singular vector of $A$ that corresponds the largest singular value. Thus the optimization objective above can be answered by doing a SVD decomposition.

My question, however, is that how to find a unit vector $s_2$ that minimizes $$ \sum_i\sqrt{\|p_i\|^2 - \langle p_i, s_2\rangle^2} \tag{2} $$ i.e. minimize sum of squared perpendicular distances to a line.

• Is there any procedure like SVD solving the problem? or a paper on this topic?
• Can we bound the difference between $s_1$ and $s_2$, e.g., is $\|s_1 - s_2\|$ bounded?

It is a common practice to use the squared one instead of the unsquared one as optimization objective. Just to mention a few, least square fitting, the optimization objective in k-Means, etc. This choice makes the objective more math-friendly but I haven't seen any evidence that this choice will make better result, e.g., better clustering in the case of k-Means.

Given a set of points (column vectors) $S = \{p_1, p_2, \cdots, p_n\} \subset \Re^d$, let $A \in \Re^{n \times d}$ be a matrix of which each row is just $p_i^T$. It is easy to find a unit vector $s_1$ such that $$ \sum_{i}(\|p_i\|^2 - \langle p_i, s_1\rangle^2) \tag{1} $$ is minimized. Here, $\langle *, * \rangle$ means inner product and $\|*\|$ is the length of a vector. $\|p_i\|^2 - \langle p_i, s_1\rangle^2$ therefore is the squared perpendicular distance from $p_i$ to the line specified by $s_1$. Facts in linear algebra tell that $s_1$ is just the right singular vector of $A$ that corresponds the largest singular value. Thus the optimization objective above can be answered by doing a SVD decomposition.

My question, however, is that how to find a unit vector $s_2$ that minimizes $$ \sum_i\sqrt{\|p_i\|^2 - \langle p_i, s_2\rangle^2} \tag{2} $$ i.e. minimize sum of squared perpendicular distances to a line.

• Is there any procedure like SVD solving the problem? or a paper on this topic?
• Can we bound the difference between $s_1$ and $s_2$, e.g., is there a non-trivial bound on $\|s_1 - s_2\|$?

It is a common practice to use the squared one instead of the unsquared one as optimization objective. Just to mention a few, least square fitting, the optimization objective in k-Means, etc. This choice makes the objective more math-friendly but I haven't seen any evidence that this choice will make better result, e.g., better clustering in the case of k-Means.