# Linear algebra of the inertial partition algorithm

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.

• have a look at the definition of the Rayleigh quotient of a Hermitian matrix. do you see how this concept plays into your problem? – GoHokies Dec 19 '17 at 12:24
• I think you would be better served using the typical principle-component-analysis (pca) process: form the covariance matrix of your points, extract from it the maximal eigenpair (x,lambda), and use a (hyper)plane orthogonal to x to partition the points. This business of picking the minimal eigenpair seems peculiar/distracting, and is perhaps an artifact of over-focusing on the 2D case instead of general ND. – rchilton1980 Dec 19 '17 at 16:33
• @rchilton1980 IMHO, in the 2d and 3d case, we can at least visualize the problem and solutions. – nbro Dec 19 '17 at 16:55
• IMHO, even with a jump as small as 2D to 3D, this idea implodes. If you extract the minimal eigenpair for the 3D covariance matrix, you don't get a vector of much use for partitioning purposes. In 3D, your separator is a plane, not a line .. and it should be the plane whose normal is the maximal eigenpair. But we will have only found one vector that lies within that plane, we'd need to find also the second most dominant eigenpair, then cross them, to unambigously establish the normal of the plane. That would be none other than the maximal eigenvector, anyway, so just go for it directly. – rchilton1980 Dec 19 '17 at 17:29

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".