Project

Generalized Graph Signal Sampling by Difference-of-Convex Optimization
（DC最適化による一般化グラフ信号サンプリング）

Keitaro Yamashita, Kazuki Naganuma, and Shunsuke Ono

Key Points of the Research

• Overcoming the Limitation of Bandlimited Assumptions
  We target "beyond bandlimited" graph signals to accurately capture complex, real-world phenomena, moving past traditional and restrictive bandlimited assumptions.

• DC Optimization Framework for Tight Relaxation
  We resolve the dilemma between modeling accuracy and tractability by tightly relaxing the intractable full-rank constraint via the nuclear norm, reformulating it into a Difference-of-Convex (DC) optimization problem.

• Theoretical Guarantees and Superior Performance
  We developed a solver based on the Double-Proximal Gradient DC Algorithm with guaranteed convergence to a critical point, outperforming existing approaches in both synthetic and real-world data experiments.

本研究のポイント

• 非帯域制限グラフ信号への挑戦と一般化
  従来の帯域制限（bandlimited）という制約を超え、複雑な現実世界の現象を正確に捉えるために不可欠な「非帯域制限グラフ信号」のサンプリング・復元を可能にする包括的な枠組みを構築

• DC（非凸）最適化による「モデル精度」と「計算容易性」の両立
  従来手法において最良な復元のために重要であるが取り扱いが困難なフルランク制約に対し、核ノルムを用いた緊密（タイト）な緩和を適用することで、DC最適化問題へと定式化することで、精度を犠牲にしない設計手法を実現

• 理論的収束性の保証
  臨界点への収束が理論的に保証されたDouble-Proximal Gradient DC Algorithmに基づく解法を開発し、人工データおよび実データを用いた実験において既存手法を凌駕するサンプリング・復元精度を実証しました。

Abstract

We propose a comprehensive framework for the generalized sampling and recovery of generalized graph signals by leveraging difference-of-convex (DC) optimization. A fundamental challenge in graph signal processing is sampling, especially for graph signals that are not bandlimited. To accurately capture complex real-world phenomena, it is essential to handle beyond bandlimited graph signals, moving past traditional bandlimited assumptions. Consequently, extending the generalized sampling theory to graph signals has been studied, enabling the best possible recovery for a wide range of signals by assuming signal priors. However, achieving the best possible recovery requires handling inherently non-convex and computationally intractable constraints such as full rank constraint. As a result, existing methods have relied on either aggressive convex relaxations that sacrifice accuracy or greedy algorithms that risk falling into poor suboptimal solutions, facing a fundamental dilemma between modeling accuracy and optimization tractability. To overcome this dilemma, we propose a DC optimization-based method for designing an aggregation sampling operator for beyond bandlimited graph signals that comprehensively handles arbitrary signal priors assumed in the generalized sampling theory. Specifically, the intractable full rank constraint is tightly relaxed using the nuclear norm, reformulating the design problem into a DC optimization problem. We developed a solver based on the general double-proximal gradient DC algorithm, which theoretically guarantees convergence to a critical point. Experimental results on synthetic and real-world data demonstrate the superiority of our method in sampling and recovering beyond bandlimited graph signals compared to existing approaches.

本研究では、非凸（DC: Difference-of-Convex）最適化を活用することで、一般化グラフ信号のサンプリングおよび復元のための包括的な枠組みを提案する。グラフ信号処理における本質的な課題の一つがサンプリングであり、特に帯域制限（bandlimited）のないグラフ信号における研究は発展途上である。複雑な実社会の現象を正確に捉えるためには、従来の帯域制限の仮定を超え、非帯域制限グラフ信号を扱うことが不可欠である。そこで、一般化サンプリング定理をグラフ信号へと拡張する研究が行われている。一般化サンプリング定理では、信号の事前情報（signal prior）を仮定することで、幅広い信号に対して最良な復元を可能にしている。しかし、最良な復元を実現するためには、フルランク制約のような、本質的に非凸かつ計算困難な制約を扱う必要がある。そのため、従来手法は、精度を犠牲にした大幅な凸緩和か、あるいは質の低い局所解に陥るリスクのある貪欲法のいずれかに依存せざるを得ず、モデルの正確性と最適化の扱いやすさの間で本質的なジレンマに直面していた。このジレンマを克服するため、本研究では、一般化サンプリング定理で仮定される任意の信号に関する事前情報を包括的に扱う、非帯域制限グラフ信号のためのサンプリング作用素の設計手法を提案する。具体的には、計算困難なフルランク制約を核ノルムを用いて緊密に緩和し、サンプリング作用素の設計問題をDC最適化問題へと定式化する。そして、理論的に臨界点への収束が保証されているDouble-Proximal Gradient DC Algorithmに基づく解法を開発した。人工データおよび実社会のデータを用いた実験結果により、従来の手法と比較して、非帯域制限グラフ信号のサンプリングおよび復元における提案手法の優位性を実証した。

Reference

K. Yamashita, K. Naganuma, and S. Ono. "Generalized Graph Signal Sampling by Difference-of-Convex Optimization" arXiv:2306.14634, 2026. 

@misc{yamashita2026generalizedgraphsignalsampling,

      title={Generalized Graph Signal Sampling by Difference-of-Convex Optimization}, 

      author={Keitaro Yamashita and Kazuki Naganuma and Shunsuke Ono},

      year={2026},

      eprint={2306.14634},

      archivePrefix={arXiv},

      primaryClass={eess.SP},

      url={https://arxiv.org/abs/2306.14634}, 

}

Links

• Paper (arXiv)

• Demo Code (github)