Вопрос по математике (к AVK прежде всего)

[KaraNagai]

Школьный вопрос можно сказать, но я что-то ответа хорошего придумать не могу:

1. Рассмотрим такой объект, как конечное множество векторов из некого Rn (ну n фиксировано и мало, скажем - 3), с числом элементов не более (но возможно менее) заданного N.

2. Рассмотрим далее множество W(n,N) всех таких объектов (для заданных n и N).

Вопрос: можно ли на этом W(n,N) так определить скалярное произведение, сумму, ноль и умножение на скаляр, чтобы в результате получилось inner product space?

[AVK]

Если честно, я не понял вопроса. Это у тебя множество зведообразных графов с конечным числом лучей, что ли? То бишь набор допустимых графов?

И что за inner product space? Inner product по-русски -- это скалярное произведение. Чтобы скал. произведение вводить, надо иметь точное описание множества, вообще-то. Но для любой структуры в R^n скалярное произведение просто наследовать можно из объемлющего линейного пространства -- тогда я просто понять не могу, в чем задача? Объясни подробнее.

[KaraNagai]

хм, если ты сделал какой-то вывод про графы, значит я явно облажался с формулировкой ;))

Итак, попытаюсь объяснить по пунктам подробнее как могу:

1. Дано n и N - два числа. Например n = 3, N = 10
2. Вектра - из R^n (в нашем примере - из R^3), любые: например (1,0,0), (-5.30, 12, -1000) и так далее.
3. Множества таких векторов - любые от пустого до множеств из N элементов (в нашем примере - из десяти элементов) максимум.
4. Нас интересует множество таких множеств, а конкретно:
5. Можно ли определить на нем ноль, операции сложения и умножения на скаляр, чтобы оно стало удовлетворять аксиомам векторного пространства
6. (и это самое главное, но без 5 некуда, похоже): можно ли и как (если можно) на таком векторном пространстве определить операцию скалярного произведения?

[AVK]

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

[AVK]

Сообщение от KaraNagai

1. Дано n и N - два числа. Например n = 3, N = 10
2. Вектра - из R^n (в нашем примере - из R^3), любые: например (1,0,0), (-5.30, 12, -1000) и так далее.
3. Множества таких векторов - любые от пустого до множеств из N элементов (в нашем примере - из десяти элементов) максимум.

Ну так вот набор таких векторов -- это граф-звезда с центром в начале координат. Ну или вещь вполне эквивалентная ему. С количеством лучей, не большим, чем N. Так что все вроде как правильно с моей изначальной интерпретацией, вроде как... Это просто кстати.

То бишь вопрос стоит о канонической процедуре введения векторного пространства на множестве графов... Хм... Лучше я завтра такой вопрос задам людям, что графами занимаются -- все едино заседание кафедры будет...

[KaraNagai]

Первое подозрение, что ответ отрицательный: где ты линейность по сложению возьмешь?

Это вопрос.

Ну с умножением на скаляр просто - умножаешь все вектора множества на этот скаляр.

А вот со сложением... ну скажем при сложении двух таких множеств каким-то однозначным образом выбирать складываемые пары векторов. При этом в бОльшем из множеств останутся невыбранные вектора - их просто засовывать в результат как есть. Вопрос только в том, как выбирать эти пары, чтобы условие линейности соблюдалось.

Ну так вот набор таких векторов -- это граф-звезда с центром в начале координат.

А ну можно и так посмотреть, хотя в этом случае координаты векторов будут лейблами вершин такого графа, и характеризоваться этот граф будет прежде всего не топологией, а этими лейблами (ну и количеством этих вершин). Я просто не думал, что подобными объектами теория графов занимается.

[AVK]

Наш народ ничего "готовенького" на эту тему не знает, так что спекулирую самостоятельно

Реально давай смотреть так: запишем N трехмерных векторов (столбцов) попросту в ряд (ну, друг рядом с другом). Если векторов меньше -- дополним нулевыми векторами до N штук. Получится матрица размера Nx3. теперь суммой двух таких агрегатов назовем сумму соответствующих матриц, ну а умножением на скаляр -- понятно, что.

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

Единственная проблема тут -- это то, что на исходном множестве векторов надо ввести упорядоченность, причем канонического способа это сделать, похоже, нету. Ну например, ты можешь нумеровать вектора по величине угла, образуемого вектором с осью какой-нибудь -- ясно, что таких способов великое множество.

