Golf kode matriks ortogonal acak

9

Sebuah matriks ortogonal adalah matriks persegi dengan entri nyata yang kolom dan baris yang ortogonal vektor satuan (yaitu, vektor ortonormal).

Ini berarti bahwa M ^ TM = I, di mana I adalah matriks identitas dan ^ T menandakan transposisi matriks.

Perhatikan bahwa ini adalah ortogonal bukan "ortogonal khusus" sehingga penentu M dapat 1 atau -1.

Tujuan dari tantangan ini bukanlah presisi mesin, jadi jika M ^ TM = I berada dalam 4 tempat desimal yang akan baik-baik saja.

Tugasnya adalah menulis kode yang mengambil bilangan bulat positif n > 1dan mengeluarkan matriks ortogonal acak n . Matriks harus dipilih secara acak dan seragam dari semua n oleh n matriks ortogonal. Dalam konteks ini, "seragam" didefinisikan dalam hal ukuran Haar, yang pada dasarnya mensyaratkan bahwa distribusi tidak berubah jika dikalikan dengan matriks ortogonal yang dipilih secara bebas. Ini berarti nilai-nilai matriks akan menjadi nilai floating point dalam rentang -1 hingga 1.

Input dan output dapat berupa bentuk apa pun yang Anda rasa nyaman.

Tolong tunjukkan contoh eksplisit dari menjalankan kode Anda.

Anda tidak dapat menggunakan fungsi pustaka yang ada yang membuat matriks ortogonal. Aturan ini sedikit halus sehingga saya akan menjelaskan lebih banyak. Aturan ini melarang penggunaan fungsi apa pun yang ada yang mengambil beberapa (atau tidak ada) input dan output matriks ukuran setidaknya n oleh n yang dijamin ortogonal. Sebagai contoh ekstrem, jika Anda ingin matriks identitas n demi n, Anda harus membuatnya sendiri.

Anda dapat menggunakan pustaka pembangkit nomor acak standar apa pun untuk memilih nomor acak yang Anda pilih.

Kode Anda harus selesai paling lama beberapa detik untuk n < 50.


sumber
Jadi menggunakan matriks identitas bawaan dilarang?
JungHwan Min
@ JKH Anda tidak bisa menggunakannya untuk membuat matriks identitas n by n setidaknya.
Bagaimana dengan diag? Ini menciptakan matriks diagonal yang memang ortogonal tetapi tidak selalu ortonormal.
Karl Napf
Ini tampaknya menjadi contoh "lakukan X tanpa Y", yang - jadi konsensus - harus dihindari.
flawr
1
Matriks diagonal bukan matriks ortogonal jadi diagharus ok.
Angs

Jawaban:

7

Haskell, 169 150 148 141 132 131 byte

import Numeric.LinearAlgebra
z=(unitary.flatten<$>).randn 1
r 1=asRow<$>z 1
r n=do;m<-r$n-1;(<>diagBlock[m,1]).haussholder 2<$>z n

Memperpanjang secara rekursif matriks ortogonal n-1dengan menambahkan 1 ke sudut kanan bawah dan menerapkan refleksi Householder acak. randnmemberikan matriks dengan nilai acak dari distribusi gaussian dan z dmemberikan vektor satuan terdistribusi secara merata dalam ddimensi.

haussholder tau vmengembalikan matriks I - tau*v*vᵀyang tidak ortogonal ketika vbukan merupakan vektor satuan.

Pemakaian:

*Main> m <- r 5
*Main> disp 5 m
5x5
-0.24045  -0.17761   0.01603  -0.83299  -0.46531
-0.94274   0.12031   0.00566   0.29741  -0.09098
-0.02069   0.30417  -0.93612  -0.13759   0.10865
 0.02155  -0.83065  -0.35109   0.32365  -0.28556
