Строго говоря, «случайная проекция» не является проекцией?

Текущие реализации алгоритма случайного Проекционного уменьшить размерность выборок данных путем сопоставления их с к с использованием проекции матрицы , элементы которой являются IID из подходящего распределения (например , из ):$\mathbb R^d$$\mathbb R^k$$d\times k$$R$$\mathcal N(0,1)$

$x^\prime = \frac{1}{\sqrt k}xR$

Удобно, что существуют теоретические доказательства, показывающие, что это отображение приблизительно сохраняет попарные расстояния.

Однако недавно я нашел эти заметки, где автор утверждает, что это отображение со случайной матрицей не является проекцией в строгом линейном алгебраическом смысле этого слова (стр. 6). Из приведенных там объяснений это объясняется тем, что столбцы не являются строго ортогональными, когда его элементы независимо выбираются из . Следовательно, более ранние версии RP, в которых была применена ортогональность столбцов можно рассматривать как проекцию.$R$$\mathcal N(0,1)$$R$

Можете ли вы дать более подробное объяснение: (1) каково определение проекции в этом строгом смысле и (2) почему RP не является проекцией согласно этому определению ?.

1. Каково определение проекции в этом строгом (линейном алгебраическом) смысле (слова)

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

   В линейной алгебры и функционального анализа, проекция есть линейное преобразование из векторного пространства в себя, что . То есть всякий раз, когда применяется дважды к любому значению, он дает тот же результат, как если бы он был применен один раз (идемпотент).$P$$P^2 = P$$P$

   Для ортогональной или векторной проекции

   https://en.wikipedia.org/wiki/Projection_(linear_algebra)

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

2. Почему RP не является проекцией по этому определению?

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

   В-третьих, если бы случайные векторы были точно ортогональными (как они были на самом деле в исходных конструкциях JL), то мы имели бы, что проекция JL была ортогональной проекцией

   ...

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

   ...

   это «достаточно хорошо».

   Таким образом, вы можете сделать, в принципе, случайную проекцию с другой конструкцией, которая ограничена ортогональными матрицами (хотя это и не нужно). Смотрите, например, оригинальную работу:

   Джонсон, Уильям Б. и Йорам Линденштраус. «Расширения липшицевых отображений в гильбертово пространство». Современная математика 26.189-206 (1984): 1.

   ... если случайным образом ортогональную проекцию ранга на$k$$l_2^n$

   ...

   Чтобы сделать это более точным, пусть будет проекцией на первые координат и пусть будет нормализованной мерой Хаара на , ортогональной группе на . Тогда случайная величина определяемая как определяет понятие «случайной проекции ранга ».$Q$$k$$l_2^n$$\sigma$$O(n)$$l_2^n$

   $$f: (O(n), \sigma) \to L(l_2^n)$$ $$f(u) = U^\star Q U$$ $k$

   Запись в Википедии описывает случайную проекцию таким образом (то же самое упоминается в примечаниях к лекциям на страницах 10 и 11).

   https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

   Первая строка - это случайный единичный вектор, равномерно выбранный из . Вторая строка представляет собой случайный единичный вектор из пространства, ортогонального первой строке, третья строка представляет собой случайный единичный вектор из пространства, ортогонального первым двум строкам, и так далее.$S^{d − 1}$

   Но вы обычно не получаете эту ортогональность, когда вы берете все элементы матрицы в матрице случайными и независимыми переменными с нормальным распределением (как Уубер упомянул в своем комментарии с очень простым следствием), если бы столбцы были всегда ортогональны, их записи могли бы не быть независимым ").

   Матрица и произведение в случае ортонормированных столбцов можно рассматривать как проекцию, поскольку она относится к матрице проекции . Это немного похоже на обычную регрессию наименьших квадратов в качестве проекции. Произведение не является проекцией, но дает координату в другом базисном векторе. «Реальная» проекция - это , а матрица проекции - .$R$$P = R^TR$$b = R^T x$$x' = Rb = R^TRx$$R^TR$

   Матрица проекции должна быть тождественным оператором в подпространстве которое является диапазоном проекции (см. Свойства, упомянутые на странице википедии). Или иначе сказал, что он должен иметь собственные значения 1 и 0, так что подпространство, для которого он является единичной матрицей, является диапазоном собственных векторов, связанных с собственными значениями 1. Со случайными элементами матрицы вы не получите это свойство. Это второй пункт в лекционных заметках$P=R^TR$$U$

   ... он во многих отношениях "выглядит как" ортогональная матрица ... является равномерно распределенным подпространством ... но собственные значения не находятся в .$range(P^T P)$$\lbrace 0, 1 \rbrace$

   ^{обратите внимание, что в этой цитате матрица относится к матрице в вопросе, а не к матрице проекции которая подразумевается матрицей$P$$R$$P = R^TR$$R$}

   Таким образом, случайная проекция с помощью различных конструкций, таких как использование случайных элементов в матрице, не совсем равна ортогональной проекции. Но это вычислительно проще и, по словам Майкла Махони, «достаточно хорошо».

