Linear algebra of the inertial partition algorithm

Question

You can find the description of the inertial partition algorithm either in [1] or [2].

I think, I understood the main idea behind this algorithm:

We have the spatial coordinates of points that we want to bisect. We find a line (or, hyperplane, in general) $L$ through these points, such that it is a total least squares fit of the nodes. We project the points onto this line. We find the "median projection", which then is used to split the points into two partitions: that is, the perpendicular hyperplane to $L$ that goes through the "median projection" divides the points into two partitions.

Nonetheless, I have a doubt regarding the theory behind the inertial partitioning algorithm.

Now, it turns out that the idea above can be framed as an eigenvalue-eigenvector problem (as for spectral partitioning algorithm). More specifically, it turns out, after a derivation (see [2]), we want to minimise the quantity $$\vec{u}^T M \vec{u} = \lambda,$$ i.e. find $\vec{u}$ such that $\lambda$ is minimised.

According to [2], $u=[a, b]$ is the unit eigenvector of $M$ corresponding to the smallest eigenvalue.

The fact that $\vec{u}$ is a unit eigenvector, I suppose, is related to the fact that the author of [2] assumes (w.l.o.g.) that $a^2 + b^2 = 1$. Why does the author assume $a^2 + b^2 = 1$? Why would that be convenient? Why is the assumption w.l.o.g.? Note $-\frac{a}{b}$ is the slow of the line $L$.

Given the assumption $a^2 + b^2 = 1$, I understand that $\vec{u} = [a, b]$ is a unit eigenvector, because $\|\vec{u}\| = \sqrt{a^2 + b^2} = 1 \iff a^2 + b^2 = 1$.

Why is $\vec{u}$ the eigenvector corresponding to the smallest eigenvalue of $M$? Why do we care about the smallest eigenvalue of $M$?

Once we have found $\vec{u}$, we have the slow of the line. We can also retrieve the center of mass, that is $(\bar{x},\bar{y})$, which is used to formulate the equation of the line of $L$: it is basically an average of the points.

Answer 1

We have the assumption $a^2 + b^2 =\vec{u}\vec{u}^T= 1$. By construction/definition (see [2]), $M$ is a symmetric matrix. Hence, we know that the Rayleigh quotient of $M$ and $\vec{u}$ is defined as

$$ R(M,\vec{u})={\vec{u}^{T}M\vec{u} \over \vec{u}^{T}\vec{u}} = \vec{u}^{T}M\vec{u} $$

It turns out that $$\min_{\vec{x}} R(M, \vec{x}) = \lambda_1$$

where $\lambda_1$ is the smallest eigenvalue of $M$. See section $3$ of paper http://people.math.gatech.edu/~ecroot/notes_linear.pdf for a proof of this fact.

Our original goal was to minimize $ R(M,\vec{u}) = \vec{u}^{T}M\vec{u}$. We now know that that quantity is the smallest eigenvalue of $M$, i.e. $\lambda_1$.

But what is the vector $\vec{x}$ which corresponds to $\lambda_1$?

\begin{align} & \vec{x}^{T}M\vec{x} = \lambda_1\\ \iff & \vec{x} \vec{x}^{T}M\vec{x} = \vec{x} \lambda_1 \\ \iff & \vec{x} \vec{x}^{T}M\vec{x} = \lambda_1 \vec{x} \\ \iff & M\vec{x} = \lambda_1 \vec{x} \\ \end{align}

Given that $\lambda_1$ is the smallest eigenvalue of $M$, it must follow that $\vec{x}$ is the corresponding eigenvector.

Finally, I suppose, according to section $2$ of http://people.math.gatech.edu/~ecroot/notes_linear.pdf, the assumption $a^2 + b^2 =\vec{u}\vec{u}^T= 1$ seems to come from the fact that minimizing the Rayleigh quotient $R(M,\vec{u}) = \frac{\vec{u}^{T}M\vec{u}}{\vec{u}^{T}\vec{u}}$ is equivalent to minimizing $R(M,\vec{u}) = \vec{u}^{T}M\vec{u}$, that is we can let $\|\vec{u}\| = 1$. In the same article, the author calls this property "scaling".