2013-03-14 1 views
7

疎な行列を効率的に格納するためのRのパッケージがあることは知っています。低ランクの行列を効率的に格納する方法もありますか?たとえば:大きいが低いランクの行列を効率的に格納する

A <- matrix(rnorm(1e6), nrow=1e5, ncol=1e1) 
B <- A %*% t(A) 

は今、Bは、メモリに格納するには余りにも大きいですが、それは、ランクが低いです。効率的な方法でBを構築して保存する方法はありますか?そのため、CPUやメモリを交換するために、いくつかの基本的な読み取り方法(rowSumscolSumsなど)が実行されていますか?私は、これは大きな行列のためになる方法を効率的に知るために経験を逃すものの、ここで

+0

興味深い質問 - アプリケーションにはどのようなものがありますか? –

+0

@DavidRobinson:これらの行列は、いくつかの[最適化アルゴリズム](http://www.adobe.com)で、(計算には大きすぎる、または格納するには大きすぎる)密行列の近似として使用されます。 /en.wikipedia.org/wiki/Limited-memory_BFGS)。 –

+1

Bを近似したい場合は、低次元の近似を使用できますか? SVDを使用し、SVDの最初のn次元を維持しますか? これはあなたが欲しいものですが、考慮する価値があるかもしれません。 –

答えて

0

は、別のアプローチです:

ランクが低い場合、それは行列が他の線形結合である多くの無関係な行を、含むことを意味します。行列が方程式の線形システムを表す場合、それらの線を連続的に除去するアルゴリズムを設計することができる。

行が無関係かどうかをチェックするには、その行のない行列のランクが同じであるかどうかを確認します。行列のランクを計算するには、thisthat答えを参照してください。

+1

それは基本的に非常に高価なファクタリングのように聞こえます:-) – Jeroen

+0

申し訳ありませんが、ひどくレプリケートされた行を持つ単純なケースでのみ機能する貧弱なアイデアです。実際、ランク1の行列を生成するのはトライアルであり、それは複製されない行または列を持たない。したがって、ランダムな行ベクトルUおよびVを選ぶと、U '* Vはランク1を持つ。 –

2

あなたの質問はすでに答えています:このような低ランクの行列を効率的に保存するには、両方の要素を含むデータ構造を作成します。行列 - ベクトル乗算が必要な場合は、要素の行列 - ベクトル積を使用して右から左へ行うことができます。

制限付きメモリBroydenまたはBFGS準ニュートン法の実装では、このストラテジおよびデータ構造の1つのアプリケーションを見つけることができます。