PCA, kernel PCA, MDS, and manifold embeddings — Examples

Each column of $X$ sums to zero, so $X_c=X$; multiplication gives $X^{T}X=\left(\begin{array}{cc}2& 0\\ 0& 0\end{array}\right)$, with singular values $\sqrt{2}$ and $0$.

The vector $Q=(1,0{)}^T$ satisfies $Q^{T}Q=1$, and $X_{c}Q{Q}^T=X$. Therefore its reconstruction error is zero.

Every squared Frobenius error is nonnegative, so this zero error is the global minimum. Since $2>0$ separates the two eigenvalues of $X^{T}X$, [F2] also gives the unique minimizing one-dimensional subspace $\mathrm{span}\{(1,0{)}^T\}$.

Put $u=(1,1,-2{)}^T$ and $v=(1,-1,0{)}^T$. Both are zero-sum, so $H_{3}u=u$ and $H_{3}v=v$. Here $D^{\circ 2}=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 9\\ 1& 9& 0\end{array}\right)$, so direct multiplication gives $u^{T}Bu=-\frac{1}{2}{u}^T{D}^{\circ 2}u=19$, $v^{T}Bv=1$, and $u^{T}Bv=-\frac{1}{2}{u}^T{D}^{\circ 2}v=-8$. Thus $w=u+8v$ satisfies $w^{T}Bw=19+16(-8)+64=-45<0$.

By [F2], $B$ is symmetric and has an orthonormal eigenbasis. If every eigenvalue were nonnegative, expressing $w$ in that eigenbasis would give $w^{T}Bw\ge 0$, contradicting step 1.1. Therefore $B$ has a negative eigenvalue.

The stated triangle inequality fails, since $D_{13}+D_{12}=2<D_{23}=3$, so no Euclidean point configuration realizes $D$. This matches the negative eigenvalue and the Euclidean-only exactness hypothesis of [F2].

The nearest neighbor of $x_1$ and $x_2$ is each other at distance $1\mathrm{/}10$; the nearest neighbor of $x_3$ and $x_4$ is each other at distance $1\mathrm{/}10$. Every distance between the two pairs is at least $99\mathrm{/}10$, so no cross-pair edge is selected. By [F1], the union graph has exactly the two edges $\{1,2\}$ and $\{3,4\}$.

The graph in step 1.1 has two connected components, so [F2] returns the disconnected status; a path between either cross-component pair does not exist, and the algorithm does not produce a finite all-pairs graph-distance matrix.

The distances from $x_1=0$ to $x_4=0$, $x_2=1$, and $x_3=-1$ are $0,1,1$, so the deterministic list is $N_1=(4,2,3)$. The corresponding row matrix is $Z_1=(0,-1,1)$ and $C_1=Z_1^T{Z}_1=\left(\begin{array}{ccc}0& 0& 0\\ 0& 1& -1\\ 0& -1& 1\end{array}\right)$, which is nonzero of rank one and hence singular.

Write the weights in the order $(w_4,w_2,w_3)$. The constraint is $w_4+w_2+w_3=1$, and the reconstructed point is $w_2-w_3$. The minimum residual is zero exactly when $w_2=w_3=t$, giving $w_4=1-2t$.

Along this affine family, the squared norm is $(1-2t{)}^2+2t^2=6(t-1\mathrm{/}3{)}^2+1\mathrm{/}3$, uniquely minimized at $t=1\mathrm{/}3$. Thus the minimum-norm weights are $(1\mathrm{/}3,1\mathrm{/}3,1\mathrm{/}3)$ in the ordered list, and [F2] guarantees the selection is well-defined despite singularity.

For $x_1=x_3=-1$, the two nearest indices to each are the duplicate at $-1$ and $x_5=0$, giving $N_1=(3,5)$ and $N_3=(1,5)$. For $x_2=x_4=1$, the lists are $N_2=(4,5)$ and $N_4=(2,5)$. From $x_5=0$ all four distances are $1$, so $N_5=(1,2)$ by the index tie rule.

For rows 1 and 3, the exact reconstruction weights are 1 on the duplicate point and 0 on $x_5$; for rows 2 and 4, they are 1 on the duplicate point and 0 on $x_5$. For row 5, weights $(1\mathrm{/}2,1\mathrm{/}2)$ on points $x_1=-1,x_2=1$ reconstruct zero exactly. Each is the unique minimum-norm choice by [F2] and [F3], yielding the displayed $W$.

