圖上信號的廣義採樣理論與重建方法研究

《圖上信號的廣義採樣理論與重建方法研究》是依託清華大學，由谷源濤擔任項目負責人的面上項目。

基本介紹

• 中文名：圖上信號的廣義採樣理論與重建方法研究
• 依託單位：清華大學
• 項目負責人：谷源濤
• 項目類別：面上項目

項目摘要

本項目研究圖上信號的廣義採樣和重建問題，具有重要的理論意義和潛在的套用價值。首先，圖上信號是高維、海量、分散式和不規則數據的有效表征方式，其處理技術可為大數據處理提供全新解決思路；其次，採樣和重建是信息科學技術的基本問題，高維空間和流形上的非均勻採樣理論日趨完備，但尚無圖上的廣義採樣理論和重建方法；最後，圖上廣義採樣是傳統抽取式採樣的一般性推廣，是感測網數據採集等套用問題的自然抽象，具有抗噪聲等先天優勢。本項目具體將建立圖上信號的廣義採樣和重建理論，系統深入地研究其關鍵技術，力爭取得一批高水平的研究成果。具體將構造基於局部節點集的採樣模型，研究由局部觀測值唯一重建原信號的充要條件；研究最優觀測方式，評估隨機觀測的性能；設計高性能的重建算法並進行理論分析；針對時變圖結構、時變信號和僅鄰居節點可見的分散式場景，設計跟蹤算法；將上述理論和技術推廣到非理想情形，為潛在套用奠定技術基礎。

結題摘要

本項目本首先將圖上信號的採樣方式從抽取式採樣拓展到局部觀測，提出 一種利用局部觀測值重建原信號的算法——疊代局部觀測重建 (ILMR) 算法， 並證明在一定條件下，帶限圖上信號可以由其局部觀測值精確重建。然後項目從時變圖上信號的集中式重建問題出發，提出了時變圖上信號的結構模型，基於該模型又提出了時變圖上信號的集中式重建方法，並對最優重建、採樣運算元的選擇等進行了相應的理論分析。隨後項目解決了時變圖上信號的線上分散式重建問題。提出了圖上時變信號的線上重建方法，並對非理想信號生成情況線上重建誤差展開了理論分析。接下來項目研究了一般的空時信號重建問題。通過發掘原始信號的低秩性 質和時間差分信號的空間光滑性，提出了一種新的空時信號重建方法，將其描述為一個無約束最佳化問題，並採用交替方向乘子法進行求解。通過對空間光滑性假設、時間光滑性假設以及差分光滑性假設的分析，我們證明了所提方法比 現有方法的適用範圍更廣。最後，項目從時變圖上信號的異常檢測問題出發，提出了圖上信號跳變點檢測模型。基於該模型又提出了時變圖上信號跳變點檢測算法，包括集中式和分散式兩種，並對算的虛警率和檢測延時進行了理論分析，證明了算法性能在階的意義上具有最優性。此外，項目還抽象出圖上信號處理問題的一般最佳化形式，形成一致最佳化問 題。針對圖上信號處理場景中的分散式計算需求，進一步研究了分散式一致最佳化算法。設計了遊走前後向梯度算法，並證明該算法在求解強凸最佳化問題時具有線性收斂性質，及其能耗相比現有算法有階上的下降。