準線形時間における有限Abel群上の2乗のスパースFourier和の計算【JST・京大機械翻訳】

Yang Jianting; Ye Ke; Zhi Lihong

プレプリント

J-GLOBAL ID：202202200047375774 整理番号：22P0026149

準線形時間における有限Abel群上の2乗のスパースFourier和の計算【JST・京大機械翻訳】

Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年01月11日プレプリントサーバーでの情報更新日： 2023年10月26日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

有限アベリアグループ上の関数の非負性を検証する問題は,長年の挑戦的な問題である。有限群の表現理論の基本理論は,有限アベルアングループG上の関数fが,f(x)=Σ_χ∈Gf(χ)χ(x)によるGの既約表現の特性の線形結合として記述でき,そこでは,GがGとf(χ)のすべての特性から成るGの二重グループが,ΔΔGにおけるfのFourier係数であることを示した。本論文では,高速(逆)Fourier変換を実行することにより,もし,もしfのk_minfがFSOSスパース性におけるGと多項式の次数において準線形であるならば,計算量を有する有限アベリアグループG上で,fのスパースFourier和(FSOS)証明書を計算量で計算できることを示した(|G|G|+log(k_min)演算子nameSDP(2k_min))。さらに,有限アベリアグループGとセットS⊂G上の非ネガタビエ関数fに対して,f+Mが}S上に担持されたFSOSを付加するような定数Mの下限を与えた。10 ̄7までの次数の様々なアベル群に関する数値実験によって提案アルゴリズムの効率性を実証した。また,アプリケーションとして,著者らは,スパースFSOSによるT ̄nfiに関して,いくつかの組合せ最適化問題とHermitian正方形(SOHS)問題の和も解決する。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , , 【Automatic Indexing@JST】

信号理論 , グラフ理論基礎

, ,

前のページに戻る