Глупый вопрос о генерации случайных векторов

[arseniiv]

Пусть в некотором евклидовом пространстве (вообще трёхмерном, но это не должно успокаивать) есть единичный вектор $\mathbf v$, и мы хотим сгенерировать вектор $\mathbf u$, распределённый в подпространстве $X = \langle\mathbf v\rangle^\perp$ (а) стандартно нормально или (б) равномерно по его единичной сфере.

Можно ли это сделать и не находя базиса $X$ (я был бы ещё может быть не против, если бы для неизменного $\mathbf v$ надо было нагенерировать кучу разных $\mathbf u$, но он каждый раз будет чуть-чуть другой), и генерируя ${}\leqslant m = \dim X$ нормально распределённых значений?

У меня решается задача (б), а задача (а) здесь добавлена для полноты; текущий способ такой: берётся $\pmb\xi\sim\mathcal N_m$, вычисляются $\mathbf u' = \pmb\xi - (\pmb\xi, \mathbf v)\mathbf v$ (выкинули лишнюю размерность), $\mathbf u = \mathbf u'/\lVert\mathbf u'\rVert$ (выкинули длину). Как видно, этот способ удовлетворяет первому, но не второму требованию, и хотя не жалко сгенерировать лишнюю величину, всё же интересно, нельзя ли что-то сделать.

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

[Geen]

arseniiv в сообщении #1334205 писал(а):

хотя не жалко сгенерировать лишнюю величину, всё же интересно, нельзя ли что-то сделать.

Какой ценой??

[mihaild]

Если хочется, можно одно лишнее число "вернуть назад" - воспользоваться тем, что скалярное произведение с $\mathbf v$ распределено нормально и независимо с получившимся $\mathbf u$. В итоге для генерации $k$ векторов нам понадобится $km + 1$ случайная величина.

arseniiv в сообщении #1334205 писал(а):

$\mathbf u' = (\pmb\xi, \mathbf v)\mathbf v$

Тут точно не должно быть $\mathbf u' = \pmb \xi - (\pmb\xi, \mathbf v)\mathbf v$?

[arseniiv]

Geen в сообщении #1334219 писал(а):

Какой ценой??

Ну, этот вопрос в общем теоретический, так что любой, какой вам не жалко.

mihaild в сообщении #1334225 писал(а):

Тут точно не должно быть $\mathbf u' = \pmb \xi - (\pmb\xi, \mathbf v)\mathbf v$?

О, спасибо. У меня там в коде было -=, так что вышла такая ошибка здесь. Исправляю.

mihaild в сообщении #1334225 писал(а):

Если хочется, можно одно лишнее число "вернуть назад" - воспользоваться тем, что скалярное произведение с $\mathbf v$ распределено нормально и независимо с получившимся $\mathbf u$.

О, красиво! (Хотя я бы не стал этим пользоваться в коде для Mathematica, оверхед манипуляций отдельными значениями может выйти больше, чем если нагенерировать изначально список побольше; с другой стороны, кому-то в низкоуровневом коде это точно было бы полезным.)

[ewert]

arseniiv в сообщении #1334205 писал(а):

У меня решается задача (б), а задача (а) здесь добавлена для полноты; текущий способ такой: берётся $\pmb\xi\sim\mathcal N_m$

А зачем $\mathcal N$-то (для второго пункта)? Берём равномерно распределённый вектор из куба и тупо отбраковываем, если он не в шаре, далее по тексту. Коэффициент отбраковки примерно 0.5 для трёхмерного случая, вполне приемлемо. Дальше будет, конечно, хуже, но для не особо больших размерностей всё равно сойдёт.

[arseniiv]

ewert в сообщении #1334848 писал(а):

Берём равномерно распределённый вектор из куба и тупо отбраковываем, если он не в шаре, далее по тексту.

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

Сам вопрос здесь, как я уже писал, больше теоретический: нам в некотором смысле приходится получать трёхмерный вектор, несмотря на то, что от них остаётся объект с двумя степенями свободы. Можно представить ситуацию, когда надо взять $N$ чисел и потом оставить что-то с $n\ll N$ степенями свободы. Практические решения, которые предложили (и ваше) меня полностью устраивают, но некоторая ферматическая неудовлетворённость остаётся.

