Операции с матрицами

[Aarnikotka]

Добрый день!

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

Задача:
Дана матрица $X$ размера $m$ на $n$. Данную матрицу необходимо разделить на две $X_1$ и $X_2$, количество строк в первой $j$, во второй $k=m-j$ соответственно. Множества строк $j$ и $k$ не пересекаются.

Пусть матрица $Z$ имеет размерность $1$ на $n$. Формула для каждого элемента $z_i$, $(i=1:n)$ будет следующей:

$z_i = \frac{\underset{j}{\sum} x^j_i}{\underset{k}{\sum} x^k_i}$, т.е. верхняя сумма, например, берется по всем элементам матрицы $X_1$ в $i$-ом столбце.

Нужно подобрать $j$ и $k$ таким образом, чтобы выборочная дисперсия была минимальна: $D(Z) \to \min$

Сейчас пытаюсь привести это все к какой-нибудь задаче оптимизации. Буду признателен за любую возможную помощь. Перебор работает пока $m$ или $j$ невелики.

[ИСН]

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

[patzer2097]

Aarnikotka в сообщении #1018150 писал(а):

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

Хорошего точного решения придумать и не удастся, если, конечно Вы запрещаете случаи $j=0$ и $k=0$ Действительно, Ваша задача остается NP-сложной, даже если Вас интересуют только матрицы из нулей и единиц и устраивает только случай $DZ=0$. Что касается приближенных алгоритмов, вряд ли они кем-то разрабатывались специально для такой задачи; поэтому можно попробовать свести ее к какой-нибудь известной задаче и применить известные для нее алгоритмы. Впрочем, никаких иллюзий по поводу скорости таких алгоритмов и качества приближения быть не должно

[Aarnikotka]

Спасибо за комментарии! А если посмотреть на эту задачу под другим углом: делить матрицы по принципу корреляции строк (сумм нескольких строк)? Так как данные из реальной жизни, при суммирование строк корреляция между суммами достигает значений более 0,9 (закон больших чисел?). Единственная проблема - даже с такой корреляцией коэффициент вариации может быть высоким (или, наоборот, низким). Все зависит, судя по всему, от коэффициента смещения в уравнении $y=a x + b$, где $x$ это одна сумма, а $y$ - другая. Возможно ли как-то устремить коэффициент смещения к нулю при суммировании строк по коэффициенту корреляции (Пирсона)?

-- 22.05.2015, 10:06 --

Или же в этом случае в регрессионной модели $y=a x + b_{\min}+\varepsilon$ все наши махинации с уменьшением $b$ уйдут в увеличение дисперсии $\varepsilon$?

[ИСН]

Ваш вопрос сродни тому, на каком километре дороги тут будет заправка или Макдональдс. А по дороге-то и не ездил никто сроду; это вообще не дорога, это направление.
Пробовать надо.