Mixing
On concave distance metrics.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
We know that the most Euclidean distance metric is convex due $f''(x) = 2 > 0$ where $f(x) = |x|^2$. Also because norms are convex.
However, $|x|^a$ where a is $0 le a le 1$ is strictly concave. Several works in the literature [1], [2], [3] show that Euclidean distance is probably not a good distance metric in high dimensionality due to several reasons.
So, is it possible that there exists a concave function that can effectively capture the distance between two vectors when they are in the same embedding space much more efficiently than its convex counterpart?
Also, is it possible that combination of both convex and concave functions can be a better approach to accurately computing distance than if used individually?
Fractional distance metrics do not satisfy the triangle inequality, does this affect their optimization?
[1] https://bib.dbvis.de/uploadedFiles/155.pdf
[2] https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf
[3] https://members.loria.fr/MOBerger/Enseignement/Master2/Exposes/beyer.pdf
convex-analysis convex-optimization
edited Jul 23 at 23:36
Michael Hardy
204k23186462
asked Jul 23 at 21:59
Kamran Janjua
43
add a comment |Â
up vote
0
down vote
favorite
We know that the most Euclidean distance metric is convex due $f''(x) = 2 > 0$ where $f(x) = |x|^2$. Also because norms are convex.
However, $|x|^a$ where a is $0 le a le 1$ is strictly concave. Several works in the literature [1], [2], [3] show that Euclidean distance is probably not a good distance metric in high dimensionality due to several reasons.
So, is it possible that there exists a concave function that can effectively capture the distance between two vectors when they are in the same embedding space much more efficiently than its convex counterpart?
Also, is it possible that combination of both convex and concave functions can be a better approach to accurately computing distance than if used individually?
Fractional distance metrics do not satisfy the triangle inequality, does this affect their optimization?
[1] https://bib.dbvis.de/uploadedFiles/155.pdf
[2] https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf
[3] https://members.loria.fr/MOBerger/Enseignement/Master2/Exposes/beyer.pdf
convex-analysis convex-optimization
edited Jul 23 at 23:36
Michael Hardy
204k23186462
asked Jul 23 at 21:59
Kamran Janjua
43
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
We know that the most Euclidean distance metric is convex due $f''(x) = 2 > 0$ where $f(x) = |x|^2$. Also because norms are convex.
However, $|x|^a$ where a is $0 le a le 1$ is strictly concave. Several works in the literature [1], [2], [3] show that Euclidean distance is probably not a good distance metric in high dimensionality due to several reasons.
So, is it possible that there exists a concave function that can effectively capture the distance between two vectors when they are in the same embedding space much more efficiently than its convex counterpart?
Also, is it possible that combination of both convex and concave functions can be a better approach to accurately computing distance than if used individually?
Fractional distance metrics do not satisfy the triangle inequality, does this affect their optimization?
[1] https://bib.dbvis.de/uploadedFiles/155.pdf
[2] https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf
[3] https://members.loria.fr/MOBerger/Enseignement/Master2/Exposes/beyer.pdf
convex-analysis convex-optimization
edited Jul 23 at 23:36
Michael Hardy
204k23186462
asked Jul 23 at 21:59
Kamran Janjua
43
We know that the most Euclidean distance metric is convex due $f''(x) = 2 > 0$ where $f(x) = |x|^2$. Also because norms are convex.
However, $|x|^a$ where a is $0 le a le 1$ is strictly concave. Several works in the literature [1], [2], [3] show that Euclidean distance is probably not a good distance metric in high dimensionality due to several reasons.
So, is it possible that there exists a concave function that can effectively capture the distance between two vectors when they are in the same embedding space much more efficiently than its convex counterpart?
Also, is it possible that combination of both convex and concave functions can be a better approach to accurately computing distance than if used individually?
Fractional distance metrics do not satisfy the triangle inequality, does this affect their optimization?
[1] https://bib.dbvis.de/uploadedFiles/155.pdf
[2] https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf
[3] https://members.loria.fr/MOBerger/Enseignement/Master2/Exposes/beyer.pdf
convex-analysis convex-optimization
edited Jul 23 at 23:36
Michael Hardy
204k23186462
asked Jul 23 at 21:59
Kamran Janjua
43
edited Jul 23 at 23:36
Michael Hardy
204k23186462
edited Jul 23 at 23:36
Michael Hardy
204k23186462
edited Jul 23 at 23:36
Michael Hardy
204k23186462
204k23186462
asked Jul 23 at 21:59
Kamran Janjua
43
asked Jul 23 at 21:59
Kamran Janjua
43
asked Jul 23 at 21:59
Kamran Janjua
43
43
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860818%2fon-concave-distance-metrics%23new-answer', 'question_page');
);
Post as a guest
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
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
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