Что касается скалярного произведения (точнее, его аналога), то тоже не видно канонического способа. Тем не менее, как вариант, можно попробовать взять что-нибудь такого сорта:

пусть A и B -- две такие матрицы, рассмотрим произведение
A B^t, где B^t -- транспонированная к B матрица.
Объект хорошо определен, будет матрицей размера 3 на 3. Теперь возьмем ее след. Ясно, что этот след линеен по каждому из двух элементов. То бишь кандидат на роль скалярного произведения готов.

По-видимому (хотя фиг знает) это построение тоже не будет каноническим ни в каком смысле.

Не уверен, что это то, что ты хотел, но что-то такого сорта сделать можно

[AVK]

В этой конструкции, впрочем, хорошо то, что невырожденность получается задаром.
Пусть tr (A A^t)=0. С другой точки зрения, довольно очевидно, что
A A^t будет симметричной положительно определенной матрицей, следовательно, она диагонализуется в собственном базисе к виду диагонали, составленной из ее собственных чисел, а след -- инвариант подобия. Т.е. этот след равен сумме трех неотрицательных собственных чисел матрицы A A^t, откуда следует, что все три собственных числа равны нулю и окончательно сама A нулевая.

Кроме того, тот же след будет, если, скажем, брать не
tr (A B^t),
а
tr (A^t B).
То бишь в этом смысле некий налет каноничности имеется

Дальше можно медитировать над вопросом: "а то ли это, что хотелось?"

[KaraNagai]

В этом подходе я вижу несколько проблем:

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

2. Каким образом отличать нулевые вектора от тех нулей, которым ты дополняешь матрицу до максимального размера? Впрочем это в моем случае не так важно, можно считать что в изначальных множествах нулевых векторов просто нет (их там и не будет).

3. Скалярное произведение, посчитанное таким образом, не будет отражать взаимного подобия векторов по-моему. То есть мне бы неплохо чтобы {(2,3), (1,2), (-1, -1)} умноженное на {(2,3), (-1, -1)} давало довольно большое значение, а в твоем случае все будет сильно зависить от порядка и конкретного набора векторов (насколько их подобие ложится на выбранный порядок). Или я ошибаюсь?

[AVK]

Сообщение от KaraNagai

В этом подходе я вижу несколько проблем:

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

2. Каким образом отличать нулевые вектора от тех нулей, которым ты дополняешь матрицу до максимального размера? Впрочем это в моем случае не так важно, можно считать что в изначальных множествах нулевых векторов просто нет (их там и не будет).

3. Скалярное произведение, посчитанное таким образом, не будет отражать взаимного подобия векторов по-моему. То есть мне бы неплохо чтобы {(2,3), (1,2), (-1, -1)} умноженное на {(2,3), (-1, -1)} давало довольно большое значение, а в твоем случае все будет сильно зависить от порядка и конкретного набора векторов (насколько их подобие ложится на выбранный порядок). Или я ошибаюсь?

1. Ага, ты прав. Это значит, что надо различать наборы векторов с разным порядков элементов в них. То есть ты различаешь геометрически одинаковые графы в зависимости от порядка нумерации их лучей. Вообще, отношение упорядоченности в этой задачи фиг знает, как вводить, сам же видишь...

2. А нулевой вектор и не надо отличать: нулевой вектор, по существу, вектор отсутствующий. В общем, просто вопринимать как особеность формализации.

3. Я не уверен, что можно разумнее как-то ввести скалярное произведение тут. Та конструкция, что я предложил, не с потолка взялась: это некое элементарное обобщение канонического способа введения гильбертовой структуре в линейном пространстве операторов класса Гильберта-Шмидта. Я вроде как сразу и не соображу, как еще вводить структуру гильбертова пространства на операторных классах...

Просто введение скалярного произведения на линейном пространстве означает появление эвклидовой (гильбертовой в общем случае) структуры, то бишь это ровно то, что ты хочешь: превратить свое множество в гильбертово пространство

[KaraNagai]

Это значит, что надо различать наборы векторов с разным порядков элементов в них.

Ага. А также допускать возможность, если так можно выразиться, членства вектора в наборе (к черту слово "множество" на данный момент) с кратностью > 1. Притом в моем случае и то и другое не имеет физического смысла.

2. А нулевой вектор и не надо отличать: нулевой вектор, по существу, вектор отсутствующий. В общем, просто вопринимать как особеность формализации.

