ترجمه فارسی مقاله ADMM پروگزیمال آنلاین برای یادگیری نمودار از پخش سیگنال های صاف

چکیده

Graph signal processing deals with algorithms and signal representations that leverage graph structures for multivariate data analysis. Often said graph topology is not readily available and may be time-varying, hence (dynamic) graph structure learning from nodal (e.g., sensor) observations becomes a critical first step. In this paper, we develop a novel algorithm for online graph learning using observation streams, assumed to be smooth on the latent graph. Unlike batch algorithms for topology identification from smooth signals, our modus operandi is to process graph signals sequentially and thus keep memory and computational costs in check. To solve the resulting smoothness-regularized, time-varying inverse problem, we develop online and lightweight iterations built upon the proximal variant of the alternating direction method of multipliers (ADMM), well known for its fast convergence in batch settings. The proximal term in the topology updates seamlessly implements a temporal-variation regularization, and we argue the online procedure exhibits sublinear static regret under some simplifying assumptions. Reproducible experiments with synthetic and real graphs demonstrate the effectiveness of our method in adapting to streaming signals and tracking slowly-varying network connectivity. The proposed approach also exhibits better tracking performance (in terms of suboptimality), when compared to state-of-the-art online graph learning baselines.

چکیده به فارسی (ترجمه ماشینی)

پردازش سیگنال نمودار با الگوریتم ها و بازنمودهای سیگنال که از ساختار نمودار برای تجزیه و تحلیل داده های چند متغیره استفاده می کنند ، سروکار دارد.غالباً توپولوژی نمودار به راحتی در دسترس نیست و ممکن است متغیر زمان باشد ، از این رو یادگیری (پویا) ساختار نمودار یادگیری از مشاهدات گره (به عنوان مثال ، سنسور) به یک مرحله اول مهم تبدیل می شود.در این مقاله ، ما یک الگوریتم جدید برای یادگیری نمودار آنلاین با استفاده از جریان های مشاهده ، فرض می کنیم که بر روی نمودار نهفته صاف است.بر خلاف الگوریتم های دسته ای برای شناسایی توپولوژی از سیگنال های صاف ، modus operandi ما پردازش سیگنال های نمودار به صورت متوالی و در نتیجه نگه داشتن حافظه و هزینه های محاسباتی است.برای حل مسئله معکوس و متغیر با زمان ، صافی ناشی از صافی حاصل ، ما تکرارهای آنلاین و سبک را ایجاد می کنیم که بر اساس نوع پروگزیمال روش جهت متناوب چند برابر (ADMM) ساخته شده است ، که به دلیل همگرایی سریع آن در تنظیمات دسته ای شناخته شده است.اصطلاح پروگزیمال در توپولوژی به روزرسانی یکپارچه یک تنظیم مجدد متغیر زمانی را پیاده سازی می کند ، و ما استدلال می کنیم که رویه آنلاین با توجه به برخی فرضیات ساده ، پشیمانی استاتیک زیرنویس را نشان می دهد.آزمایش های قابل تکرار با نمودارهای مصنوعی و واقعی ، اثربخشی روش ما در تطبیق با سیگنال های جریان و ردیابی اتصال به آرامی با شبکه را نشان می دهد.رویکرد پیشنهادی همچنین عملکرد ردیابی بهتری (از نظر پایین بودن) را نشان می دهد ، در حالی که با خطوط اصلی یادگیری نمودار آنلاین مقایسه می شود.