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

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

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

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

Индексируйте строки WHT целым числом x, для . Таким образом, х имеет лог D бит. Аналогично, индексировать столбцы. (Х, у) положение ( - 1 ) ⟨ х , у $0 \le x \lt d$$(-1)^{\langle x,y \rangle}$ где показатель является скалярным произведением лог длины д. Предположим, что 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,b)^T$$(a+b,0)^T$

++
+-

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

++
+-