Example Problem:

Suppose we are given a set of pixel values for bunch of images, MRI scans, or movies. These obviously tend to be 2D, 3D, or 4D manifolds (movies have time, MRI scans can have z-axis or time). However, since we're given the set of pixels, we do not know what ordering the pixels are supposed to have (although we assume that we do have a mapping of pixel identities for each set that is the same for each image). We also may not know if the data comes from an image, movie, etc.

What I have seen before is that using the Traveling Salesman Problem (TSP) to solve this works given one assumption - that the rows and columns are shuffled together. Example: we can perform the following (from this github project):

--> TSP rows and columns -->

As long as we know which row and column set each pixel belongs to this works. However, when removing this knowledge the process does not work so well. (For example, instead of having the image as a matrix, just getting a vector of pixels, and shuffling that vector - recovering the image is not as achievable).

But given a large enough sample of images, with the same mapping of pixel identities, this should be more achievable with some algorithm (TSP to solve a surface instead of a path).

More Formal Problem Statement:

Given the matrix $X\in\mathbb{R}^{n\times m}$ where $n$ is the number of samples (images, movies, etc), and $m$ is the number of features (pixels).

Determine the dimension $d$ of the objects ($d<m$) and the position/connectivity of each feature $m$, such that $\sum{\nabla X_{ordered}}$ is minimized.


This also seems close to manifold learning, but often the solutions there only provide approximations, and do not "go through each city".

  • $\begingroup$ This question makes no sense. $\endgroup$ Sep 28, 2021 at 22:06


You must log in to answer this question.