Project

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

Keitaro Yamashita, Kazuki Naganuma, and Shunsuke Ono

Key Points of the Research

• Introduces a difference-of-convex (DC) optimization to design sampling operators for beyond bandlimited graph signals based on the generalized sampling theory.

• Achieves a method for designing a flexible sampling operator without strict assumptions and aggressive relaxations of existing methods.

• Develops an efficient solver based on the general double-proximal gradient DC algorithm and shows superior performance over existing methods.

本研究のポイント

• 一般化サンプリング定理に基づき、帯域制限を超えたグラフ信号に対する最良な復元を達成するサンプリング演算子を設計するためにDifference-of-Convex（DC）最適化技術を導入

• 既存手法において用いられていた厳格な仮定や過度な緩和が不要となるフレキシブルサンプリング演算子の設計手法を実現

• General Double-Proximal Gradient DCアルゴリズムを用いた効率的な解法を開発し、既存手法より優れた性能を実証

Abstract

We propose a desigining method of a flexible sampling operator for graph signals via a difference-of-convex (DC) optimization algorithm. A fundamental challenge in graph signal processing is sampling, especially for graph signals that are not bandlimited. In order to sample beyond bandlimited graph signals, there are studies to expand the generalized sampling theory for the graph setting. Vertex-wise sampling and flexible sampling are two main strategies to sample graph signals. Recovery accuracy of existing vertex-wise sampling methods is highly dependent on specific vertices selected to generate a sampled graph signal that may compromise the accurary especially when noise is generated at the vertices. In contrast, a flexible sampling mixes values at multiple vertices to generate a sampled signal for robust sampling; however, existing flexible sampling methods impose strict assumptions and aggressive relaxations. To address these limitations, we aim to design a flexible sampling operator without such strict assumptions and aggressive relaxations by introducing DC optimization. By formulating the problem of designing a flexible sampling operator as a DC optimization problem, our method ensures robust sampling for graph signals under arbitrary priors based on generalized sampling theory. We develop an efficient solver based on the general double-proximal gradient DC algorithm, which guarantees convergence to a critical point. Experimental results demonstrate the superiority of our method in sampling and recovering beyond bandlimited graph signals compared to existing approaches.

本研究では、任意のグラフ信号に対応するフレキシブルサンプリング演算子の設計手法を、Difference-of-Convex（DC）最適化技術を用いて提案する。グラフ信号処理における基盤的な課題の一つにサンプリング、特に帯域制限の仮定を逸脱したグラフ信号に対するサンプリングである。帯域制限を超えたグラフ信号をサンプリングするために、一般化サンプリング定理をグラフ信号に拡張する研究が行われている。ここで、グラフ信号サンプリングには、各点サンプリングとフレキシブルサンプリングがある。既存の各点サンプリング法は、サンプル信号を生成するために選択される一部の頂点に復元精度が大きく依存するため、特にそれらの頂点でノイズが発生した場合に復元精度が低下する可能性がある。これに対し、フレキシブルサンプリングは、安定した復元を行うために複数の頂点の値を混合してサンプル信号を生成する。しかし、既存のフレキシブルサンプリング手法は、厳格な仮定と過度な緩和に依存しているという課題がある。このような課題を解決するために、本研究ではDC最適化技術を導入することで、このような厳格な仮定や過度な緩和を必要とせずにフレキシブルサンプリング演算子を設計する手法を目指す。これにより、本手法では、一般化サンプリング定理に基づく任意の事前知識を仮定したグラフ信号に対する安定的なサンプリングを行う。提案するサンプリング演算子の設計問題を解くために、general double-proximal gradient DC アルゴリズムに基づいて臨界点への収束が保証された効率的な解法を開発する。最後に、数値実験によって既存のアプローチと比較して、帯域制限を超えたグラフ信号のサンプリングと復元における本手法の優位性を実証した。

Reference

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

@misc{yamashita2025generalizedgraphsignalsampling,

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

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

      year={2025},

      eprint={2306.14634},

      archivePrefix={arXiv},

      primaryClass={eess.SP},

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

}

Links

• arXiv