Find a line such that sum of perpendicular distances of points to the line is minimized

Question

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.

Answer 1

For the $s_1$ problem, the Lagrange condition is: there is $\lambda\in \mathbb{R}$ s.t. $-\sum_i<p_i,s_1>p_i+\lambda s_1=0$, that is linear with respect to $s_1$; since $p_i=A^T e_i$, where $(e_i)_i$ is the canonical basis of $\mathbb{R}^n$, our condition can be rewritten: $(-A^TA+\lambda I_d)s_1=0$.

For the $s_2$ problem, it is more complicated. The Lagrange condition is: there is $\lambda\in \mathbb{R}$ s.t. $-\sum_i\dfrac{<p_i,s_2>p_i}{\sqrt{||p_i||^2-<p_i,s_2>^2}}+\lambda s_2=0$, that is not linear with respect to $s_2$.

Answer to Echo. You have no closed form for $\min(f(s))$. You are in front of a system of $d+1$ algebraic equations in the $d+1$ real unknowns $\lambda,s$. There are (many ?) solutions $(\lambda_j,s_j)_j$. Since the derivative of $f$ is not defined when $s\in(\pm p_i)_i$, your required minimum is $\min\{(f(s_j))_j,(f(\pm p_i))_i\}$. Of course, if $n$ is a great number, then, using an iterative method, you look for an approximation of a solution $\lambda,s$; I think that the best is to choose "the solution for the $s_1$ problem" as the initial value of your iteration. If the iteration converges, then you have a good candidate.