Создать симметричную положительно определенную матрицу с заранее заданным шаблоном разреженности

Я пытаюсь сгенерировать корреляционную матрицу (симметричный psd) с заранее заданной разреженной структурой (указанной графом на узлах). Узлы, которые связаны в графе, имеют корреляцию , все остальные равны 0, а диагональ равна 1. $p\times p$ $p$ $\rho \sim U(0,1)$

Я пытался сгенерировать эту матрицу несколько раз, но только редко получал действительную матрицу корреляции.

Есть ли способ, которым я могу обеспечить корреляционную матрицу whp? Обратите внимание, что у меня может быть только положительная корреляция, поэтому и т. Д. Не вариант. $\rho \sim U(-1,1)$

Любая помощь с благодарностью!

correlation matrix sparse correlation-matrix Бегущий по лезвию
источник

Может быть, функция nearPD пакета Matrix в R может помочь.

niandra82

Какова ваша мера редкости, которая установлена для вас? Должны ли ваши данные быть двоичными или неотрицательными непрерывными?

ttnphns

@ niandra82: nearPD не годится, так как разрушает разреженность матрицы.

Бегущий по лезвию

В общем случае нет таких матричных распределений, как описано в этом вопросе. Рассмотрим, например, случай

с тремя коэффициентами

. Если

, то

тогда и только тогда, когда матрица положительно определена. Но тогда вы не можете иметь и

3 \times 3

$3\times 3$

ρ, σ, τ

$\rho,\sigma,\tau$

τ = 0

$\tau=0$

ρ > 0, σ > 0

$\rho\gt 0, \sigma\gt 0$

ρ^{2} + σ^{2} < 1

$\rho^2+\sigma^2\lt 1$

ρ \sim U (0, 1)

$\rho\sim U(0,1)$

σ \sim U (0, 1)

$\sigma\sim U(0,1)$

whuber

Тогда почему бы сначала не сгенерировать матрицу корреляции. Затем создайте симметричный индекс для этой матрицы, в котором индексированные элементы равны нулю. Разница будет определяться размером индекса, и вы можете использовать случайную переменную с помощью функции, подобной sample в r. Независимо от того, сколько не диагональных элементов вы выставите в 0, matix все равно будет pd

Zachary Blumenfeld

Ответы:

Близко, но нет сигары для @Rodrigo de Azevedo.

Решение состоит в том, чтобы использовать полуопределенное программирование, чтобы найти максимальное значение и минимальное значение (при условии, что оно неотрицательно), , , так что матрица корреляции с заданным шаблоном разреженности является положительной полуопределенной (psd). ). Все значения такое , что , будет производить PSD матрицы (упражнение для читателя) $\rho_{max}$ $\rho_{min}$ $\rho$ $\rho$ $\rho_{max}\le \rho \le \rho_{max}$

Следовательно, вы должны либо выбрать распределение которое может принимать значения только в , либо вы должны использовать принятие / отклонение и отклонить любые сгенерированные значения которые не производят матрицу psd. $\rho$ $[\rho_{max},\rho_{max}]$ $\rho$

Пример для матрицы 4 на 4 с использованием YALMIP под 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)

Результаты: максимальное значение rho = 0,57735, минимальное значение rho = 0. Очевидно, что нулевое значение будет минимальным значением rho при условии, что rho является неотрицательным, а заданная матрица - psd, независимо от размерности или разреженности. Следовательно, нет необходимости запускать полуопределенную оптимизацию, чтобы найти минимальное неотрицательное значение . $\rho$

Марк Л. Стоун
источник

Это интересная интерпретация вопроса: она предполагает, что все ненулевые недиагональные коэффициенты равны (что значительно упрощает задачу). Неясно, была ли это предполагаемая интерпретация, или все ненулевые недиагональные коэффициенты должны быть независимыми реализациями из общего распределения.

whuber

