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

[ilghiz]

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$, а потом наоборот и так несколько раз. Обычно такой метод довольно быстро сходится за несколько итераций, но я не могу доказать, что он всегда будет сходится, и предполагаю, что можно построить контрпримеры, когда он будет находить не максимум, а что-то близкое.

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

Спасибо!

[ozheredov]

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? ))

[ilghiz]

Ой, да, максимум, спасибо, что заметили! Жалко, что уже нельзя отредактировать мое исходное сообщение.

[Ende]

ilghiz в сообщении #1570082 писал(а):

Ой, да, максимум, спасибо, что заметили! Жалко, что уже нельзя отредактировать мое исходное сообщение.

Я отредактировал.

[ilghiz]

Ende в сообщении #1570123 писал(а):

Я отредактировал.

Спасибо!

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

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

[ilghiz]

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

А разве такая запись будет эквивалентна? Там вроде бы $\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$ нельзя, но как раз к этому значению-то и хочется приблизиться.

[Ende]

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

[ilghiz]

Ende в сообщении #1570188 писал(а):

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

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

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

[Ende]

ilghiz в сообщении #1570195 писал(а):

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

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

[ilghiz]

Ende в сообщении #1570197 писал(а):

ilghiz в сообщении #1570195 писал(а):

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

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

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

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

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

Ende в сообщении #1570197 писал(а):

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

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

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

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

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

[ilghiz]

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

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

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

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

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

[ilghiz]

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

https://en.wikipedia.org/wiki/Stepwise_regression

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

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

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