1
$\begingroup$

I have a matrix of samples vs. features and would like to organize or permute the features such that the sum of the first derivative along these features is minimized for all of the samples within the matrix.

The goal of this would be to have an algorithm to re-create a continuous x-axis ordering for several samples if the x-axis is permuted, given sufficient samples, in order to increase the system's ability to minimize the derivative across all samples.


I suppose this could be stated more formally as:

Given an $n \times p$ matrix of $n$ samples and $p$ features,

$$ \bf{X} = \mathbb{R}^{n \times p} $$

where each sample has previously been described as a continuously differentiable function:

$$S = f(p)$$

but then is permuted along the $p$ axis to give $\bf{X}'$, where the samples now have discontinuous features along $p$.

Find the correct permutation matrix, $\bf{\sigma}^{p \times p}$, such that

$$\min \huge( \normalsize{\sum_{n}\sum_{p}(\frac{dS}{dp})}\huge) \normalsize \rightarrow \bf{\sigma} $$

$$ \sigma \times \bf{X'}= \bf{X}$$


For my problem, I have the assumption that, at some point, the samples were created from a summation of Gaussian or other normal distributions.

Here is an example of $\bf{X}$, wherein the samples were a linear combination of Gaussian distributions:

$$ \bf{X} = $$

samples by features

Now if the features are permuted, we receive the following matrix:

$$ \bf{X'} = $$ permuted samples by features

So, my main question is: Given this X', how can you find the correct ordering of p to receive the original matrix X?


Attempts:

I have tried using argsort or distance matrices as inputs into Sinkhorn normalization for the prediction for $p$ to be in a certain row. After Sinkhorn Normalization [1]: I thought it would return something resembling the permutation matrix I am seeking $\sigma$. However, the results have not been very fruitful.

$\endgroup$
1
  • 1
    $\begingroup$ I noticed that sink horn normalization or Gumbel-Sinkhorn normalization is being used for tasks similar to this recently (Google's recent paper, as well as a few others) however, I attempted to utilize this approach and quickly found that it is more dependent upon first predicting a placement of each $p$. I attempted to do this with distance matrices, but there is a large issue, as using this with the sinkhorn operator essentially just swaps the placement of each correlated $p$. $\endgroup$
    – chase
    Aug 11, 2018 at 5:36

1 Answer 1

1
$\begingroup$

While this is not dependent on Gumbel-Sinkhorn, I did find the answer in a very common spot. Apparently, this is a traveling salesman problem. By utilizing each feature as a point in $n$-dimensional space, and then solving the traveling salesman problem, the "list of cities" returned is simply the indices which will sort the matrix back to its original unpermuted form.

TLDR: It's the traveling salesman problem

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .