Fast and Guaranteed Tensor Decomposition via Sketching, NIPS2015
Tensor CANDECOMP/PARAFAC (CP) decompositionはSVDの一般化でテンソルに適用可能にしたものである。
本論では、count sketchingの手法に基づいた高速で確率的なCP decompositionを提案する。
Count sketchingは計算オーダーが対象とする行列の非ゼロ要素数に依存する手法で、sketch行列の列番号をランダムに割り当て、和を取る事で縮約する方法である。
提案手法はFFTによるテンソル縮約を行う事で、具体的なテンソル計算を回避する。
またcolliding hash関数を用いる事で効率的なsketching計算を行う。
さらにpower iterative techniquesとwhitening手法を組み合わせる事で高速なアルゴリズムを開発した。
この手法は密、または疎な行列双方に適用可能である。
近似誤差はスパース性や要素の一様性などに依存しない。
Efficient Compressive Phase Retrieval with Constrained Sensing Vectors, NIPS2015
Compressive phase retrieval問題を扱う。
この問題は大きさの観測値よりそれを発生させた潜在的なスパースベクトルを復元する問題である。
従来手法は、sample complexityが最適ではなく、またロバスト性が獲得出来ていなかった。
またスパース性と低ランク性の双方を仮定した場合の手法は難しい。
提案手法では、それぞれ一貫しない部分空間からランダムにsensingベクトルを選ぶことで、効率的にスパース要素と低ランク要素を分離する。
そしてスパース部と低ランク部に分けて２段階の凸計画問題を逐次的に解くことでスパースベクトルは再構成される。
この手法はSample complexityが条件を満たせば、精度の高い予測が可能である。
Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees, NIPS2015
最近では積分計算を推論問題として捉え直す動きが出てきている。
従来手法ではGPを用いて積分推論をするBayesian Quadratureがあるが、理論的な保証がない。
本論では、理論的な収束保証が可能な積分推論の手法としてFrack-Wolfe Bayesian Quadratureを提案する。
本手法は積分値の事後分布に関して指数的な収束が可能である。