2
$\begingroup$

After doing extensive literature research in all sorts of science I am completely puzzled. I am trying to find out what the state-of-the-art techniques would be to recover a (let's say euclidean) distance or dissimilarity matrix given only sparse pairwise co-occurrence measures (strictly positive correlations with a threshold >= 0, nothing like anti-correlation) within overlapping neighborhoods or cliques of observations. The input values might be partially corrupted with noise but this is a secondary problem for now. In the extreme case the input matrix could be just binary in the sense of "i,j are neighbors" or "i,j are not known to be neighbors". This case would lead to the scenario discussed in "1-Bit matrix completion" (Davenport et al. 2014)

In case of a geometric correlation matrix I could just transform the correlations to distances (according to https://stats.stackexchange.com/q/36158) and the problem becomes a simpler euclidean matrix completion task.

In my head concepts of dimensionality reduction, embedding, (nonnegative) matrix factorization, global positioning, wireless sensor networks, graph theory, algebraic topology, manifold learning, recommendation systems, (euclidean) distance matrix completion, clustering etc. are mixing up and I feel a bit lost. I hope this is even the right channel to ask that question. There seem to be so much happening on this topic in the last years and decades across fields that for me as a beginner I find it hard to get an overview and find out which concept or mix of concept is most suited for this particular usecase.

I am not looking for detailed explanations but rather intuitions and concepts of promising strategies that are used in such cases.

What I found particularly useful so far was reading Amit Singer's paper "A remark on Global Positioning from Local Distances" as well as literature on Isomap and LLE. The problem is that this work is from 2007 and older and I expect that there are tons of newer techniques. On the other hand it feels like many old ideas are just rephrased, some properties proven or worked out for particular use-cases in the modern literature. One quite recent overview is provided by "An overview of low-rank matrix recovery from incomplete observations" (Davenport & Romberg, 2016) but this one is not particularly discussing the special case of recovering euclidean distance matrices - which should be easier to solve due to geometrical constraints.

What would be your method of choice? Do you have suggestions for reading? I would like to get a better overview over the fundamentally different approaches existing out there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.