OSNAP: Faster numerical linear algebra algorithms via sparser subspace ... - todo314 @ ウィキ

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)