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.

  • 1
    $\begingroup$ You can use iteratively reweighted least squares to find $s_2$: en.wikipedia.org/wiki/Iteratively_reweighted_least_squares $\endgroup$ – user35593 Apr 5 '15 at 10:30
  • $\begingroup$ @user35593 It seems that the iterative method doesn't necessarily converge to the optimum value. $\endgroup$ – user49129 Apr 5 '15 at 16:12
  • $\begingroup$ I think it does in your situation. The problem mentioned in the Wikipedia-article is just if you use it for sparse-recovery. Then you need to make sure that there exist a sparse solution. $\endgroup$ – user35593 Apr 9 '15 at 9:41
  • $\begingroup$ @user35593 I meant that it may converge to a local minimum rather than $s_2$ since the problem is not convex. $\endgroup$ – user49129 Apr 15 '15 at 15:24
  • $\begingroup$ I can answer the second question: yes, $\lVert s_1-s_2\rVert$ is bounded. By $2$, since $s_1$ and $s_2$ are unit vectors. $\endgroup$ – Benoît Kloeckner May 5 '15 at 18:54

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.

| cite | improve this answer | |
  • $\begingroup$ @blanc and then? $\endgroup$ – user49129 Apr 5 '15 at 16:15

Your Answer

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