Eigenmaps and minimal and bandlimited immersions of graphs into Euclidean spaces

Abstract

We introduce concepts of minimal immersions and bandlimited (Paley–Wiener) immersions of combinatorial weighted graphs (finite or infinite) into Euclidean spaces. The notion of bandlimited immersions generalizes the known concept of eigenmaps of graphs. It is shown that our minimal immersions can be used to perform interpolation, smoothing and approximation of immersions of graphs into Euclidean spaces. It is proved that under certain conditions minimal immersions converge to bandlimited immersions. Explicit expressions of minimal immersions in terms of eigenmaps are given. The results can find applications for data dimension reduction, image processing, computer graphics, visualization and learning theory.

Additional details