Att studera landskapet av nonconvex kostnadsfunktion är nyckeln till en bättre förståelse av optimeringsalgoritmer som ofta används i signalbehandling, statistik och maskininlärning. Samtidigt har den berömda Kuramoto-modellen varit en viktig matematisk modell för att studera synkroniseringsfenomenen hos kopplade oscillatorer över olika nätverkstopologier. I den här artikeln sammanför vi dessa två till synes orelaterade objekt genom att undersöka optimeringslandskapet för en icke-linjär funktion E( på engelska) = 1 2 1≤i,j≤n a ij (1 − cos( på engelska)) i samband med ett underliggande nätverk och utforska förhållandet mellan förekomsten av lokala minima och nätverkstopologi. Denna funktion uppstår naturligt i Burer-Monteiro metod tillämpas på Z 2 synkronisering samt matris komplettering på torus. Dessutom motsvarar det energifunktionen hos den homogena Kuramoto-modellen på komplexa nät för kopplade oscillatorer. Vi bevisar att minimeraren av energifunktionen är unik upp till en global översättning under deterministiska täta grafer och Erdős-Rényi slumpmässiga grafer med verktyg från optimering och slumpmässig matristeori. Följaktligen är den stabila jämvikten hos motsvarande homogena Kuramoto-modell unik och attraktionsbassängen för synkrontillståndet för dessa kopplade oscillatorer är hela fasutrymmet minus en uppsättning mått noll. Dessutom, våra resultat behandlar när Burer-Monteiro metoden återhämtar marken sanningen exakt från mycket ofullständiga observationer i Z 2 synkronisering och kasta ljus på robustheten av nonconvex optimering algoritmer mot vissa typer av så kallade monotona motståndare. Numeriska simuleringar utförs för att illustrera våra resultat. där A = (a ij ) 1≤i,j≤n med en ij ≥ 0 är viktmatrisen för en oriktad graf. Som specialfall kan A vara en adjakensmatris. Vi vill ta upp följande nyckelfråga: Nyckelfråga: Vad är förhållandet mellan förekomsten av lokala minima och nätverkets topologi? Antag att det finns n gruppelement {g i } n i=1 av en grupp G. Istället för att observera dessa element direkt, är endast en delmängd av deras bullriga offset g i g −1 j tillgänglig. Målet är att återställa alla gruppers element upp till en global fas från {g i g −1 j } {(i, j) till E} där E betecknar indexuppsättningen tillgängliga observationer. Detta kallas gruppsynkroniseringsproblemet, se [1, 2, 6, 7, 8, 13, 33, 49] för mer detaljer. Det enklaste exemplet på gruppsynkronisering är Z 2-synkronisering [1] där g i antas tillhöra {±1} och därmed minskar förskjutningarna till g i g −1 j = g i g j. Mer exakt, vi har Y som observerade data, som är en ingångsvis produkt av en binär symmetrisk matris A  på 0 {0, 1} n×n och den perturbed marken sanning gg  på + W, d.v.s., där W är bullermatrisen och " • " betecknar entrywise multiplikation. Utan gruppbegränsningar på {g i } n i=1, är det exakt ett matriskompletteringsproblem [11, 20, 34, 43] som ursprungligen kommer från Netflix Prize-problemet. En möjlig formulering är att maximera följande kombinatoriska quadratic form max z-±1} n z -Y z och sedan använda maximatorn som en uppskattning av g från dess partiella bullriga mätningar. I själva verket är programmet ovan motsvarar minst kvadrat förlust funktion efter en enkel omvandling. Men, lösa detta program är NP-hård i allmänhet. Man kan betrakta semidefinit programmering (SDP) avkoppling som ett alternativ genom att försöka återställa rank-1 matris gg  och istället för enskilda gruppelement: Observera marken sanningen gg  och uppfyller de två begränsningarna ovan. Under milda förhållanden, är denna SDP avslappning visat sig återhämta gg  på exakt [1]. Trots effektiviteten i SDP avkoppling [35], tenderar det att lida av en hög computational komplexitet. Därför har många ansträngningar gjorts för att hitta effektiva och robusta gradient-descent-baserade metoder som alternativ för att lösa SDP som uppstår genom avslappning av matris återhämtning problem med låg rank. Den metod som föreslås av Burer och Monteiro i [9, 10] kan utan tvekan vara en av de mest framgångsrika metoderna för att ta itu med dessa annars svåra problem genom att bekvämt hålla Z i en faktoriserad form och dra full nytta av den låga rank egendom. Genom att låta Z = QQ  ska där Q  på R n×q med q < n, har vi max Tr(Y QQ) s.t. (QQ) ii = 1, 1 ≤ i ≤ n. Med andra ord måste varje rad av Q normaliseras. Dessa begränsningar ger ett sökutrymme som består av ett Riemannian grenrör, och Riemannian lutning nedstigning används för att lösa detta program [3, 7].
REF studerar problemet från landskapet av en föreslagen objektiv funktion och visar att den globala minimeraren är unik även när den tillhörande grafen är ofullständig och följer av Erdös-Rényi slumpmässiga grafer.
On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics', 'Computer Science']}