Hasilkan matriks definitif positif simetris dengan pola sparsity yang ditentukan sebelumnya

9

Saya mencoba untuk menghasilkan matriks korelasi hal×hal (symmetric psd) dengan struktur sparsity yang ditentukan sebelumnya (ditentukan oleh grafik pada hal node). Node yang terhubung dalam grafik memiliki korelasi ρU(0,1) , sisanya semua adalah 0 dan diagonal adalah semua 1.

Saya telah mencoba membuat matriks ini beberapa kali tetapi jarang mendapatkan matriks korelasi yang valid.

Apakah ada cara yang bisa saya pastikan matriks korelasi whp? Perhatikan bahwa saya hanya dapat memiliki korelasi positif sehingga dll bukanlah pilihan.ρU(-1,1)

Setiap bantuan sangat dihargai!

Blade Runner
sumber
Mungkin fungsi nearPD dari paket Matrix di R dapat membantu.
niandra82
Apa ukuran Anda dari sparsity yang ditetapkan untuk Anda? Apakah data Anda harus biner atau nonnegatif terus menerus?
ttnphns
@ niandra82: nearPD tidak bagus karena akan menghancurkan sparsity dari matriks.
Blade Runner
1
Secara umum tidak ada distribusi matriks seperti yang dijelaskan dalam pertanyaan ini. Pertimbangkan, misalnya, kasus dengan tiga koefisien ρ , σ , τ . Jika τ = 0 dan ρ > 0 , σ > 0 , maka ρ 2 + σ 2 < 1 jika dan hanya jika matriksnya pasti positif. Tetapi kemudian Anda tidak dapat memiliki ρ U ( 0 , 1 ) dan σ U (3×3ρ,σ,ττ=0ρ>0,σ>0ρ2+σ2<1ρU(0,1) . σU(0,1)
whuber
3
Lalu mengapa tidak menghasilkan matriks korelasi terlebih dahulu. Kemudian buat indeks simetri untuk matriks tersebut di mana Anda memaksa elemen yang diindeks ke 0. Sparcity akan ditentukan oleh ukuran indeks dan Anda dapat memasukkan randommess melalui fungsi seperti sampel dalam r. Tidak peduli berapa banyak elemen diagonal yang Anda paksakan ke 0, matix akan tetap pd
Zachary Blumenfeld

Jawaban:

2

Tutup tetapi tidak ada cerutu untuk @Rodrigo de Azevedo.

Solusinya adalah dengan menggunakan pemrograman semidefinite untuk menemukan nilai maksimum, , dan nilai minimum (dikenakan nonnegatif), ρ m i n , dari ρ sehingga matriks korelasi dengan pola sparsity yang ditentukan adalah semidefinite positif (psd ). Semua nilai-nilai ρ sehingga ρ m sebuah xρ ρ m a xρmaxρminρρρmSebuahxρρmSebuahx , akan menghasilkan matriks PSD (latihan bagi pembaca)

Oleh karena itu, Anda harus memilih distribusi yang hanya dapat mengambil nilai dalam [ ρ m a x , ρ m a x ] , atau Anda harus menggunakan penerimaan / penolakan dan menolak nilai-nilai ρ yang dihasilkanρ[ρmSebuahx,ρmSebuahx]ρ yang yang tidak menghasilkan matriks psd.

Contoh untuk matriks 4 oleh 4 menggunakan YALMIP di bawah MATLAB

sdpvar rho % declare rho to be a scalar variable
% find maximum value of rho (by minimizing -rho) subject to prescribed matrix being psd.
optimize([1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,-rho) 
% find minimum value of rho subject to prescribed matrix being psd and rho being >= 0.
optimize([[1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,rho >= 0],rho) 

Hasil: maksimum rho = 0,57735, minimum rho = 0. Sudah jelas bahwa nol akan menjadi nilai minimum rho yang dikenakan rho menjadi tidak negatif dan matriks yang ditentukan menjadi psd, terlepas dari dimensi atau pola sparsity. Oleh karena itu, tidak perlu menjalankan optimasi semidefinite untuk menemukan nilai minimum negatif dari .ρ

Mark L. Stone
sumber
4
Ini adalah interpretasi yang menarik dari pertanyaan: mengasumsikan semua koefisien off-diagonal bukan nol sama (dengan demikian sangat menyederhanakan masalah). Tidak jelas apakah itu interpretasi yang dimaksud, atau apakah semua koefisien non-nol-diagonal dianggap sebagai realisasi independen dari distribusi umum.
Whuber
Itulah interpretasi yang saya buat. Sekarang setelah Anda menyebutkannya, saya bisa melihat interpretasi yang berbeda menjadi mungkin. Setidaknya interpretasi saya memiliki sifat menghasilkan masalah yang cukup jelas. Saya kira suatu masalah dapat dirumuskan, yang solusinya belum saya teliti, untuk menemukan nilai maksimum ρ sehingga semua elemen non-nol-diagonal satu segitiga dari matriks korelasi dapat diisi dengan nilai-nilai non-negatif yang tidak sama dengan ≤ nilai itu, dan tentu saja membuat matriks yang terisi penuh menjadi psd.
Mark L. Stone
0

Matriks korelasi simetris, semidefinit positif, dan memiliki pada diagonal utamanya. Satu dapat menemukan n × n matriks korelasi dengan memecahkan berikut Program semidefinite (SDP) di mana fungsi tujuan adalah sewenang-wenang, katakanlah, fungsi nol1n×n

memperkecilHAIn,Xtunduk padax11=x22==xnn=1XHAIn

Jika seseorang memiliki kendala tambahan, seperti kendala sparsity

xsayaj=0 untuk semua (saya,j)Z[n]×[n]

dan kendala non-negatif, , maka seseorang memecahkan SDP berikutXHAIn

memperkecilHAIn,Xtunduk padax11=x22==xnn=1xsayaj=0 untuk semua (saya,j)Z[n]×[n]XHAInXHAIn

A 3×3 contoh

Misalkan kita ingin punya x13=0x12,x230

cvx_begin sdp

    variable X(3,3) symmetric

    minimize( trace(zeros(3,3)*X) )
    subject to

        % put ones on the main diagonal
        X(1,1)==1
        X(2,2)==1
        X(3,3)==1

        % put a zero in the northeast and southwest corners
        X(1,3)==0

        % impose nonnegativity
        X(1,2)>=0
        X(2,3)>=0

        % impose positive semidefiniteness
        X >= 0

cvx_end

Menjalankan skrip,

Calling sedumi: 8 variables, 6 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 6, order n = 6, dim = 12, blocks = 2
nnz(A) = 8 + 0, nnz(ADA) = 36, nnz(L) = 21
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            3.00E+000 0.000
  1 : -1.18E-001 6.45E-001 0.000 0.2150 0.9000 0.9000   1.86  1  1  1.2E+000
  2 : -6.89E-004 2.25E-002 0.000 0.0349 0.9900 0.9900   1.52  1  1  3.5E-001
  3 : -6.48E-009 9.72E-007 0.097 0.0000 1.0000 1.0000   1.01  1  1  3.8E-006
  4 : -3.05E-010 2.15E-009 0.000 0.0022 0.9990 0.9990   1.00  1  1  1.5E-007
  5 : -2.93E-016 5.06E-015 0.000 0.0000 1.0000 1.0000   1.00  1  1  3.2E-013

iter seconds digits       c*x               b*y
  5      0.3   5.8  0.0000000000e+000 -2.9302886987e-016
|Ax-b| =  1.7e-015, [Ay-c]_+ =  6.1E-016, |x|= 2.0e+000, |y|= 1.5e-015

Detailed timing (sec)
   Pre          IPM          Post
1.563E-001    2.500E-001    1.094E-001    
Max-norms: ||b||=1, ||c|| = 0,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0

Mari kita lihat solusi apa yang ditemukan CVX,

>> X

X =

    1.0000    0.4143         0
    0.4143    1.0000    0.4143
         0    0.4143    1.0000

Apakah matriks ini semidefinit positif? Yang pasti positif?

>> rank(X)

ans =

     3

>> eigs(X)

ans =

    1.5860
    1.0000
    0.4140

Ini pasti positif, seperti yang diharapkan. Kita dapat menemukan matriks korelasi semidefinit positif dengan memilih fungsi objektif yang bukan nol (linier).

Rodrigo de Azevedo
sumber
Karena di situs ini "menghasilkan" akan dipahami berarti "menarik dari distribusi acak," dapatkah Anda menjelaskan bagaimana kode Anda menghasilkan matriks korelasi acak dan menunjukkan distribusi apa yang mereka ikuti?
whuber
[-1,1](n2)
1
[0,1](n2)
3
3×3xsayaj=00
1
Itu cara yang bagus untuk menggambarkan situasi.
whuber
3
Anda benar tentang bagaimana volume relatif menyusut. Itulah mengapa ini adalah masalah yang sulit.
Whuber