OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
-
Jelani Nelson, Huy L. Nguyen
-
In FOCS 2013
-
線形空間の次元削減の話
-
問題
-
(1-eps)||x||≦||Πx||≦(1+eps)||x||
-
Π:R^n→R^m
-
Πはm×n行列上の確率分布Dに従う
-
設計したいのはD
-
応用
-
min ||Ax-b||
-
min ||ΠAx-Πb||にする
-
m<dなら解きやすい
-
だけど、Πが疎じゃないと意味ない(行列演算が重くなる
-
結果
-
(i)既存の評価をimprove
-
非ゼロは各列1つだけ
-
Π_i(j),j=σ∈{-1,+1}
-
これだけ
-
(ii)非ゼロO(poly log d)
FOCS
2013-11-03 02:16:43 (Sun)
最終更新:2013年11月03日 02:16