Using an adjacency matrix, Graph Matching becomes a matrix factorization. A relaxation of that problem fails beyond a certain point according to the following paper. Interesting. I will add this to the Advanced Matrix Factorization Jungle page with its attendant sharp phase transition.
Graph Matching: Relax at Your Own Risk by Vince Lyzinski, Donniell Fishkind, Marcelo Fiori, Joshua T. Vogelstein, Carey E. Priebe, Guillermo Sapiro
We present theoretical results addressing the ubiquitous problem of graph matching. Two correlated random Bernoulli graphs have, via their correlation, a natural underlying correspondence between their two vertex sets. We prove, in this very broad random-graph model, and under very general conditions, that a popular convex relaxation of graph matching---solved exactly---will almost always fail to provide the underlying correspondence and that, under mild conditions, a nonconvex relaxation of graph matching---solved exactly---will almost always produce the underlying correspondence. Experimental results illuminate these theoretical findings and provide hints on how to mitigate the risky use of popular convex relaxations in graph matching.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment