Många problem med maximal sannolikhet för uppskattning är i allmänhet oåtkomliga optimeringsproblem. Som ett resultat, är det vanligt att approximera den maximala sannolikheten estimator (MLE) med konvex avkopplingar. Halvdefinita avkopplingar är bland de mest populära. Ibland visar det sig att avslappningarna är tajta. I den här artikeln studerar vi ett sådant fenomen. Problemet med vinkelsynkronisering består i att uppskatta en samling n-faser, givet bullriga mätningar av några av de parvisa relativa faserna. MLE för vinkelsynkronisering problem är lösningen på en (hård) nonbipartite Grothendieck problem över komplexa tal. Det är känt att dess halvdefinita avkoppling åtnjuter värsta-fall approximation garantier. I det här dokumentet överväger vi en stokastisk modell på inmatningen av den halvdefinita avkopplingen. Vi antar att det finns en planterad signal (motsvarande en uppsättning av marksanningar) och mätningarna korrumperas med slumpmässiga ljud. Även om MLE inte sammanfaller med den planterade signalen, visar vi att avkopplingen är, med hög sannolikhet, tight. Detta håller även för höga ljudnivåer. Denna analys förklarar, för det intressanta fallet med vinkelsynkronisering, ett fenomen som har observerats utan förklaring i många andra inställningar. Nämligen, det faktum att även när exakt återvinning av marken sanningen är omöjligt, halvdefinita avkopplingar för MLE tenderar att vara tight (i gynnsamma bullersystem).
Denna fråga besvaras delvis i REF för det närbesläktade fassynkroniseringsproblemet, under en stokastisk modell för data.
Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
{'venue': 'Mathematical Programming, Series A, 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}