The algorithm is based on the
definition of principal curves with a given length.
However, for practical reasons the length penalty suggested by the theoretical model is replaced
by a discrete curvature penalty. The diagram on the right indicates the basic
steps of the algorithm.
The algorithm starts with a straight line segment (a part of the first PCA line), and in each iteration it increases the number of line segments by adding a vertex to the polygonal line produced by the previous iteration. After adding the vertex, the position of each vertex are updated in an inner loop. The algorithm stops when the number of vertices exceeds a threshold.
The inner loop consists of a projection step and an optimization step. In the projection step the data points are partitioned into "nearest neighbor regions" according to which segment or vertex they project. In the optimization step the new position of each vertex is determined in a line search to minimize an objective function that consists an average squared distance term and a curvature penalty. These two steps are iterated until convergence is achieved.
The algorithm is implemented in Java.