-0.22919  -0.41411   0.01141  -0.30659   0.82575
*Main> (<1e-14) . maxElement . abs $ tr m <> m - ident 5
True
Angs
sumber
Membuat 1×1matriks membutuhkan terlalu banyak ruang untuk seleraku, kasus khusus hanya untuk mendapatkan nol dari variabel acak gaussian: / (Tanpa itu, ada peluang sangat kecil untuk mendapatkan kolom nol)
Angs
Saya suka semangat Anda untuk membuatnya benar-benar benar, tetapi saya pikir Anda dapat membatalkan persyaratan itu. Dalam kode saya ada juga kemungkinan bahwa 2 baris tergantung linear dan tidak ada yang peduli.
Karl Napf
@ KarlNapf baik, saya menemukan cara untuk kehilangan dua byte dari bagian itu, jadi masalah sebagian terpecahkan :)
Angs
Ah oke, menghapus komentar saya ...
Karl Napf
Selalu senang saat jawaban Haskell menang!
4

Python 2 + NumPy, 163 byte

Terima kasih kepada xnor karena menunjukkan untuk menggunakan nilai acak terdistribusi normal bukan yang seragam.

from numpy import*
n=input()
Q=random.randn(n,n)
for i in range(n):
 for j in range(i):u=Q[:,j];Q[:,i]-=u*dot(u,Q[:,i])/dot(u,u)
Q/=(Q**2).sum(axis=0)**0.5
print Q

Menggunakan Orthogonalization Gram Schmidt pada matriks dengan nilai acak gaussian untuk memiliki semua arah.

Kode demonstrasi diikuti oleh

print dot(Q.transpose(),Q)

n = 3:

[[-0.2555327   0.89398324  0.36809917]
 [-0.55727299  0.17492767 -0.81169398]
 [ 0.79003155  0.41254608 -0.45349298]]
[[  1.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   1.00000000e+00  -5.55111512e-17]
 [  0.00000000e+00  -5.55111512e-17   1.00000000e+00]]

n = 5:

[[-0.63470728  0.41984536  0.41569193  0.25708079  0.42659843]
 [-0.36418389  0.06244462 -0.82734663 -0.24066123  0.3479231 ]
 [ 0.07863783  0.7048799   0.08914089 -0.64230492 -0.27651168]
 [ 0.67691426  0.33798442 -0.05984083  0.17555011  0.62702062]
 [-0.01095148 -0.45688226  0.36217501 -0.65773717  0.47681205]]
[[  1.00000000e+00   1.73472348e-16   5.37764278e-17   4.68375339e-17
   -2.23779328e-16]
 [  1.73472348e-16   1.00000000e+00   1.38777878e-16   3.33066907e-16
   -6.38378239e-16]
 [  5.37764278e-17   1.38777878e-16   1.00000000e+00   1.38777878e-16
    1.11022302e-16]
 [  4.68375339e-17   3.33066907e-16   1.38777878e-16   1.00000000e+00
    5.55111512e-16]
 [ -2.23779328e-16  -6.38378239e-16   1.11022302e-16   5.55111512e-16
    1.00000000e+00]]

Itu selesai dalam sekejap untuk n = 50 dan beberapa detik untuk n = 500.

Karl Napf
sumber
Saya tidak berpikir ini seragam. Distribusi awal Anda dengan sebuah kubus, yang memiliki lebih banyak barang diagonal. Gaussians acak akan berfungsi karena menghasilkan distribusi simetris bola.
xnor
@xnor diperbaiki. Untungnya, ini berharga tepat 1 byte.
Karl Napf
@ xnor Bahkan lebih beruntung, ini menyimpan byte untuk-0.5
Karl Napf
Hampir, Anda membutuhkan rata-rata normal menjadi 0, tetapi itu tidak lebih lama dari itu n.
xnor
-1

Mathematica, 69 byte, mungkin tidak bersaing

#&@@QRDecomposition@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

QRDecompositionmengembalikan sepasang matriks, yang pertama dijamin orthogonal (dan yang kedua tidak orthogonal, tetapi segitiga atas). Orang bisa berpendapat bahwa ini secara teknis mematuhi surat pembatasan di pos: itu tidak menghasilkan matriks ortogonal, tetapi sepasang matriks ....

Mathematica, 63 byte, jelas tidak bersaing

Orthogonalize@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

Orthogonalizejelas-jelas dilarang oleh OP. Tetap saja, Mathematica cukup keren ya?

Greg Martin
sumber
You may not use any existing library function which creates orthogonal **matrices**.
Karl Napf