Motiverade av tillämpningar av distribuerad linjär uppskattning, distribuerad kontroll och distribuerad optimering, överväger vi frågan om att utforma linjära iterativa algoritmer för att beräkna genomsnittet av nummer i ett nätverk. Särskilt är vårt intresse att utforma en sådan algoritm med den snabbaste graden av konvergens med tanke på nätets topologiska begränsningar. Som huvudresultatet av detta papper, vi designar en algoritm med den snabbaste möjliga graden av konvergens med hjälp av en icke reversibel Markov kedja på den givna nätverksgrafen. Vi konstruerar en sådan Markov kedja genom att omvandla den standard Markov kedja, som erhålls med Metropolis-Hastings metod. Vi kallar den här nya förvandlingen pseudo-lyftning. Vi tillämpar vår metod på grafer med geometri, eller grafer med dubbla dimensioner. Konvergenstiden för vår algoritm (likvärdigt med blandningstiden för vår Markovkedja) är proportionell mot nätverksgrafens diameter och därmed optimal. Som en biprodukt, vårt resultat ger den snabbaste blandning Markov kedjan med tanke på nätverket topologiska begränsningar, och bör naturligtvis hitta sina tillämpningar i samband med distribuerad optimering, uppskattning och kontroll.
Kyomin m.fl. REF har konstruerat en algoritm med den snabbaste möjliga konvergenshastigheten med hjälp av en icke reversibel Markov-kedja på den givna nätverksgrafen.
Distributed Averaging Via Lifted Markov Chains
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}