Быстрый поиск дискретного максимума довольно спец функции

[Евгений Машеров]

Ну, мне представляется простая процедура. Матрица C рассматривается, как совокупность n регрессоров, из которых надо выбрать 2 лучших. Строим n парных регрессий q на $c_{i,*}$, выбираем наилучшую по минимуму суммы квадратов отклонений (не по R). Затем считаем остатки от этой регрессии, строим регрессию их на те же регрессоры, выбираем второй.

[ilghiz]

Евгений Машеров в сообщении #1570312 писал(а):

Ну, мне представляется простая процедура. Матрица $C$ рассматривается, как совокупность $n$ регрессоров, из которых надо выбрать 2 лучших. Строим $n$ парных регрессий $q$ на $c_{i,*}$, выбираем наилучшую по минимуму суммы квадратов отклонений (не по R). Затем считаем остатки от этой регрессии, строим регрессию их на те же регрессоры, выбираем второй.

Спасибо за ответ!

Так ведь не всегда будет работать (если я конечно правильно Вас понял).

Вот пусть у нас матрица $C$ состоит из дискретных векторов, которые мы получили от дискретизации гауссовых функций на отрезке $[0,n]$, причем ширина каждой такой функции существенно больше единицы. Тогда если в качестве $q$ у нас была сумма $i+1$ и $i-1$ гауссов, то наилучшей по минимуму суммы квадратов будет не один из них, а $i$, а остатком будет уже что-то совсем подальше, обычно $i+2$ или $i-2$, то есть вместо того, чтобы получить $i+1$ и $i-1$ мы получим $i$ и $i+2$, c очень не правильными весами, так как вес $i$ будетт почти равен весу суммы $i+1$ и $i-1$.

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

[Евгений Машеров]

Ну, если задача представить q суммой двух гауссианов - может быть, вообще не морочиться с матрицами, а использовать нелинейную регрессию? Скажем, Левенберга-Марквардта, подбирая параметры гауссианов?

[ilghiz]

Спасибо большое, Евгений Машеров за советы!

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

У меня почти всегда две соседние функции очень близки друг к другу, грубо говоря их скалярное произведение примерно равно 0.99 (сами функции нормированы на единицу). Но также для каждой функции есть еще несколько функций (не соседних!!!) скалярное произведение которых тоже близко к 0.99. Отсортировать в линейный список по близости друг к другу нельзя, там по физике это или 2Д или 3Д объект. Вернее конечно отсортировать-то можно, но все равно с каким-то шагом остаются тоже очень близкие в смысле скалярного произведения функции.

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

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

[Евгений Машеров]

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

[B@R5uk]

ilghiz, я правильно понимаю, что в матрице C у вас количество базисных векторов существенно меньше, чем число координат в каждом из этих векторов?

-- 22.11.2022, 15:50 --

Если да, то в процессе поиска

$$\min\limits_X^{}||Y-CX||^2$$

вне зависимости от ограничений на X вас будут интересовать две величины

$$Y^TC;\quad C^TC$$

обе из которых вам так или иначе придётся посчитать, если вы хотите решить задачу честно. Однако, если ширина матрицы базисных векторов C много меньше её высоты, то в конечном итоге работы то вам делать придётся не так уж и много, потому что все суммирования по самому "длинному" индексу уже выполнены. Или вам и эту работу делать слишком затратно?

[ilghiz]

Спасибо большое, Евгений Машеров и B@R5uk за комментарии и советы!

B@R5uk в сообщении #1570954 писал(а):

ilghiz, я правильно понимаю, что в матрице C у вас количество базисных векторов существенно меньше, чем число координат в каждом из этих векторов?

не, наоборот!

B@R5uk в сообщении #1570954 писал(а):

Если да, то в процессе поиска

$$\min\limits_X^{}||Y-CX||^2$$

вне зависимости от ограничений на X вас будут интересовать две величины

$$Y^TC;\quad C^TC$$

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

да, верно, более того, в моем первом сообщении в этой ветке я обозначил

$$A = C^TC, ~~ b = Y^TC$$

и по началу специально не заострял внимание откуда взялись эти $A$ и $b$, чтобы не обсуждать наименшие квадраты. У нас с Вами кстати путаница в обозначении транспонированности матрицы $C$.

У меня есть память для $A$, у меня есть возможность изначально выполнить сколько угодно много предварительных операций, но вот потом у меня появляются векторы $Y$, и я хочу с минимальными затратами получать позиции ненулей в решении ($X$), и пытаюсь придумать что-то гарантированное, что могло бы максимально быстро решать такую задачу.

Исходная формула поиска максимума конечно позволяет на каждую пару $i,j$ выполнить ну очень немного арифметических операций, особенно если запоминать

$\displaystyle \frac{2a_{ij}}{1-a_{ij}^2}~~$ и $~~\displaystyle\frac{1}{1-a{ij}^2}$

но таких вычислений всяко надо сделать $\displaystyle\frac{N(N-1)}{2}$ и от этой асимптотики как раз и хотелось бы избавиться.

[B@R5uk]

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

Если бы у нас все базисные столбцы были ортогональны, то минимум бы доставляла та пара столбцов, которые имеют наибольшие (по модулю) скалярные произведения на столбец данных Y. То есть, для решения надо было бы посчитать N скалярных произведений и выбрать наибольшее по модулю и следующее по величине модуля. Так как у нас нет ортогональности, то для выбора первого наибольшего скалярного произведения придётся рассмотреть не только все базисные столбцы, но и все возможные нормированные разности базисных столбцов. Потому что каждая пара базисных столбцов задаёт двумерное пространство, таких пространств порядка $N^2$ и проекция вектора данных может оказаться наибольшей на любое из таких пространств (если, опять же, вам что-то хорошее про ваши базисные вектора не известно). Чтобы учесть проекции на эти пространства более полно необходимо рассматривать все возможные нормированные разностные столбцы.

У вас матрица C какого ранга, N? Линейно зависимых базисных столбцов нет? Если есть, то можно попытаться как-то это использовать. Хотя так на вскидку ничего не видится, кроме ускорения расчёта скалярных произведений.