The union edges are $\{1,3\}$, $\{1,5\}$, $\{3,5\}$, $\{2,4\}$, $\{2,5\}$, and $\{4,5\}$, so every vertex lies in one connected graph.

The equation $Wy=y$ gives $y_1=y_3$, $y_3=y_1$, $y_2=y_4$, $y_4=y_2$, and $y_5=(y_1+y_2)\mathrm{/}2$. The parameters $y_1,y_2$ are free, so $\dim \ker (I_5-W)=2$, whereas the constant vectors form a one-dimensional subspace. The condition in [F4] fails despite connectivity, and LLE does not specify an embedding for this input.

After centering the four points, their Gram matrix is $B=\left(\begin{array}{cccc}1\mathrm{/}2& 0& -1\mathrm{/}2& 0\\ 0& 1\mathrm{/}2& 0& -1\mathrm{/}2\\ -1\mathrm{/}2& 0& 1\mathrm{/}2& 0\\ 0& -1\mathrm{/}2& 0& 1\mathrm{/}2\end{array}\right)$. The unit vector $u_x=(-1,1,1,-1{)}^T\mathrm{/}2$ is an eigenvector with eigenvalue $1$, as is $u_y=(-1,-1,1,1{)}^T\mathrm{/}2$; the other two eigenvalues are zero. Thus the x-coordinate choice $Y_M=u_x$ is a valid q=1 classical-MDS output, and it has repeated pairs $y_1=y_4$ and $y_2=y_3$.

With one neighbor per row, each LLE weight is $1$. Thus $W_{12}=W_{21}=W_{32}=W_{41}=1$ and other entries are zero; the equations $Wy=y$ force $y_1=y_2=y_3=y_4$, so the kernel is exactly the constant vectors. The matrix is $M=(I-W{)}^T(I-W)=\left(\begin{array}{cccc}3& -2& 0& -1\\ -2& 3& -1& 0\\ 0& -1& 1& 0\\ -1& 0& 0& 1\end{array}\right)$. Its symmetric subspace vectors $(c,c,d,d)$ have eigenvalues $0,2$. On antisymmetric vectors $(c,-c,-d,d)$ it acts by $(c,d)\mapsto (5c-d,d-c)$, whose characteristic equation is ${\lambda }^2-6\lambda +4=0$, giving eigenvalues $3-\sqrt{5}$ and $3+\sqrt{5}$. Hence the lowest positive eigenvalue is $3-\sqrt{5}$ with eigenvector $(a,-a,-1,1{)}^T$, where $a=\sqrt{5}-2\in (0,1)$.

The distances from each square vertex to its two side-neighbors tie at $1$. By [F3], the neighbor lists are $N_1=(2)$, $N_2=(1)$, $N_3=(2)$, and $N_4=(1)$; the union graph has the stated edges and is the path $4-1-2-3$. Its graph distances are exactly the line distances of the centered vector $Y_I=(-1\mathrm{/}2,1\mathrm{/}2,3\mathrm{/}2,-3\mathrm{/}2{)}^T$. Since this graph-distance matrix is Euclidean in one dimension, [F2] shows that ISOMAP’s q=1 classical-MDS output is congruent to $Y_I$. In particular its distance between vertices 1 and 4 is $1$, unlike the zero MDS distance in step 1.1.

The LLE coordinate has four distinct values, unlike $Y_M$, so it is not congruent to the classical-MDS output. Its sorted consecutive gaps are proportional to $1-a,2a,1-a$, and these are not all equal: $2a=1-a$ would imply $3\sqrt{5}=7$, contradicting $45\mathrm{\ne }49$ after squaring. The ISOMAP line has equal consecutive gaps, so LLE is not congruent to ISOMAP either. The distinct distance $d_{14}=1$ in ISOMAP and $d_{14}=0$ in classical MDS already separates those two outputs.

For $Y(t)=(t,-t)$, the sole distance is $\mathrm{\mid }t-(-t)\mathrm{\mid }=2\mathrm{\mid }t\mathrm{\mid }$, so [F1] gives $f(t)=(1-2\mathrm{\mid }t\mathrm{\mid }{)}^2$.

A convex function must satisfy the midpoint inequality $f(0)\le \frac{1}{2}f(-a)+\frac{1}{2}f(a)$. At $a=1\mathrm{/}4$, $f(0)=1$ and $f(-a)=f(a)=(1-1\mathrm{/}2{)}^2=1\mathrm{/}4$, so the midpoint inequality fails. Hence this valid stress objective is nonconvex.