Правильно: «случайная проекция», строго говоря, не является проекцией.

Проектируется четко определен математический объект: https://en.wikipedia.org/wiki/Projection_(linear_algebra) - это линейный оператор idempotentent, то есть линейный оператор такой , что . Применение проекции дважды - это то же самое, что применение ее только один раз, потому что после проецирования точки на подпространство она должна просто оставаться там, если проецируется снова. В этом определении нет ничего об ортогональности; на самом деле, проекция может быть косой (см. Википедия).$P$$P^2 = P$

Обратите внимание, что только квадратные матрицы могут представлять «проекции» в этом смысле. «Случайные проекции» использует случайный матрице с , поэтому он не может быть проекцией в смысле приведенного выше определение.$d\times k$$R$$k\ll d$

Даже если вы сделаете столбцы ортонормированными (например, применив процесс Грамма-Шмидта), этот аргумент все равно будет применяться. Кто-то недавно задал этот вопрос о PCA: что именно следует называть «проекционной матрицей» в контексте PCA? - a матрица ортонормированных собственных векторов, строго говоря, также не является проекцией.$R$$d\times k$$U$

Я думаю, что ключом здесь является рассмотрение пространства столбцов матрицы RP как подпространства, на которое мы выполняем проекцию. В общем, независимо от того, являются ли столбцы ортогональными, можно спроецировать образец на пространство столбцов используя следующее уравнение [1]:$d\times k$$R$$R$$x\in \mathbb R^d$$R$

$p = xR(R^TR)^{-1}R^T$ , где .$p\in\mathbb R^d$

Если, как и в более старых версиях или RP, столбцы матрицы ограничены ортонормированными, то и, следовательно, проекция на пространство столбцов будет выглядеть так :$R$$R^TR = I\in \mathbb R^{k\times k}$$x$$R$

$p = xRR^T$ , с ,$p\in\mathbb R^d$

и становится матрицу проекции , потому что квадратные и .$RR^T\in\mathbb R^{d\times d}$$(RR^T)^2=RR^TRR^T=RR^T$

Возможно, утверждение о том, что более ранняя версия Random Projection (где столбцы были ортонормированными) на самом деле является проекцией, относится к тому факту, что в этом случае вложение вниз в и последующее восстановление обратно в образца заданного , действительно является проекцией на пространство столбцов , а является проекционной матрицей .$R$$\mathbb R^k$$\mathbb R^d$$x\in\mathbb R^d$$xRR^T$$R$$RR^T$

Я был бы признателен, если бы вы могли подтвердить / исправить мои рассуждения здесь.

Ссылка:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projection.pdf

Если вы используете перевычисляемый случайный переворот или перестановку знаков перед быстрым преобразованием Уолша-Адамара, случайная проекция будет ортогональной.