getch

Спасибо, посмотрел книгу. Срезюмировав: Не совсем понял, что вы хотели сказать своим постом. Если задать норму вектор-столбца, как сумму квадратов разниц соседних элементов, то, вроде, задача сводится к нахождению вектора, индуцирующего матричную норму. Но как приведенные выше свойства индуцированной матричной нормы помогут решить задачу? Я запомнил данный Вами замечательный итерационный алгоритм нахождения собственного вектора, соответствующего максимальному собственному значению матрицы. Поэтому данная ранее перефломулировка задачи через матрицу A = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) видится наиболее оптимальной на данный момент.

Матрица сдвига, конечно, получается огромной - NxN (N - количество элементов в исходном векторе Vi). Т.е. ее для перемножения использовать совсем нерезонно на практике. Проще алгоритмом сразу. Спасибо, задача теперь решена полностью. В выкладках заинтересовал такой нюанс, что если бы использовалась не матрица-сдвига, а матрица любого преобразования, то все равно не потребовалось бы ее искать. Достаточно лишь знать алгоритм преобразования. Выходит, эксплуатируется какое-то фундаментальное свойство, что любое преобразование можно задать умножением на соответствующую матрицу. Не очевидно совсем.

Если переписать матрицу A следующим образом: A = V'*V - V'*S*V -V'*S'*V + V'*S'*S*V = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) то S-матрица-сдвига будет присутствовать только в виде (S*V), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме. Скажите, нет ли ошибки в таких рассуждениях?

Спасибо за подробный ответ! Подскажите, как выглядит матрица сдвига в данном случае? Вместо нее делал бы сдвиг индексов в самом алгоритме, но в выражении ниже ее надо и транспонировать и другое. Т.е. без явного вида не представляю, как обойтись. Жирным шрифтом подправил неточности. k - собственный вектор матрицы A, соответствующий максимальному собственному значению матрицы A. Правильно ли понимаю, что для такого решения условия равенства нулю суммы элементов каждого исходного вектора Vi, а также единичной длины искомого вектора-стобца k не обязательны?

Да, вектора относительно удобные для мат. аппарата, которым, к сожалению, владею крайне слабо. Поэтому и прошу помощи.

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

Только максимизировать надо не саму сумму векторов, а определенную выше функцию F от этой суммы - F(K1 * V1 + ... + Kn * Vn). F - сумма модулей (или квадратов) разностей соседних элементов вектора.

Это произведение числа на вектор: Ki - вещественные числа. Vi - вектора. V[j] - j-й элемент вектора V.

Приветствую всех! На данном форуме мне очень здорово когда-то помогли в решении некоторых задач. Поэтому решил еще раз обратиться к уважаемому сообществу с просьбой дать дельный совет/рекомендации, как подступиться к решению такой задачи: Определена такая функция для любого вектора: F(V) = Sum(Abs(V[j] - V[j + 1])) , либо F(V) = Sum((V[j] - V[j + 1])^2)) Даны одинаковой размерности вектора V1, V2, ..., Vn, у каждого из которых сумма его элементов равна нулю. Нужно найти вектор NewV = K1 * V1 + K2 * V2 + ... + Kn * Vn, где Sum(Abs(Ki)) = 1, либо Sum(Ki^2) = 1 значение F(NewV) которого было бы максимальным. У меня есть гипотеза, что всегда верно неравенство F(NewV) <= max(F(V1), F(V1), ...., F(Vn)), т.е. решением задачи является вектор коэффициентов, где один элемент равен ±единице, а остальные - нули. Возможно, кому-то известно решение схожей или частного случая этой задачи. Спасибо.

Существует итерационный алгоритм расчета СКО сдвинутого окна через СКО окна до сдвига. Нормировка делается через деление фрагмента на его почти бесплатно полученное СКО. При этом Среднее каждого фрагмента обнулять не требуется при сравнении. Надо лишь один раз отнормировать сам шаблон (что ищется) к СКО = 1 и Ср. = 0.

Алгоритмическая сложность такого метода "лобовая" - O(N^2). Быстрая корреляция через БПФ значительно эффективнее - O(N * log(N)).

Листинг программы на C++ (N - любое)

Поискал в интернете схожие задачи. Выкладываю ссылки, возможно, кому-то пригодятся: Контурный анализ. Видео создания шаблона. Видео нахождения шаблона(-ов). Обнаружение устойчивых признаков изображения: метод SURF. «Выглядит похоже». Как работает перцептивный хэш. Алгоритм быстрого нахождения похожих изображений. Презентация «Поиск изображений. Методы индексирования изображений. Методы на основе хэш-функций. Обучение метрик. Фильтры объектов для классификации и поиска изображений.» (из курса лекций Введение в компьютерное зрение) Блог Распознавание образов для программистов. Тематические реализации (поисковики): Поиск изображений по исходному изображению. Распознавание шрифта по картинке. Поиск песни по ритму. Поиск песни по аудио-образцу. Поиск песни по напеву.

На другом форуме есть очень схожая по задаче тема: Распознавание звукового сигнала (звука) по образцам. Привожу цитату одного поста оттуда: Т.е. предлагаются альтернативные корреляции варианты, а также упоминается возможность значительного уменьшения признаков сравнения. Кто-нибудь использовал отличные от корреляционного методы или занимался уменьшением признаков сравнения? У меня корреляция через оптимизированный (насколько мог) БПФ считается, к сожалению, не так быстро, как хотелось бы.

Да, с каждым новом шаблоном нужно считать корреляцию во всем множестве точек исходного сигнала. И тут есть две ситуации: 1. Меняется только шаблон, сигнал - нет. Тогда БПФ сигнала делать повторно не требуется при расчете корреляции. Делается только прямое БПФ шаблона и обратное БПФ. 2. Меняется и шаблон и сигнал (добавляется один отсчет). Вот тут и хочу БПФ сигнала с новым отсчетом получить из ранее посчитанного БПФ сигнала без этого отсчета.