Основы преобразования Уолша-Адамара
- Практическое преобразование Уолша-Адамара в терамасштабе(arXiv)
Автор: Йи Лу
Аннотация: В середине второго десятилетия нового тысячелетия развитие ИТ достигло беспрецедентно новых высот. Как одна из производных закона Мура, операционная система эволюционирует от первоначальных 16-битных, 32-битных, до окончательных 64-битных. Большинство современных вычислительных платформ находятся в процессе перехода на 64-битные версии. В ближайшие десятилетия ИТ-индустрия неизбежно будет отдавать предпочтение программному обеспечению и системам, которые могут эффективно использовать новые 64-разрядные аппаратные ресурсы. В частности, с появлением массивных выходных данных на регулярной основе, программное обеспечение и системы с эффективным использованием памяти будут лидировать в будущем. В этой статье мы стремимся изучить практическое преобразование Уолша-Адамара (WHT). WHT популярен в различных приложениях, связанных с кодированием изображений и видео, обработкой речи, сжатием данных, проектированием цифровой логики, коммуникациями, и это лишь некоторые из них. Мощь и простота WHT стимулировали исследовательские усилия и интерес к (шумному) разреженному WHT в междисциплинарных областях, включая (но не ограничиваясь) обработку сигналов, криптографию. Грубо говоря, разреженный WHT относится к случаю, когда количество ненулевых коэффициентов Уолша намного меньше размерности; зашумленная версия разреженного WHT относится к случаю, когда количество больших коэффициентов Уолша намного меньше, чем размерность, в то время как существует большое количество малых ненулевых коэффициентов Уолша. Ясно, что общее преобразование Уолша-Адамара является первым решением зашумленного разреженного WHT, которое может получить все коэффициенты Уолша, превышающие заданный порог, и позиции индекса. В этой работе мы изучаем эффективные реализации общего ВТП очень большой размерности. Считается, что наша работа проливает свет на шумный разреженный WHT, который остается большой открытой проблемой. Между тем, основная идея поможет изучить параллельные вычисления с интенсивным использованием данных, которые имеют широкий спектр приложений.△ Меньше
2.Почти оптимальный детерминированный алгоритм для разреженного преобразования Уолша-Адамара(arXiv)
Автор :Махди Черагчи, Петр Индик
Аннотация: Для каждой фиксированной константы α›0 мы разрабатываем алгоритм вычисления k-разреженного преобразования Уолша-Адамара N-мерного вектора x∈RN за время k1+α(logN)O( 1). В частности, алгоритму предоставляется запрос на доступ к x, и он вычисляет k-разреженное x~∈RN, удовлетворяющее ∥x~−x^∥1≤c∥x^−Hk(x^)∥1, для абсолютной константы c›0 , где x^ — преобразование x, а Hk(x^) — его наилучшее k-разреженное приближение. Наш алгоритм полностью детерминирован и использует только неадаптивные запросы к x (т. е. все запросы определяются и выполняются параллельно при запуске алгоритма). Важным техническим инструментом, который мы используем, является конструкция почти оптимальных и линейных конденсаторов без потерь, которая представляет собой точную реализацию конденсатора GUV (Guruswami, Umans, Vadhan, JACM 2009). Кроме того, мы разрабатываем детерминированную и неадаптивную схему ℓ1/ℓ1 сжатого зондирования на основе общих конденсаторов без потерь, которая оснащена алгоритмом быстрой реконструкции, работающим за время k1+α(logN)O(1) (для конденсатора на основе GUV) и представляет самостоятельный интерес. Наша схема значительно упрощает и совершенствует более раннюю конструкцию на основе экспандеров Беринде, Гилберта, Индика, Карлоффа, Штрауса (Аллертон 2008). В наших методах используются линейные конденсаторы без потерь по типу «черного ящика»; следовательно, любое будущее улучшение явных конструкций таких конденсаторов немедленно приведет к улучшению параметров в нашей структуре (что потенциально приведет к времени реконструкции k(logN)O(1) с уменьшенным показателем в полилогарифмическом множителе и устранению дополнительного параметра а). Наконец, если разрешить алгоритму использовать случайность, но при этом использовать неадаптивные запросы, время работы алгоритма можно сократить до O~(klog3N).
3.Регистрация изображений мозга с использованием быстрого преобразования Уолша-Адамара(arXiv)
Автор:Д. Сасикала, Р. Неелавени
Аннотация: было разработано множество методов регистрации изображений, которые имеют большое значение для анализа данных в медицине, астрофотографии, спутниковой съемке и некоторых других областях. В данной работе предлагается метод регистрации медицинских изображений с использованием быстрого преобразования Уолша-Адамара. Этот алгоритм регистрирует изображения одной и той же или разных модальностей. Каждый бит изображения удлиняется с точки зрения базисных функций быстрого Уолша-Адамара. Каждая базисная функция представляет собой понятие определения различных аспектов локальной структуры, например, горизонтального ребра, угла и т. д. Эти коэффициенты нормализуются и используются в качестве числительных в выбранной системе счисления, что позволяет сформировать уникальное число для каждого типа локальной структуры. . Экспериментальные результаты показывают, что быстрое преобразование Уолша-Адамара дает лучшие результаты, чем обычное преобразование Уолша во временной области. Кроме того, быстрое преобразование Уолша-Адамара более надежно при регистрации медицинских изображений и занимает меньше времени.
