仕事のためにランダムな平均不変直交行列をたくさん生成する必要があります。平均不変行列にはプロパティ がありますA*1_n=1_n。ここで、1_n はスカラー 1 のサイズ n のベクトルであり、基本的にnp.ones(n)です。Python、特に Numpy を使用して行列を作成していますが、自分の方法が正しく、最も効率的であることを確認したいと考えています。また、私が試した 3 つの別々の直交化方法に関する調査結果を提示し、うまくいけば、ある方法が他の方法よりも高速である理由について説明したいと思います。投稿の最後で、調査結果について 4 つの質問をします。
一般に、平均不変ランダム直交行列 A を作成するには、ランダム正方行列 M1 を作成し、その最初の列を 1 の列に置き換えて、行列を直交化する必要があります。次に、別の行列 M2 を使用してこれを繰り返します。最終的な平均不変ランダム直交行列は A = M1*(M2.T) です。このプロセスのボトルネックは直交化です。直交化には主に 3 つの方法があります。つまり、射影を使用するグラム・シュミット過程、鏡映とギブンス回転を使用するハウスホルダー変換です。
Numpy: を使用すると、nxn ランダム行列を簡単に作成できます
M1 = np.random.normal(size=(n,n))。次に、M1 の最初の列を 1_n に置き換えます。
私が知る限り、Gram-Schmidt プロセスは非常に人気のあるライブラリには存在しないため、問題なく動作する次のコードを見つけました。
def gram_schmidt(M1):
"""Orthogonalize a set of vectors stored as the columns of matrix M1."""
# Get the number of vectors.
n = M1.shape[1]
for j in range(n):
# To orthogonalize the vector in column j with respect to the
# previous vectors, subtract from it its projection onto
# each of the previous vectors.
for k in range(j):
M1[:, j] -= np.dot(M1[:, k], M1[:, j]) * M1[:, k]
M1[:, j] = M1[:, j] / np.linalg.norm(M1[:, j])
return M1
明らかに、上記のコードは M1 と M2 の両方に対して実行する必要があります。
10,000x10,000 ランダム平均不変直交行列の場合、このプロセスは私のコンピューター (8 コア @3.7GHz、16GB RAM、512GB SSD) で約1 時間かかります。
Gram-Schmidt プロセスの代わりに、Numpy で行列を直交化できることがわかりました。
q1, r1 = np.linalg.qr(M1)
ここで、q1 は直交化された行列で、r1 は上三角行列です (r1 を保持する必要はありません)。M2 に対しても同じことを行い、q2 を取得します。次に、A=q1*(q2.T)。同じ 10,000x10,000 マトリックスのこのプロセスは、同じコンピューターで約70 秒かかります。ライブラリはハウスホルダー変換を使用していると思いますlinalg.qr()が、誰かに確認してもらいたいです。
最後に、最初の乱数行列 M1 と M2 が生成される方法を変更しようとしました。代わりに
M1 = np.random.normal(size=(n,n))、ディリクレ分布: を使用しました
M1 = np.random.default_rng().dirichlet(np.ones(n),size=(n))。その後、linalg.qr()以前のようなものを使用して、 とほぼ同じ時間で 10000x10000 マトリックスを取得しましたM1 = np.random.normal(size=(n,n))。
私の質問は次のとおりです。
- Numpy の
np.linalg.qr()メソッドは実際に Householder 変換を使用しますか? それともギブンズの回転？ - グラム-シュミット法が よりもずっと遅いのは
np.linalg.qr()なぜですか? - ディリクレ過程がほぼ直交行列を生成することを知っています。10,000 次元を作成しているため、他のすべてのベクトルと直交するベクトルがランダムに取得される可能性が高いためですか? は
np.linalg.qr()、行列が直交性にどれだけ近いかを気にしません。 - ランダムな直交行列を生成するさらに高速な方法はありますか? コードを高速化/効率化するためにコードを最適化できますか?
編集:cp.linalg.qr()同じ 10,000x10,000 のランダム マトリックスでの cupy は、CPU での numpy の 70 秒ではなく、私の 2080ti で 16 秒しかかかりません (8 コア @3.7 GHz マルチスレッド、16 GB RAM および 512 GB SSD)。