抄録
CA-002
低ランク最適化のための高速特異値閾値処理の数理
佐々木崇元・北原正樹・清水 淳(NTT)
近年,多次元データが持つ低ランク性に基づくデータ解析,信号変換手法の研究が盛んである。これらの手法では,核型ノルム正則化に基づく最適化問題を立式し,間接的に低ランク性を扱うアプローチが一般的である。この最適化問題は一次法により効果的に求解できるが,核型ノルムの近接勾配である特異値閾値処理(SVT)が必要であり,中でも特異値分解(SVD)の計算複雑度が高いため,計算時間が増大していた。
 筆者らは特定条件下において,核型ノルムを最大値関数とL2ノルムの合成で表現することで,SVD不要なSVTアルゴリズムを提案しており,約70倍の高速化に成功している。本報告では核型ノルムの合成関数表現およびSVTアルゴリズムの数理的証明を示す。