Разреженное преобразование Уолша-Адамара

15

Преобразование Уолша-Адамара (WHT) является обобщением преобразования Фурье и представляет собой ортогональное преобразование для вектора действительных или комплексных чисел размерности . Преобразование популярно в квантовых вычислениях, но недавно оно было изучено как своего рода предварительное условие для случайных проекций многомерных векторов для использования при доказательстве леммы Джонсона-Линденштраусса. Его главная особенность заключается в том, что, хотя это квадратная матрица d × d , она может быть применена к вектору за время O ( d log d ) (а не d 2 ) методом, подобным FFT.dзнак равно2мd×dО(dжурналd)d2

Предположим, что входной вектор является разреженным : он имеет только несколько ненулевых элементов (скажем, ). Есть ли способ вычислить WHT за время f ( r , d ) так , чтобы f ( d , d ) = O ( d log d ) и f ( r , d ) = o ( d log d ) для r = o ( dр«dе(р,d)е(d,d)знак равноО(dжурналd)е(р,d)знак равноо(dжурналd) ?рзнак равноо(d)

Примечание: эти требования являются лишь одним из способов формализовать идею, что я хотел бы что-то, что работает быстрее, чем для малых r .dжурналdр

Суреш Венкат
источник
Я уверен, что вам известны следующие два простых наблюдения, но в любом случае я запишу их для других читателей: (1) Простое умножение дает время O (rd). Это лучше, чем O (d log d), только когда r = o (log d). (2) Даже если входной вектор является разреженным, выходной в целом не является разреженным. Это означает, что мы не можем надеяться, что f (r, d) будет o (d) даже при r = 1.
Цуёси Ито
4
Вы знаете, что ответ на тот же вопрос для преобразования Фурье?
Робин Котари
Tsuyoshi: да, я знаю (1), и это на самом деле то, что делается для приложений, которым это нужно. что касается (2), это также верно. Робин, это хороший момент - я ничего не знаю о FT, и на самом деле это может быть хорошим местом для начала копать.
Суреш Венкат
Оказывается, я должен был копаться в Википедии. на странице БПФ упоминаются две статьи, которые могут быть связаны с проблемой разреженных вычислений.
Суреш Венкат

Ответы:

6

Индексируйте строки WHT целым числом x, для . Таким образом, х имеет лог D бит. Аналогично, индексировать столбцы. (Х, у) положение ( - 1 ) х , у 0Икс<d(-1)Икс,Y где показатель является скалярным произведением лог длины д. Предположим, что r является степенью 2, округляя при необходимости. Разбейте матрицу dxr на блоки rxr, изменяя первые log r биты и фиксируя другие log (d / r) биты в каждом из d / r путей. Этот блок rxr представляет собой меньшую матрицу WHT размера r, за исключением того, что некоторые столбцы могут отсутствовать, повторяться или отменяться. В любом случае, предварительно обработайте вектор легко, затем выполните rxr WHT за время r log r, затем повторите d / r раз для общего времени d log r.

Пример:

д = 4.

ЧТО Н

++++
+-+-
++--
+--+

Произвольный набор столбцов - 00 и 10 (крайний левый и два над ним):

++
++
+-
+-

Блоки строк

++
++

и

--
--

В каждом блоке есть повторяющиеся столбцы, пропущенные столбцы и во втором блоке отрицательные столбцы. Предварительно обработать вектор в ( a + b , 0 ) T и умножить на 2x2 WHT:(a,б)T(a+б,0)T

++
+-

Затем препроцесс в ( -(a,б)T(-a-б,0)T

++
+-
Мартин Штраус
источник