2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Быстрый поиск дискретного максимума довольно спец функции
Сообщение15.11.2022, 15:58 
 i  Ende
Исправлена опечатка в формуле.

Добрый день,

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

Итак, сама задача:

Имеется симметричная не отрицательно определенная малоранговая матрица
$$A \in {\mathBB R}^{N \times N}, ~~ A = \{a_{ij}\}, ~~ A = C C^T, ~~ C \in {\mathBB R}^{N \times K}, ~~ K<<N$$
причем каждая строка $C$ нормирована на единицу, то есть $\forall i \ne j: ~~ a_{ij}<1$ и $\forall i: ~~ a_{ii}=1$,
и имеется вектор $b \in {\mathBB}R^N, ~~ b = \{ b_i\}$, мне надо найти максимум по всем индексам вида
$$\max_{i,j} \frac{b_i^2 + b_j^2 - 2 b_i b_j a_{ij}}{1 - a_{ij}^2}.$$

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

Для ранга 1 и 2 исходной матрицы все можно решить линейно, но совершенно не понятно как это все обобщить на произвольный ранг. В моем случае ранг матрицы $A$ обычно равен около 10, а размерность ($N=10^3 - 10^4$), то есть если найти какое-то решение, то можно сильно ускорить поиск.

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

Вдруг у кого-то будут идеи в какую сторону посмотреть, пожалуйста, посоветуйте!

Спасибо!

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение15.11.2022, 16:49 
ilghiz в сообщении #1570069 писал(а):
максимум по всем индексам вида
$$\min_{i,j} \frac{b_i^2 + b_j^2 - 2 b_i b_j a_{ij}}{1 - a_{ij}^2}.$$


Так max или min? ))

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение15.11.2022, 17:22 
Ой, да, максимум, спасибо, что заметили! Жалко, что уже нельзя отредактировать мое исходное сообщение.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение15.11.2022, 22:19 
ilghiz в сообщении #1570082 писал(а):
Ой, да, максимум, спасибо, что заметили! Жалко, что уже нельзя отредактировать мое исходное сообщение.
Я отредактировал.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение15.11.2022, 23:57 
Ende в сообщении #1570123 писал(а):
Я отредактировал.

Спасибо!

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 11:44 
Аватара пользователя
Что-то мне захотелось переписать оптимизируемую функцию в виде $\frac {(b_i-b_j)^2} {1-a_{i,j}^2}+b_i b_j$. Но что потом - возможно, что лишь показалась польза от такой записи.
И по $b_i$ и $a_{i.j}$ - они положительны, или знак произволен?
Ну и касательно матрицы A - известна матрица C, из которой она получена? Или только ранг задан?

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 13:58 
Спасибо Евгений Машеров, за интересные вопросы!

А разве такая запись будет эквивалентна? Там вроде бы $\displaystyle\frac{(b_i-b_j)^2} {1-a_{i,j}^2}+\frac{2 b_i b_j}{1+a_{ij}}$ должно получиться. Но вроде тоже не помогает.

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

На самом деле исходная постановка:
$$\min_x ||C^T x-q||~~~ (1)$$
причем в $x$ разрешено иметь только два ненулевых элемента - то есть классический компрессед сенсинг метод. Отсюда получается, что $A = CC^T$. Для простоты и устойчивости строки $C$ можно нормировать, а мой вектор $b = Cq$. Моя формула (1) получается после упрощения той, что я записал в исходном сообщении.

Также все можно преобразовать так, чтобы $|a_{i.j}| \le 1$, $b_i \le 1$ но знак тут не определен.

Часто даже $C$ бывает плохо обусловленной, то есть обычное явление, когда матрица $A$ имеет ранг 10, и размерность $10^4 \times 10^4$.

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

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 14:01 
 i  ilghiz
Чтобы обратиться к участнику, кликните мышкой на его ник. Тогда он скопируется вместе с болдом и цветом, вот так: Евгений Машеров. А самое главное - участник увидит в разделе "Упоминания", что его упомянули, и прочтет Ваше сообщение.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 15:08 
Ende в сообщении #1570188 писал(а):
 i  ilghiz
Чтобы обратиться к участнику, кликните мышкой на его ник. Тогда он скопируется вместе с болдом и цветом, вот так: Евгений Машеров. А самое главное - участник увидит в разделе "Упоминания", что его упомянули, и прочтет Ваше сообщение.

Спасибо! Обычно у меня получалось, но этот раз задумался, и не пометил тек как надо.

Обычно если хочется обратиться, и, одновременно процитировать, стандартных средств для этого нет, приходится вначале цитировать, а потом ручками дорисовывать теги, ято я впопыхах и не сделал.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 15:13 
ilghiz в сообщении #1570195 писал(а):
Обычно если хочется обратиться, и, одновременно процитировать, стандартных средств для этого нет
Цитата сама по себе считается обращением (и видна в упоминаниях), упоминать при этом еще и ник излишне.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 15:31 
Ende в сообщении #1570197 писал(а):
ilghiz в сообщении #1570195 писал(а):
Обычно если хочется обратиться, и, одновременно процитировать, стандартных средств для этого нет
Цитата сама по себе считается обращением (и видна в упоминаниях), упоминать при этом еще и ник излишне.

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

То есть я бы вместо этого написал бы так:

Спасибо Ende за советы!
Ende в сообщении #1570197 писал(а):
Цитата сама по себе считается обращением (и видна в упоминаниях), упоминать при этом еще и ник излишне.

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

Эх бы теперь по сути исходной проблемы такую же дискуссию!

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 16:03 
Аватара пользователя
Столкнись я с такой задачей на практике, решал бы через пошаговую регрессию.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение16.11.2022, 17:52 
Евгений Машеров в сообщении #1570203 писал(а):
Столкнись я с такой задачей на практике, решал бы через пошаговую регрессию.

Спасибо большое за ответ! Пожалуйста, можно спросить, а как именно, что именно делать в виде регрессии? Я просто идеи не понял что именно Вы советуете... Спасибо!

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение17.11.2022, 08:33 
Аватара пользователя
Я бы вообще не связывался с матрицей A в явном виде. Работал бы непосредственно с
$\min_x ||C^T x-q||$
Алгоритм прост
https://en.wikipedia.org/wiki/Stepwise_regression
Есть у Себера описание. Отличие от обычной процедуры пошаговой - не по F-критерию число регрессоров определяем, или там по Акайке, а ограничиваемся двумя.

 
 
 
 Re: Быстрый поиск дискретного максимума довольно спец функции
Сообщение17.11.2022, 14:09 
Евгений Машеров в сообщении #1570260 писал(а):

Спасибо большое! Теперь понял, что имеется ввиду. Я как раз от аналогичных не детерминистических методов хотел отказаться и решать задачу детерминистическим методом, так как у меня всего-то два ненулевых параметра в регрессии и мне не надо угадывать два их, или больше, или меньше.

То есть у меня арифметическая сложность квадратична от числа строк в матрице, но она детерминирована.

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

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group