[mihaild]

Пусть мы изначально сгенерировали двумерный вектор $\pmb \xi$ и сделали из него вектор $f(\pmb \xi, \mathbf v) \perp \mathbf v, \|f(\pmb \xi)\| = 1$. Тогда $f$ - "плохая" по второму аргументу, иначе $f(\pmb \xi, \mathbf v)$ при фиксированном $\pmb \xi$ было бы причесыванием ежа.
Что не означает, что такой $f$ невозможно, особенно с учетом того, что нас интересует только поведение почти наверное, а почти причесать ежа можно. Но означает, что нам придется выписывать какие-то не очень красивые штуки.

[ewert]

arseniiv в сообщении #1334897 писал(а):

нам в некотором смысле приходится получать трёхмерный вектор, несмотря на то, что от них остаётся объект с двумя степенями свободы

Это в известном смысле тоже отбраковка -- 30%-процентная (а при повышении размерности всё менее и менее существенная). Те или иные накладные расходы будут всегда. Вопрос лишь в суммарных затратах. Не представляю себе, как это генерация эн нормально распределённых случайных величин может оказаться дешевле генерации эн равномерных; ну разве что в символах кода выйдет на три-четыре байта короче.

[mihaild]

ewert в сообщении #1334905 писал(а):

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

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

UPD: более точно (если пренебречь тем, что равномерное распределение на $[-1; 1]$ может на практике попасть в $0$ или не попасть в $[-1; 1]$ и не проверять на это) - достаточно сгенерировать две величины равномерно на $[-1; 1]$, посчитать $5$ произведений (из них одно - на константу), одно частное, один корень и один логарифм для получения двух нормально распределенных величин.

[venco]

arseniiv в сообщении #1334897 писал(а):

Кроме того, в потенциальном практическом приложении можно нагенерировать заранее большую кучу нормально распределённых величин достаточно дёшево

Вроде бы эффективный метод генерации нормальных случайных чисел как раз с отбраковкой.

[arseniiv]

mihaild в сообщении #1334902 писал(а):

Тогда $f$ - "плохая" по второму аргументу, иначе $f(\pmb \xi, \mathbf v)$ при фиксированном $\pmb \xi$ было бы причесыванием ежа.

(О, то есть это у нас размерность пространства неудачная! ) Спасибо за результат, действительно просто.

[mihaild]

arseniiv в сообщении #1334922 писал(а):

О, то есть это у нас размерность пространства неудачная

Ну на самом деле тот же аргумент применим и к использованию трех случайных величин (и ваш метод действительно ломается при $\pmb \xi = \alpha \mathbf x$).
Зато не применим для четырехмерного пространства, но в нем я тоже не могу придумать, как обойтись генерацией трех величин.

[arseniiv]

Если я не ошибся в идее и реализации идеи, вектору с координатами $(a,b,c,d)$ в некотором ортонормированном базисе ортогональны, как и друг другу, и векторы $(b,-a,d,-c)$, $(c,-d,-a,b)$, $(-d,-c,b,a)$. Ну и потом умножаем их, если они все единичные, на три случайные координаты; тут читерство с использованием базиса выглядит для меня не так уж страшно. Аналогично для других чётных размерностей.

[Andrey_Kireew]

Генерируется равномерно распределённый вектор.
$\xi \sim U(-\pi,\pi]^{n-1}$
потом:
$\rho_1=cos(\xi_1)$,
$\rho_2=cos(\xi_2)sin(\xi_1)$,
$\rho_3=cos(\xi_3)sin(\xi_2)sin(\xi_1)$,
и т.д., т.е. из полярной системы переходим в декартову.

Потом наращиваем размерность из условия:

$$\begin{pmatrix} \rho_0 \\ \rho \end{pmatrix}\cdot v=0,$$

т.е. находим неизвестную компоненту $\rho_0$.
Уже потом можно нормировать.

Так, отсеивать ничего не придётся.

[venco]

И получится неравномерное распределение.