Найти матрицу наименее отклоняющуюся от данного набора.

[Смит]

Заголовок по причине своей краткости не совсем точен.

Задача стоит так:
Для заданного набора (вообще говоря прямоугольных) матриц A_k,\ k=1,\dots,N требуется построить из столбцов матриц A_k матрицу B такую, что \sum_{l=1}^{N}\|A_l-B\|_F минимально.

я "залип" и у меня совсем нет идей, как к задаче подступиться.

[Brukvalub]

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

[Смит]

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

Еще эта задача есть и в более сильной постановке, а именно, матрица B не обязана состоять из столбцов матриц A_k. В этом случае не получается применять даже перебор.

[незваный гость]

Простите мне серость, а что за норма $\| \cdot \|_F$? Это тоже самое, что $\| \cdot \|_p$ ($p = F$), или что-то другое?

[Смит]

нет, это несколько другое.
http://mathworld.wolfram.com/FrobeniusNorm.html

[Brukvalub]

Смит писал(а):

Еще эта задача есть и в более сильной постановке, а именно, матрицаB не обязана состоять из столбцов матриц A_k. В этом случае не получается применять даже перебор.

А почему бы в этом случае не применить стандартную технику исследования функции многих переменных на экстремум?

[Смит]

Хорошая идея, как то сразу не догадался. Пойду попробую.