Случайные матрицы с ограничениями на длину строки и столбца

Мне нужно сгенерировать случайные неквадратные матрицы с $R$ строками и столбцами , элементами, случайно распределенными со средним значением = 0, и ограниченными таким образом, чтобы длина (норма L2) каждой строки составляла а длина каждого столбца составляла . Эквивалентно, сумма квадратных значений равна 1 для каждой строки и для каждого столбца. $C$ $1$ $\sqrt{\frac{R}{C}}$ $\frac{R}{C}$

До сих пор я нашел один способ достичь этого: просто инициализировать матричные элементы случайным образом (например, из равномерного, нормального или распределения Лапласа с нулевым средним и произвольной дисперсией), а затем поочередно нормализовать строки и столбцы в , заканчивающийся нормализацией строки. Похоже, что это довольно быстро сходится к желаемому результату (например, для и дисперсия длины столбца обычно составляет ~ после итераций), но я не уверен, могу ли я зависеть от этой быстрой скорости сходимости в общем (для различных размеров матрицы и начальных распределений элементов). ${\rm length} = 1$ $R=40$ $C=80$ $~0.00001$ $2$

Мой вопрос заключается в следующем: есть ли способ достичь желаемого результата ( , ) напрямую без итерации между нормализация строк / столбцов? Например, что-то вроде алгоритма нормализации случайного вектора (инициализируйте элементы случайным образом, измерьте сумму квадратов, затем масштабируйте каждый элемент с помощью общего скаляра). Если нет, существует ли простая характеристика скорости сходимости (например, num итераций до ошибки ) итерационного метода, описанного выше? ${\rm row \ lengths} = 1$ ${\rm column \ lengths} = \sqrt{\frac{R}{C}}$ $< \epsilon$

random-generation normalization markov-process random-matrix Тайлер Стритер
источник

Это очень похоже на алгоритм Синкхорна-Ноппа, также альтернативно известный как итеративная пропорциональная подгонка.

кардинал

Также вы должны определить, что вы подразумеваете под «случайными» матрицами. Например, процедура, которую вы описываете, (почти несомненно) не будет генерировать случайные матрицы равномерно по желаемому пространству.

кардинал

@ Cardinal Хороший вопрос. Но обратите внимание, что вы можете, по крайней мере, достичь одинакового (предельного) распределения для всех компонентов, умножив их на посту случайных матриц перестановок (чтобы случайным образом расположить как строки, так и столбцы).

whuber

@whuber: Да, хотя совместное распространение может быть довольно странным. Под «постмножением» я предполагаю, что вы имеете в виду умножение слева и справа «постсходимости» (а не, например, умножение справа).

кардинал

На самом деле, подумав немного, я думаю, что ваш алгоритм - это в точности алгоритм Синхорна-Кноппа с очень незначительной модификацией. Пусть

будет вашей исходной матрицей, и пусть

будет матрицей того же размера, что

. Затем, ваш алгоритм эквивалентно применения Sinkhorn-Кноппы к

, где на последний шаг восстановить нужную форму, принимая

X

$X$

Y

$Y$

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

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

Y

$Y$

. Синхорн-Нопп гарантированно сходится, за исключением довольно патологических обстоятельств. Читать об этом должно быть очень полезно.

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

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

кардинал

Как сказал @cardinal в комментарии:

На самом деле, подумав немного, я думаю, что ваш алгоритм - это в точности алгоритм Синхорна-Кноппа с очень незначительной модификацией. Пусть будет вашей исходной матрицей, и пусть будет матрицей того же размера, что . Затем, ваш алгоритм эквивалентно применения Sinkhorn-Кноппы к , где на последний шаг восстановить нужную форму, принимая $X$ $Y$ $Y_{ij}=X^2_{ij}$ $Y$ . Синхорн-Нопп гарантированно сходится, за исключением довольно патологических обстоятельств. Читать об этом должно быть очень полезно. $\hat{X}_{ij}=sgn(X_{ij})\sqrt{Y_{ij}}$

... кажется, что итерационный алгоритм, который я предложил в первоначальном вопросе, очень похож на алгоритм Синхорна-Кноппа. Интересно, что это также кажется очень похожим на итеративную пропорциональную подгонку (IPF), которая, как описано на странице Википедии IPF, связана с методом Ньютона и максимизацией ожиданий (у всех одинаковый предел).

Эти итерационные методы часто применяются к задачам, в которых отсутствует решение в закрытой форме, поэтому я предположу, что ответ на вопрос отрицательный: нет способа достичь желаемого решения без итерации строки / столбца.

Тайлер Стритер
источник

(+1) За постоянный интерес к этому вопросу и независимое наблюдение. :-)

кардинал

Случайные матрицы с ограничениями на длину строки и столбца

Ответы: