Matriks acak dengan batasan panjang baris dan kolom

Saya perlu membuat matriks non-kuadrat acak dengan baris dan kolom , elemen yang didistribusikan secara acak dengan mean = 0, dan dibatasi sedemikian rupa sehingga panjang (norma L2) dari setiap baris adalah dan panjang setiap kolom adalah . Secara ekuivalen, jumlah nilai kuadrat adalah 1 untuk setiap baris dan untuk setiap kolom. $R$ $C$ $1$ $\sqrt{\frac{R}{C}}$ $\frac{R}{C}$

Sejauh ini saya telah menemukan satu cara untuk mencapai ini: cukup inisialisasi elemen matriks secara acak (misalnya dari distribusi seragam, normal, atau laplace dengan nol mean dan varian sewenang-wenang), kemudian secara normal menormalkan baris dan kolom menjadi , diakhiri dengan normalisasi baris. Ini tampaknya menyatu dengan hasil yang diinginkan cukup cepat (misalnya untuk dan , varians panjang kolom biasanya ~ setelah iterasi), tapi saya tidak yakin apakah saya bisa bergantung pada tingkat konvergensi cepat ini. secara umum (untuk berbagai dimensi matriks dan distribusi elemen awal). ${\rm length} = 1$ $R=40$ $C=80$ $~0.00001$ $2$

Pertanyaan saya adalah ini: apakah ada cara untuk mencapai hasil yang diinginkan ( , ) secara langsung tanpa beralih antara normalisasi baris / kolom? Misalnya sesuatu seperti algoritma untuk menormalkan vektor acak (menginisialisasi elemen secara acak, mengukur jumlah nilai kuadrat, lalu skala setiap elemen dengan skalar yang sama). Jika tidak, adakah karakterisasi sederhana untuk laju konvergensi (misal, jumlah iterasi hingga kesalahan ) dari metode iteratif yang dijelaskan di atas? ${\rm row \ lengths} = 1$ ${\rm column \ lengths} = \sqrt{\frac{R}{C}}$ $< \epsilon$

random-generation normalization markov-process random-matrix Tyler Streeter
sumber

Ini sangat mirip dengan algoritma Sinkhorn-Knopp, yang juga dikenal sebagai iterative proporsional fitting.

kardinal

Juga, Anda harus mendefinisikan apa yang Anda maksud dengan matriks "acak". Sebagai contoh, prosedur yang Anda gambarkan akan (hampir tidak diragukan) tidak menghasilkan matriks acak secara seragam di atas ruang yang diinginkan.

kardinal

@ kardinal Poin bagus. Tetapi perhatikan bahwa Anda setidaknya dapat mencapai distribusi yang identik (marginal) untuk semua komponen dengan mengalikannya dengan sepasang matriks permutasi acak (untuk mengatur secara acak baris dan kolom).

whuber

@whuber: Ya, meskipun distribusi bersama masih bisa sangat aneh. Dengan "posting mengalikan" Saya menganggap Anda mengalikan di sebelah kiri dan kanan "pasca-konvergensi" (daripada, misalnya, mengalikan di sebelah kanan).

kardinal

Sebenarnya, setelah sedikit berpikir, saya pikir algoritma Anda persis algoritma Sinkhorn-Knopp dengan modifikasi yang sangat kecil. Biarkan

menjadi matriks asli Anda dan biarkan

menjadi matriks dengan ukuran yang sama sehingga

. Kemudian, algoritma Anda setara dengan menerapkan Sinkhorn-Knopp ke

, di mana pada langkah terakhir Anda memulihkan bentuk yang Anda inginkan dengan mengambil

X

$X$

Y

$Y$

Y_{i j} = X_{i j}^{2}

$Y_{ij} = X_{ij}^2$

Y

$Y$

. Sinkhorn-Knopp dijamin akan bertemu kecuali dalam keadaan yang cukup patologis. Membaca tentang itu harus sangat membantu.

{\hat{X}}_{i j} = s g n (X_{i j}) \sqrt{Y_{i j}}

$\hat{X}_{ij} = \mathrm{sgn}(X_{ij}) \sqrt{Y_{ij}}$

kardinal

Seperti @ cardinal katakan dalam komentar:

Sebenarnya, setelah sedikit berpikir, saya pikir algoritma Anda persis algoritma Sinkhorn-Knopp dengan modifikasi yang sangat kecil. Biarkan menjadi matriks asli Anda dan biarkan menjadi matriks dengan ukuran yang sama sehingga . Kemudian, algoritma Anda setara dengan menerapkan Sinkhorn-Knopp ke , di mana pada langkah terakhir Anda memulihkan bentuk yang Anda inginkan dengan mengambil $X$ $Y$ $Y_{ij}=X^2_{ij}$ $Y$ . Sinkhorn-Knopp dijamin akan bertemu kecuali dalam keadaan yang cukup patologis. Membaca tentang itu harus sangat membantu. $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$

... tampaknya algoritma berulang yang saya sarankan dalam pertanyaan asli sangat mirip dengan algoritma Sinkhorn-Knopp. Menariknya, itu juga tampak sangat mirip dengan iterative proporsional fitting (IPF), yang, seperti yang dijelaskan pada halaman wikipedia IPF, terkait dengan metode Newton dan maksimalisasi harapan (semuanya memiliki batas yang sama).

Metode berulang ini sering diterapkan pada masalah yang tidak memiliki solusi bentuk tertutup, jadi saya akan sementara menganggap bahwa jawaban untuk pertanyaan itu negatif: tidak ada cara untuk mencapai solusi yang diinginkan tanpa iterasi baris / kolom.

Tyler Streeter
sumber

(+1) Untuk minat Anda yang berkelanjutan pada pertanyaan ini dan tindak lanjut independen Anda. :-)

cardinal

Matriks acak dengan batasan panjang baris dan kolom

Jawaban: