Ортогональные базисы k-значных логик

[sofa_mathematician]

Какие существуют ортогональные базисы k-значных логик, кроме дискретного преобразования Фурье, дискретного преобразования Хартли, дискретного преобразования Виленкина — Крестенсона и прочих обобщений дискретного преобразования Фурье?

Постановка задачи: имеется ряд полученных в результате вычислений квадратных матриц ${k \times k\,, ~k \in \mathbb{N}\,,}$ неотрицательных целых значений от 0 включительно до k-1 включительно. Иными словами, имеется ряд таблиц значений функции k-значной логики от 2-х аргументов. При этом ${k \neq 2^n}$ во всех случаях, кроме 2-х тривиальных: $k = 2\,,~k = 8\,.$ А также k является (большим) составным числом во всех нетривиальных случаях.

Кроме того, для каждой строки и для каждого столбца любой матрицы заведомо выполнены 3 условия: каждое значение от 0 до k-1 встречается ровно 1 раз; строки не повторяются; столбцы не повторяются. Я хочу получить несложные аналитические формулы для каждой функции k-значной логики от 2-х аргументов. По крайней мере, графические визуализации в виде картинок размером ${k \times k}$ в градациях серого явно показывают, что это не шумы.

Преобразование Уолша — Адамара не интересует, т.к. хорошо подходит только для ${k = 2^n}$ . "Идеальный" ортогональный базис должен являть собою что-то вроде нумеруемого набора правил перестановки элементов строки значений k-значной логики. По k-значной логике читал первые 2 главы книги: Яблонский С.В. Введение в дискретную математику (2003).djvu , но там ничего нет о примерах ортогональных базисов, если я правильно понял прочитанное.

Также в результате поисков в интернете наткнулся на теорему "каждая функция k-значной логики задается полиномом по модулю k тогда и только тогда, когда k — простое число". Данный вариант меня также заинтересовал. Но у меня во всех нетривиальных случаях k заведомо является составным числом.

Прошу подтолкнуть меня в нужном направлении (русскоязычные/англоязычные научные статьи/книги) по всем возможным вариантам.

[Xaositect]

Мне кажется, у Вас некоторая путаница в терминологии. Что Вы называете ортогональным базисом $k$-значной логики? Я как-то не понимаю, как связать дискретное преобразование Фурье с $k$-значной логикой.

[sofa_mathematician]

Xaositect в сообщении #1095541 писал(а):

Мне кажется, у Вас некоторая путаница в терминологии. Что Вы называете ортогональным базисом $k$-значной логики?

Базис, являющийся полным, т.е. позволяющий представить что угодно из k-значных функций посредством суммирования (или умножения, если без него никак) его базисных элементов по модулю k. Но в силу большого значения k я бы хотел иметь нумерацию базисных столбцов, подобно преобразованию Уолша — Адамара, но для k-значной логики. Т.е., как я писал в корневом сообщении, "идеальный" ортогональный базис должен являть собою что-то вроде нумеруемого набора правил перестановки элементов строки значений k-значной логики. Вот я и хотел узнать, существуют ли какие-либо стандартные ортогональные базисы k-значных логик.

Приведу самый простой пример для 3-ичной логики (хоть в моей задаче её и нет) от 2 аргументов:

0 1 2
1 2 0
2 0 1

Я смогу представить любую матрицу ${3 \times 3}$ неотрицательных целых значений от 0 включительно до 2 включительно в виде суммы базовых строк/столбцов по модулю k. При этом положение значений базисного элемента определяется его порядковым номером: очевидное смещение по модулю суммы номеров строки и столбца. Т.е. я "не трачу" коэффициенты на сам базис, расход памяти O(1).

Цитата:

Я как-то не понимаю, как связать дискретное преобразование Фурье с $k$-значной логикой.

Косвенно. Приведу в минимальной степени изменённую цитату из книги Основы теории дискретных сигналов на конечных интервалах 1975 года:

Если значения дискретного сигнала s(x) являются равноотстоящими, то выбрав соответствующий масштаб, их можно приравнять числам 0 ... k-1
...
В обычной линейной теории дискретных сигналов их также представляют в виде линейной комбинации базисных дискретных экспоненциальных функций (ДЭФ):

$s(x) = \sum_{z=0}^{k-1} \Big\{ S(z) \cdot e^{\frac{-2 \pi i x}{k} \cdot z} \Big\} $

Т.е., имея действительно- или комплексно- значную функцию, можно набор из k комплексных равноотстоящих значений абсолютно точно разложить на k гармоник с комплексными коэффициентами. Для этого нужно произвести ДПФ — поставить коэффициент 1/k, под суммой должен быть сигнал вместо спектра, а у экспоненты должен быть знак минус. При этом набор гармоник являет собой k-значный базис. При этом в общем случае не происходит сжатия информации, если сигнал не имеет синусоидальной природы (а также есть ещё некоторые ограничения). Т.е. все или почти все коэффициенты будут не равны 0.

Но у меня имеются функции k-значной логики от 2 аргументов. Здесь также почти не будет 0-х коэффициентов, в силу специфики моей задачи (см. 3 условия в корневом сообщении). Поэтому я хочу "угадать" такой базис, в котором:

1) существует детерминированный способ определения его элементов;
2) задана нумерация его базисных элементов.

Конечная цель: имея $k^2$ элементов, "заархивировать" информацию о них, используя O(k) коэффициентов. Но для этого нужно угадать "красивый" базис, если таковые вообще существуют... И разложение по нему должно иметь определённую структуру, сжимающую информацию.

Вот я и интересуюсь всевозможными достижениями человечества на предмет существующих "красивых" базисов k-значных логик.

[sofa_mathematician]

Ладно. Радикально упрощу свой вопрос. Какие существуют ортогональные базисы, принципиально не содержащие экспонент/тригонометрических функций?

[Brukvalub]

sofa_mathematician в сообщении #1127940 писал(а):

Радикально упрощу свой вопрос. Какие существуют ортогональные базисы, принципиально не содержащие экспонент/тригонометрических функций?

Базисы где?

[sofa_mathematician]

Brukvalub в сообщении #1128007 писал(а):

sofa_mathematician в сообщении #1127940 писал(а):

Радикально упрощу свой вопрос. Какие существуют ортогональные базисы, принципиально не содержащие экспонент/тригонометрических функций?

Базисы где?

Да чёрт возьми, ну неужели я так непонятно объясняю!? Вот есть у меня сигнал. Я взял и разложил его в ряд Фурье. Это экспоненты, тригонометрия, ну я не знаю, откройте любой учебник по мат. анализу или тригонометрии. Представил его в виде суммы сигналов разных частот sin/cos.

Мой сигнал явно имеет не тригонометрическую и не экспоненциальную природу. Я спрашиваю, существует ли ещё хоть что-нибудь хоть где-нибудь? Где? Хоть на Марсе, хоть на Луне, хоть в Гильбертовом пространстве.

[Brukvalub]

sofa_mathematician в сообщении #1128053 писал(а):

Да чёрт возьми, ну неужели я так непонятно объясняю!? Вот есть у меня сигнал. Я взял и разложил его в ряд Фурье. Это экспоненты, тригонометрия, ну я не знаю, откройте любой учебник по мат. анализу или тригонометрии.

Назовите тот учебник по тригонометрии, который мне следует открыть, чтобы понять ваше объяснение.

sofa_mathematician в сообщении #1128053 писал(а):

Мой сигнал явно имеет не тригонометрическую и не экспоненциальную природу.

Поясните, как именно природа вашего сигнала мешает разложить его в ряд Фурье.

sofa_mathematician в сообщении #1128053 писал(а):

Я спрашиваю, существует ли ещё хоть что-нибудь хоть где-нибудь?

Да, существует. Много чего и много где.

sofa_mathematician в сообщении #1128053 писал(а):

Где? Хоть на Марсе, хоть на Луне, хоть в Гильбертовом пространстве.

Многое есть на Марсе, многое, но меньше, чем на Марсе, есть на Луне, еще кое-что есть в Гильбертовом пространстве.

[sofa_mathematician]

>Поясните, как именно природа вашего сигнала мешает разложить его в ряд Фурье.
Никак. Просто данное изложение малоинформативно. Поясню ещё раз: разложение хорошо, если оно например может передать $n^2$ значений с помощью n коэффициентов (остальные равны 0). Таким образом, получается сжатие информации в n раз. В случае ряда Фурье для моего сигнала равны 0 не более чем $3/4$ коэффициентов, это вообще не сжатие при n стремящемся к бесконечности.

>Да, существует. Много чего и много где.
Анекдот про математика под деревом.

>еще кое-что есть в Гильбертовом пространстве
Жду-не дождусь примеров/ключевых слов.

[Brukvalub]

(Оффтоп)

Вы сначала разучитесь хамить в ответ на разумный вопрос, а уж потом чего-то там ждите.

[sofa_mathematician]

Brukvalub в сообщении #1128138 писал(а):

(Оффтоп)

Вы сначала разучитесь хамить в ответ на разумный вопрос, а уж потом чего-то там ждите.

Во-первых, не вижу хамства со своей стороны, во-вторых, вопросы сформулировал настолько ясно, насколько смог.

[Brukvalub]

(Оффтоп)

Издевательским хамством выглядит ваше мне, лектору мехмата МГУ, который раз в два года читает студентам, в том числе, и теорию рядов и интегралов Фурье, предложение почитать учебник по тригонометрии, хамским же выглядит в ответ на мой уточняющий вопрос ваше требование рассказать "существует ли ещё хоть что-нибудь хоть где-нибудь?", хамским выглядят и выкрики "Где? Хоть на Марсе, хоть на Луне".
Раз вы притворяетесь, что не понимаете сути хамства, то остается порекомендовать вам посещать курсы изящных манер, где учат вести себя вежливо.

По сути: ортогональные базисы бывают в Евклидовых пространствах, например, в конечномерных пространствах, в пространствах многочленов, в пространствах квадратично суммируемых функций и т.п. Более того, с помощью процесса ортогонализации Грама-Шмидта любой базис в Евклидовом пр-ве можно превратить в ортогональный. Поэтому без уточнения ваш вопрос

sofa_mathematician в сообщении #1127940 писал(а):

Какие существуют ортогональные базисы, принципиально не содержащие экспонент/тригонометрических функций?

выглядит необъятно-бессмысленным.

[iifat]

Таки к тому ж не понимаю, почему вы ожидаете экономии места. Множество интересующих вас матриц существенно меньше полного, да, но уж больно, на первый взгляд, прихотливо устроено. Сомнительно мне, что переход к другому базису позволит сильно сэкономить. Ну да, можно не хранить одну из строк и один из столбцов, так что матрица $3\times3$ будет задаваться четырьмя числами вместо девяти — но, во-первых, это не имеет отношения к базисам, а во-вторых — при бОльших размерностях экономия стремится к нулю.

[sofa_mathematician]

(Оффтоп)

>Brukvalub
Я отвечаю любому человеку одинаково вне зависимости от его регалий, смотрю только на буквы в его сообщении.

>По сути: ортогональные базисы бывают в Евклидовых пространствах, например, в конечномерных пространствах, в пространствах многочленов, в пространствах квадратично суммируемых функций и т.п. Более того, с помощью процесса ортогонализации Грама-Шмидта любой базис в Евклидовом пр-ве можно превратить в ортогональный. Поэтому без уточнения ваш вопрос выглядит необъятно-бессмысленным.

Не выглядит, если мне захотят помочь. Кроме того, я не понимаю общие ответы. Мне бы на примерах. Я могу разложить по sin/cos (экспоненты), но там всё плохо. Мог бы разложить по Уолшу-Адамару 1/-1 (тоже по сути экспоненты), если бы количество элементов было $2^n$, но увы.

Т.е. ничего кроме этого я не знаю. И мне нужны примеры, литература, всё что угодно, но не формулировки вида "уточните вопрос". Если бы я мог его уточнить, велика вероятность, что данная тема не была бы создана. Как я могу уточнить то, о чём я уже несколько лет не то, что ничего не знаю, и нагуглить-то не могу сам? Знакомых математиков у меня нет, и общие формулировки для меня (СУБЪЕКТИВНО) выглядят куда большим хамством, выражаясь Вашим языком (но на самом деле я не считаю это хамством).

iifat в сообщении #1128213 писал(а):

Таки к тому ж не понимаю, почему вы ожидаете экономии места. Множество интересующих вас матриц существенно меньше полного, да, но уж больно, на первый взгляд, прихотливо устроено. Сомнительно мне, что переход к другому базису позволит сильно сэкономить. Ну да, можно не хранить одну из строк и один из столбцов, так что матрица $3\times3$ будет задаваться четырьмя числами вместо девяти — но, во-первых, это не имеет отношения к базисам, а во-вторых — при бОльших размерностях экономия стремится к нулю.

Совершенно резонный вопрос, ведь в общем случае должен быть тот же объём информации. Потому что визуализация исходного ряда полученных в результате вычислений квадратных матриц ${k \times k\,, ~k \in \mathbb{N}\,,}$ воспринимается моим мозгом как совершенно неслучайная картина, описывающаяся не более чем $k + \operatorname{const}$ чисел. Даже если я не прав, я полагаю, можно меня хотя бы познакомить с основными существующими базисами, чтобы я проверил своё предположение и успокоился.

В очередной раз повторюсь, что имею наглость рассчитывать на экономию в (корень от общего количества элементов) раз.