Mixing
Permuting with Sinkhorn normalization: find $sigma$ s.t. $bf{min}frac{dS}{dp}rightarrow bf{sigma} times...
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} = $$
Now if the features are permuted, we receive the following matrix:
$$ bf{X'} = $$
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.
differential-equations derivatives permutations sorting clustering
asked Aug 11 '18 at 5:10
chasechase
1326
add a comment |
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} = $$
Now if the features are permuted, we receive the following matrix:
$$ bf{X'} = $$
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.
differential-equations derivatives permutations sorting clustering
asked Aug 11 '18 at 5:10
chasechase
1326
1
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$.
– chase
Aug 11 '18 at 5:36
add a comment |
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} = $$
Now if the features are permuted, we receive the following matrix:
$$ bf{X'} = $$
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.
differential-equations derivatives permutations sorting clustering
asked Aug 11 '18 at 5:10
chasechase
1326
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} = $$
Now if the features are permuted, we receive the following matrix:
$$ bf{X'} = $$
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.
differential-equations derivatives permutations sorting clustering
differential-equations derivatives permutations sorting clustering
asked Aug 11 '18 at 5:10
chasechase
1326
asked Aug 11 '18 at 5:10
chasechase
1326
edited Aug 14 '18 at 15:54
chase
asked Aug 11 '18 at 5:10
chasechase
1326
asked Aug 11 '18 at 5:10
chasechase
1326
asked Aug 11 '18 at 5:10
chasechase
1326
1326
1
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$.
– chase
Aug 11 '18 at 5:36
add a comment |
1
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$.
– chase
Aug 11 '18 at 5:36
1
1
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$.
– chase
Aug 11 '18 at 5:36
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$.
– chase
Aug 11 '18 at 5:36
add a comment |
1 Answer
1
active
oldest
votes
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
answered Nov 21 '18 at 18:13
chasechase
1326
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2879082%2fpermuting-with-sinkhorn-normalization-find-sigma-s-t-bfmin-fracdsdp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
answered Nov 21 '18 at 18:13
chasechase
1326
add a comment |
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
answered Nov 21 '18 at 18:13
chasechase
1326
add a comment |
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
answered Nov 21 '18 at 18:13
chasechase
1326
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
answered Nov 21 '18 at 18:13
chasechase
1326
answered Nov 21 '18 at 18:13
chasechase
1326
answered Nov 21 '18 at 18:13
chasechase
1326
answered Nov 21 '18 at 18:13
chasechase
1326
1326
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2879082%2fpermuting-with-sinkhorn-normalization-find-sigma-s-t-bfmin-fracdsdp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
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$.
– chase
Aug 11 '18 at 5:36