We propose a landmark-constrained algorithm, LA-VDM (Landmark Accelerated Vector Diffusion Maps), to accelerate the Vector Diffusion Maps (VDM) framework built upon the Graph Connection Laplacian (GCL), which captures pairwise connection relationships within complex datasets. LA-VDM introduces a novel two-stage normalization that effectively address nonuniform sampling densities in both the data and the landmark sets. Under a manifold model with the frame bundle structure, we show that we can accurately recover the parallel transport with landmark-constrained diffusion from a point cloud, and hence asymptotically LA-VDM converges to the connection Laplacian. The performance and accuracy of LA-VDM are demonstrated through experiments on simulated datasets and an application to nonlocal image denoising.
Figures & tables
Figure 1. Illustration of a potential issue in estimating parallel transport from x to y via landmark diffusion: different paths yield different parallel-transported vectors at y .
Figure 2. Illustration of parallel transport from s1 to s2 on the distorted sphere. The vector attached at s1 is transported along the surface to s2 using different size of landmark.
Figure 3. From left to right: a comparison of computational time between VDM and (1/2,0) -LA-VDM with different landmark sizes, he difference ratio of the 1st, 3rd, 5th eigenvalues between VDM and (1/2,0) -LA-VDM, the cosine similarity of the 1st, 3rd, 5th eigenvectors between VDM and (1/2,0) -LA-VDM.
Figure 4. Plot of the first, third, and fifth eigenvector fields eigenvectors, for the Klein bottle on the parameter space P . From top to bottom: first, third, and fifth eigen vector fields, and from left to right column: landmark set size 256, 1024, and 4096.
Figure 5. Plot of Il,2 , where l=1,3,5 , for the Klein bottle on the parameter space P ; that is, plot (ϕ−1(si),Il,2(i)) . From top to bottom: first, third, and fifth eigen vector fields, and from left to right column: landmark set size 256, 1024, and 4096.
Figure 6. Plot of Il,a , where l=1,3,5 , for the Klein bottle on the parameter space P ; that is, plot (ϕ−1(si),Il,a(i)) . From top to bottom: first, third, and fifth eigen vector fields, and from left to right column: landmark set size 256, 1024, and 4096.
Figure 7. Plot of Il,m , where l=1,3,5 , for the Klein bottle on the parameter space P ; that is, plot (ϕ−1(si),Il,m(i)) . From top to bottom: first, third, and fifth eigen vector fields, and from left to right column: landmark set size 256, 1024, and 4096.
Eigen
Metric
Landmark size
128
512
2048
1st
I1,2
0.108 ± 0.045
0.036 ± 0.014*
0.026 ± 0.010*
I1,a
0.639 ± 0.378
0.549 ± 0.339*
0.342 ± 0.204*
I1,m
1.262 ± 0.686
1.029 ± 0.676*
0.303 ± 0.179*
3rd
I3,2
0.999 ± 0.001
0.999 ± 0.001*
0.999 ± 0.001*
Table 1. Performance comparison across different eigenvector with different landmark sizes.
Figure 8. From left to right: the difference ratio of the 2nd, 4th, 6th non-trivial eigenvalues between VDM and (β,0) -LA-VDM, the inner product between the 2nd, 4th, 6th non-trivial eigenvectors of VDM and (β,0) -LA-VDM, the difference of the 2nd, 4th, 6th non-trivial eigenvectors of VDM and (β,0) -LA-VDM.
Figure 9. From left to right: the difference ratio of the 2nd, 4th, 6th non-trivial eigenvalues between VDM with α=1 and (1/2,α) -LA-VDM, the inner product between the 2nd, 4th, 6th non-trivial eigenvectors of VDM with α=1 and (1/2,α) -LA-VDM, the difference of the 2nd, 4th, 6th non-trivial eigenvectors of VDM with α=1 and (1/2,α) -LA-VDM.
Figure 10. From left to right: the difference ratio of eigenvalues between VDM and LA-VDM, the inner product between eigenvectors of VDM and LA-VDM, the L2 difference of eigenvectors of VDM and LA-VDM.