Derivation of Normal Vectors from Point Cloud

In this page, I describe how to derive normal vectors from a point cloud. A simple explanation is provided in the tutorial of the Point Cloud Library(PCL). According to the page, there are two approaches to calculate normal vectors from a point cloud:

1. Determine a surface from a point cloud, and calculate a normal vector of a tangent plane.
2. Calculate a normal vector from a point cloud directly.

The tutorial focuses on the latter case, and introduces one of the most simple methods in the case:

1. Consider a query point in a point cloud.
2. Consider k points in the vicinity of the query point.
3. Determine a plane by means of a least-square plane fitting with the query point and the k neighbors.
4. Extract a normal vector of the plane.

The tutorial tells us that the problem results in an analysis of the eigenvectors and eigenvalues of a covariance matrix created from the nearest neighbors of the query point, and shows only the equation of the eigenvalue problem. I'm interested in the deriving process of the equation. In this page, I give you a detailed description about it.
A point on a plane satisfies the following equation,
,
where is a normal vector of the plane, and is a constant term. The sum of squared residuals that we have to minimize is
,
where indicates an element of a set of neighbors of the query point. An equation of a plane multiplied by a constant represents the same plane as the original equation. To eliminate this indefiniteness, we set the condition that the norm of the normal vector is 1. The condition is introduced into the sum of squared residuals by using the Lagrange multiplier as
.
First, we differentiate it partially with respect to and get
.
The equation is rewritten as
,
where is a centroid of the neighbors. By substituting this formula into the equation , we obtain
.
Differentiating it partially with respect to yields
.
The deformation of the equation reduces to

.
Now we have the equation of the eigenvalue problem of the covariance matrix created from the nearest neighbors of the query point.

This page tells us that the eigenvector corresponding to the smallest eigenvalue approximates the normal vector of the plane. We can confirm the fact as follows.
The sum of squared residuals is
,
where is a set of nearest neighbors, and is a centroid of them.
Using , we can rewrite as, \begin{eqnarray} F(\vec{n})&=&\vec{n}^{T}\;Q\;\vec{n} \nonumber \\ &=&\lambda\;\vec{n}^{T}\cdot\vec{n} \nonumber \\ &=&\lambda \nonumber \end{eqnarray} We used the condition that the norm of the vector is 1.
So we can now understand that in order to minimize , we have to select the smallest eigenvalue.