хехех я бы назвал это проблемой "0 == null?". Кстати, я хорошо подумал, в моем случае нулевой вектор там может быть в одном из вариантов задачи.

Если быть чуть ближе к телу, то эти вектора - это центры "кластеров" цветов и частот (две разные задачи) вокруг какой-то окресности некоей точки на растровой картинке. Центры соответственно выраженные в частотных или цветовых координатах. А набор этих векторов - так называемая сигнатура (частотная или цветовая соответственно). Я больше про frequency domain думал, но в пространстве цветов нулевой вектор - это черный цвет. Который чисто теоретически может быть центром кластера если он широко представлен в рассматриваемой окрестности. Что, естественно, отличается от отсутвия нулевого вектора в наборе (что означает что черного цвета либо нет, либо центр кластера, к которому он пренадлежит приходится не на него самого, а на какой-то соседний цвет).

превратить свое множество в гильбертово пространство

Гильбертово пространство меня бы устроило. Но не любое, а определенными свойствами скалярного произведения, о которых я говорил раньше. Другое дело, необходимо ли мне чтобы оно соблюдало критерий гильбертова пространства - это я сказать не могу.

[AVK]

Сообщение от KaraNagai

Ага. А также допускать возможность, если так можно выразиться, членства вектора в наборе (к черту слово "множество" на данный момент) с кратностью > 1. Притом в моем случае и то и другое не имеет физического смысла.

Гильбертово пространство меня бы устроило. Но не любое, а определенными свойствами скалярного произведения, о которых я говорил раньше. Другое дело, необходимо ли мне чтобы оно соблюдало критерий гильбертова пространства - это я сказать не могу.

Я посмотрел, профакторизовать пространство тут, похоже, фиг получится. Значит, надо подбирать иную формализацию. Ты бы объяснил толком, зачем тебе структура произведения, тогда можно придумать че-нить более разумное.

Пп гильбертова пространства: собственно, введение скалярного произведения, удовлетворяющего аксиоматике, на линейном пространстве во всех случаях к нему приводит. Аксиоматику ты знаешь: линейность, однородность, невырожденность.

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

[KaraNagai]

Сорьки, AVK, я как-то выпал из обсуждения на время..

Итак:

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

Мне строго говоря нужна мера близости между этими структурами, притом такая, которая удолветовряла аксиомам скалярного произведения (и соответственно чтобы само пространство удовлетворяло аксиомом векторного пространства).

Зачем именно такая? Потому что это мне дает _автоматом_ сходимость определенного алгоритма к решению.

[AVK]

Ты _абсолютно_ уверен, что нужно именно скалярное произведение, и не хватит просто нормы? Или еще меньше -- метрики? Если в доказательстве ты используешь принцип сжимающих отображений (что обычно в таких задачках и делается), то тебе нужно только линейное метрическое пространство для этого...

Почему спрашиваю: введение структуры скалярного произведения -- это _чертовски_ сильное ограничение.

Пример: пространство суммируемых функций на отрезке -- нормированное, но скалярного произведения там быть не может. То же относится к суммируемым с любой степенью, большей 1, и _только_ в случае квадратично суммируемых функций допускает введение гильбертовой структуры.

В любом случае, попробую пораскинуть мозгой Ну, графы-то -- не мой хлеб, вообще говоря, а вот гильбертовы пространства -- енто как раз моя специализация Так что задачка интересная.

[KaraNagai]

Ты _абсолютно_ уверен, что нужно именно скалярное произведение, и не хватит просто нормы? Или еще меньше -- метрики?

Строго говоря нужна, как я сказал, kernel function, удовлетворяющая т.н. Mercer's condition (см. википедию).

Но любое скалярное произведение таковой функцией является, насколько я понимаю.

К сожалению, я доказательства как такового не помню. Видишь ли, проблема вроде как практическая.

То есть вообщем-то многие вообще смотрят на вопрос так: да хрен с ним с доказательством, работает на практике - и фиг бы с ним. К чему я тоже вообщем-то склоняюсь, но хорошо бы конечно если бы оно и в теории тоже работало ;)

введение структуры скалярного произведения -- это _чертовски_ сильное ограничение.

А разве нельзя ввести скалярное произведение при наличии метрики и нормы в векторном пространстве как (d(a,b)^2 - ||a||^2 - ||b||^2) / 2 ? Или я это чушь несу?