Это интерпретация, которую я сделал. Теперь, когда вы упомянули это, я увидел, что возможна другая интерпретация. По крайней мере, моя интерпретация имеет то преимущество, что приводит к довольно четко определенной проблеме. Я полагаю, что можно сформулировать задачу, решение которой я не исследовал, найти максимальное значение ρ так, чтобы все ненулевые недиагональные элементы одного треугольника матрицы корреляции могли быть заполнены необязательно равными неотрицательными значениями ≤ это значение, и обязательно сделать полностью заполненную матрицу PSD.

Марк Л. Стоун

Корреляционная матрица является симметричной, положительно полуопределенной и имеет на своей главной диагонали. Можно найти корреляционную матрицу , решив следующую полуопределенную программу (SDP), где целевая функция произвольна, скажем, нулевая функция $1$ $n \times n$

\begin{array}{ll} минимизировать & ⟨ О_{N}, Икс ⟩ \\ при условии & {Икс}_{11} знак равно {Икс}_{22} знак равно \dots знак равно {Икс}_{N N} знак равно 1 \\ Икс ⪰ О_{N} \end{array}

$\begin{array}{ll} \text{minimize} & \mathrm \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & x_{11} = x_{22} = \cdots = x_{nn} = 1\\ & \mathrm X \succeq \mathrm O_n\end{array}$

Если у вас есть дополнительные ограничения, такие как ограничения по разреженности

{Икс}_{я J} знак равно 0 для всех (я, J) \in Z \subset [N] \times [N]

$x_{ij} = 0 \text{ for all } (i,j) \in \mathcal Z \subset [n] \times [n]$

и неотрицательные ограничения, , то один решает следующее SDP $\mathrm X \geq \mathrm O_n$

\begin{array}{ll} минимизировать & ⟨ О_{N}, Икс ⟩ \\ при условии & {Икс}_{11} знак равно {Икс}_{22} знак равно \dots знак равно {Икс}_{N N} знак равно 1 \\ {Икс}_{я J} знак равно 0 для всех (я, J) \in Z \subset [N] \times [N] \\ Икс \geq О_{N} \\ Икс ⪰ О_{N} \end{array}

$\begin{array}{ll} \text{minimize} & \mathrm \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & x_{11} = x_{22} = \cdots = x_{nn} = 1\\ & x_{ij} = 0 \text{ for all } (i,j) \in \mathcal Z \subset [n] \times [n]\\ & \mathrm X \geq \mathrm O_n\\ & \mathrm X \succeq \mathrm O_n\end{array}$

Пример $3 \times 3$

$x_{13} = 0$ $x_{12}, x_{23} \geq 0$

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

Запуск сценария,

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

Посмотрим, какое решение нашел CVX,

>> X

X =

    1.0000    0.4143         0
    0.4143    1.0000    0.4143
         0    0.4143    1.0000

Является ли эта матрица положительной полуопределенной? Положительно определен?

>> rank(X)

ans =

     3

>> eigs(X)

ans =

    1.5860
    1.0000
    0.4140

Это положительно определенно, как и ожидалось. Мы можем найти положительные полуопределенные корреляционные матрицы, выбрав ненулевую (линейную) целевую функцию.

Родриго де Азеведо
источник

Поскольку на этом сайте под «генерацией» подразумевается «извлечь из случайного распределения», не могли бы вы объяснить, как ваш код генерирует матрицы случайной корреляции, и указать, за каким распределением они следуют?

whuber

[- 1, 1]^{(\binom{N}{2})}

$[-1,1]^{\binom{n}{2}}$

1

$1$

[0, 1]^{(\binom{N}{2})}

$[0,1]^{\binom{n}{2}}$

3 \times 3

$3 \times 3$

x_{i j} = 0

$x_{ij} = 0$

≻ 0

$\succ 0$

Это отличный способ описать ситуацию.

whuber

Вы правы относительно того, как уменьшаются относительные объемы. Именно поэтому это сложная проблема.

whuber