Сингулярное разложение и "самое слабое звено"

[Combat Zone]

B@R5uk
Ваш последний пост слабо связан с первым. Тут уже высказывали пожелание, я его повторю. Пока вы не поставите задачу - в данный момент она просто не сформулирована - можно фантазировать до одури. С любым результатом.

Так какова ваша задача? Что вы делаете?

[B@R5uk]

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

Свет на ситуацию пролила бы теорема, которая бы давала ограничения в виде неравенств на то, какими станут (как сильно изменятся) сингулярные значения у матрицы A, если в ней занулить/вычеркнуть одну или несколько строк. Поэтому вопрос: кто-нибудь знает какую-нибудь теорему в этом духе?

Решил подойти к этой проблеме численно в самом простейшем случае: алгоритмом Нелдера-Мида подбираю матрицу 3x3 с фиксированным числом обусловленности так, чтобы в матрице, получаемой вычёркиванием/занулением строки, исправленное число обусловленности было максимально (худший случай) или минимально (лучший). Матрица A ищется как сингулярное разложение специального вида

$$A=U\Sigma,\qquad\qquad\Sigma=\left(\begin{matrix}p&0&0\\0&s&0\\0&0&1\end{matrix}\right),\qquad\qquad 1\le s\le p$$

Здесь U — это матрица общего вращения 3-мерного пространства, сингулярное число p фиксировано и задаёт число обусловленности исходной матрицы A, а сингулярное число s вместе с матрицей вращения подбирается алгоритмом. Матрицу V сингулярного разложения общего вида я положил равной единичной матрице, потому что она не на что не влияет при занулении строк, зато уменьшается число оптимизируемых параметров. Код алгоритма ниже.

Файл find_worst_case_3d.m. Знак переменной m задаёт что ищется — наилучший (минус) или наихудший случай:

Используется синтаксис Matlab M

%   dxdy.ru/topic160345-15.html
%   B@R5uk, 2025, May

clc
clearvars
format compact
%format long
format short

p = 3;
m = -1;

run_flag = 1;
while run_flag
    w0 = randn (1, 3);
    w0 = w0 / sqrt (sum (w0 .^ 2));
    w0 = w0 * rand ^ (1 / 3);
    w0 = 2 * pi * [rand, w0];

    fmso = optimset ('fminsearch');
    fmso = optimset (fmso, 'Display', 'off', 'TolFun', 1e-17, 'TolX', 1e-17, ...
        'MaxIter', 20000, 'MaxFunEvals', 10000);
    w = fminsearch (@(w) m * find_worst_case_3d_func (w, p), w0, fmso);
    a = build_matrix_3d (w, p);
    b = a;
    b ([1 5 9]) = 0;
    if 0.01 < sum (abs (b (:)))
        run_flag = 0;
    end
end
a

[u s v] = svd (a)
b = a;
b (3, :) = 0;
disp (' ')
[uu ss vv] = svd (b)
disp (' ')
disp (ss (1) / ss (5))
 

Файл find_worst_case_3d_func.m:

Используется синтаксис Matlab M

function res = find_worst_case_3d_func (w, p)

a = build_matrix_3d (w, p);
a (3, :) = 0;
s = svd (a);
res = s (2) / s (1);

end
 

Файл build_matrix_3d.m:

Используется синтаксис Matlab M

function a = build_matrix_3d (w, p)

u = rotation_matrix_3d (w (2 : 4));
s = 1 + (p - 1) * acos (cos (w (1))) / pi;
s = diag ([p s 1]);
a =u * s;

end
 

Файл rotation_matrix_3d.m:

Используется синтаксис Matlab M

function mat = rotation_matrix_3d (vector)

if isequal ([1 3], size (vector))
    vector = vector';
elseif ~isequal ([3 1], size (vector))
    error ('Input must be 3-element vector')
end
v_len = sqrt (sum (vector .^ 2));
if 0 == v_len
    mat = eye (3);
else
    vector = vector / v_len;
    cl = cos (v_len);
    mat = cl * eye (3) + (1 - cl) * vector * vector' + sin (v_len) * ...
        [0 -vector(3) vector(2);vector(3) 0 -vector(1);-vector(2) vector(1) 0];
end

end
 

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

Тем не менее, не смотря на эту оговорку получаются интересные результаты. Например, алгоритм ни разу не выдал 3x3 матрицу, после вычёркивания строки в которой число обусловленности ухудшилось. Сразу возникает гипотеза: при вычёркивании строк матрицы её число обусловленности может только улучшаться. Это явно претендует на роль важной теоремы или хотя бы призывает найти контр-пример. Получающиеся матрицы имеют довольно интересный специальный вид (2-х типов), но он не так важен, как сама гипотеза.

(Оффтоп)

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

Далее, другими интересными результатами являются случаи, когда результирующая матрица имеет минимально возможное число обусловленности. Оно, очевидно, будет 1, так как не сложно привести пример:

$$A=\left(\begin{matrix}10&0&0\\0&10&0\\0&0&1\end{matrix}\right)$$

в котором при вычёркивании последней строки число обусловленности улучшается с 10 до 1. Но интерес представляет вопрос, в каких ещё случаях такое происходит. И программа такие интересные случаи находит. Все эти случаи характеризуются двумя фактами:

1. среднее сингулярное значение s может быть произвольным,
2. в удаляемой строке в матрице U в столбце, соответствующему этому сингулярному значению, стоит 0
3. элемент матрицы U в удаляемой строке в последнем столбце может быть как больше других элементов столбца (по модулю), так и меньше.

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

Чтобы пролить ещё чуть-чуть света на проблему, я думаю провернуть точно такой же эксперимент для матриц 4x4. Но пока застопорился на поиске формулы для матрицы поворота общего вида в 4-мерном пространстве. Я знаю, что там 6 степеней свободы, и видел кой-какие формулы, но они мне не нравятся из-за сложности и/или непонятности и/или отсутствия неограниченности параметров. Формула должна удовлетворять условиям непрерывности от оптимизируемых параметров, быть более-менее хорошо обусловленной для всех областей параметров и не иметь ограничений на параметры в виде неравенств. В этом случае алгоритм численной оптимизации будет иметь значительно меньше проблем со сходимостью и вырожденностью области значений при его рассмотрении как оператора нелинейного проектирования.

Combat Zone, озвучил в этом посте два вопроса, которые меня сейчас больше всего интересуют. Первый вопрос — в цитате в начале поста (с идущей далее попыткой его численного решения в частном случае, второй — выделенная жирным гипотеза ближе к концу поста. Буду очень благодарен, если поможете в решении и/или посоветуете литературу/статьи, где эти два вопроса обсуждаются. Извиняюсь, что вам приходится читать весь мой поток сознания, выражение мысли письменно помогает мне лучше разобраться в вопросе.

[zgemm]

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

Свет на ситуацию пролила бы теорема, которая бы давала ограничения в виде неравенств на то, какими станут (как сильно изменятся) сингулярные значения у матрицы A, если в ней занулить/вычеркнуть одну или несколько строк. Поэтому вопрос: кто-нибудь знает какую-нибудь теорему в этом духе?

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

То есть смысл этого всего - не правильно в этом направлении думать. Я не спорю, что может что-то и есть лучше rank-revealing, но я видел в начале 2000 битвы на US и EU конференциях и симпозиумах на тему ранк-ревеалинга, а с того момента ничего в мире не появилось, то есть вероятность того, что скоро что-то лучше появится - стремиться к нулю.

[Combat Zone]

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

Тем не менее, не смотря на эту оговорку получаются интересные результаты. Например, алгоритм ни разу не выдал 3x3 матрицу, после вычёркивания строки в которой число обусловленности ухудшилось. Сразу возникает гипотеза: при вычёркивании строк матрицы её число обусловленности может только улучшаться. Это явно претендует на роль важной теоремы или хотя бы призывает найти контр-пример. Получающиеся матрицы имеют довольно интересный специальный вид (2-х типов), но он не так важен, как сама гипотеза.

Погуглите Cauchy's interlacing theorem. Из нее следует, что число обусловленности при вашей процедуре не увеличивается.

[Combat Zone]

Combat Zone в сообщении #1685681 писал(а):

Погуглите Cauchy's interlacing theorem. Из нее следует, что число обусловленности при вашей процедуре не увеличивается.

Прошу прощения, не уменьшается. упс

[B@R5uk]

Combat Zone, большое спасибо! Это, судя по всему, что надо. Я правильно понимаю, что Poincare separation theorem и Cauchy's interlacing theorem — это всё из одной оперы? В чём основное различие, что у них разные названия? Какое устоявшееся название у этих теорем на русском? Единственную межязыковую связь, что я нашёл, — это английская статься вики Min-max theorem, содержащая упоминание о теореме Коши, ссылается на отечественную статью Теорема Куранта-Фишера, но обе статьи в целом совсем про другое. В какой отечественной литературе есть детальное обсуждение этих теорем (и, возможно, истории)?

Из ссылок на английскую я пока нашёл Gene H. Golub, Charles F. Van Loan - Matrix computations (1996, 3rd ed) и Richard Bellman - Introduction to matrix analysis (1987, 2nd ed). Судя по оглавлению, первая занимается вычислительными вопросами матриц, вторая — применением линейной алгебры к оптимизации и решению ДУ и многое другое (даже не знаю, где искать мой вопрос). Первая представляет интерес для меня сама по себе, во второй надо разбираться.

-- 12.05.2025, 08:26 --

Combat Zone в сообщении #1685685 писал(а):

Прошу прощения, не уменьшается.

Нет, изначально правильно было написано: число обусловленности не увеличивается (численный эксперимент именно это подтверждает, откуда и вопрос вылез). Большие числа обусловленности — это плохо, самое лучшее — это когда число обусловленности равно 1 (матрица с одной строкой/столбцом имеет именно это число обусловленности).

[Combat Zone]

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

Нет, изначально правильно было написано: число обусловленности не увеличивается

Да, вы правы. Я нынче не в форме, увы.
Максимальное собственное значение может стать меньше, минимальное может стать больше. А могут и не стать. Отношение не увеличится.

Для вас картинка, для наглядности. https://disk.yandex.ru/i/VXgGQRKDofbR5g
Позаимствована из чужой презентации.

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

Я правильно понимаю, что Poincare separation theorem и Cauchy's interlacing theorem — это всё из одной оперы? В чём основное различие, что у них разные названия?

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

-- 12.05.2025, 07:52 --

Что касается другого вашего вопроса (не того, который в цитате, на него отвечает теорема, а того, который в стартовом посте), то так и неясно, чего вы хотите. Если оставить только линейно независимые - то это одно. Это задача найти базис в подпространстве, порожденном вашими векторами, и даже если этот базис строить только на данных строках - задача имеет не единственное решение. Тут уже говорили. Что если первая строка является линейной комбинацией двух других, то и третья будет линейной комбинацией двух оставшихся. Возня с числами обусловленности тут не очень понятна, что число обусловленности 4, что CI= 7, это примерно одинаково хорошо, потому пока не ясны цели этой возни, ничего посоветовать невозможно.

-- 12.05.2025, 08:17 --

Как-то по-русски редко попадается даже на российских сайтах, и обычно звучит как Теорема Пуанкаре/Коши о перемежаемости.

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

В переводе "Симметрическая проблема собственных значений" Парлетт именуется теоремой Коши.

[B@R5uk]

Евгений Машеров, эпиграф к введению про волны — это нечто! Большое СПАСИБО за книгу. Численные методы — всегда в мою аллею, почитаю обязательно.

[B@R5uk]

Теорема (Коши о чередовании собственных значений). Пусть Q — это симметричная матрица с размерами m, собственные числа которой:

$$\lambda_1\ge\lambda_2\ge\ldots\ge\lambda_m$$

Пусть Q' — это главная подматрица матрицы Q размера m ‒ k (то есть матрица, полученная удалением одних и тех же строк и столбцов в количестве k) с собственными значениями

$$\mu_1\ge\mu_2\ge\ldots\ge\mu_{m-k}$$

Тогда выполнено:

$$\lambda_l\ge\mu_l\ge\lambda_{l+k},\qquad 1\le l\le m-k$$

К моему вопросу про изменение числа обусловленности она применяется следующим образом.

Пусть у матрицы A экономное сингулярное разложение (то есть без "лишних" нулевых столбцов в матрице Σ и без зануляемых ими столбцов в матрице V) и сингулярные числа следующие:

$$A=U\Sigma V^T,\qquad UU^T=U^TU=V^TV=I_m$$

$$A\in\mathbb{R}^{m\times n},\qquad U,\Sigma,I_m\in\mathbb{R}^{m\times m},\qquad V\in\mathbb{R}^{n\times m},\qquad m\le n$$

$$\Sigma=\operatorname{diag}\lBig(\sigma_1,\sigma_2,\ldots,\sigma_m\rBig),\qquad\qquad\sigma_1\ge\sigma_2\ge\ldots\ge\sigma_m$$

Пусть матрица A' получается из матрицы A удалением k строк. Тогда её можно представить как произведение матриц выше (уже не являющееся сингулярным разложением) и через её собственное разложение (с новыми сингулярными числами):

$$A'=U_{\text{red}}\Sigma V^T,\qquad U_{\text{red}}U_{\text{red}}^T=I_{m-k},\qquad U_{\text{red}}\in\mathbb{R}^{(m-k)\times m},\qquad 0<k<m$$

$$A'=U'\Sigma'V'^T,\qquad U'^TU'=U'U'^T=V'^TV'=I_{m-k}$$

$$A'\in\mathbb{R}^{(m-k)\times n},\qquad U',\Sigma'\in\mathbb{R}^{(m-k)\times(m-k)},\qquad V'\in\mathbb{R}^{n\times(m-k)}$$

$$\Sigma'=\operatorname{diag}\lBig(\tau_1,\tau_2,\ldots,\tau_{m-k}\rBig),\qquad\qquad\tau_1\ge\tau_2\ge\ldots\ge\tau_{m-k}$$

Здесь $U_{\text{red}}$ — это матрица, полученная из U удалением тех же строк, что и при удалении из матрицы A для получения A'. Составим из матриц A и A' новые матрицы Q и Q', соответственно:

$$Q=AA^T=U\Sigma V^TV\Sigma^TU^T=U\Sigma^2U^T$$

$$Q'=A'A'^T=U_{\text{red}}\Sigma V^TV\Sigma^TU_{\text{red}}^T=U_{\text{red}}\Sigma^2U_{\text{red}}^T$$

$$Q'=A'A'^T=U'\Sigma'V'^T'V'\Sigma'^TU'^T=U'\Sigma'^2U'^T$$

Видно, что полученные матрицы являются симметричными, а из первого и второго выражений так же видно, что матрица Q' является главной подматрицей матрицы Q. По этому, к ним применима теорема Коши выше. Более, того, собственные значения матриц Q и Q' являются квадратами сингулярных чисел матриц A и A' соответственно. Используя эти два факта и, опуская квадраты, получаем неравенства:

$$\sigma_l\ge\tau_l\ge\sigma_{l+k},\qquad 1\le l\le m-k$$

Далее, запишем отношение чисел обусловленности и применим неравенства:

$$\frac{\kappa(A)}{\kappa(A')}=\frac{\sigma_1}{\sigma_m}\frac{\tau_{m-k}}{\tau_1}=\frac{\sigma_1}{\tau_1}\frac{\tau_{m-k}}{\sigma_m}\ge 1$$

$$\kappa(A)\ge\kappa(A')\ge 1$$

То есть, с удалением строк число обусловленности матрицы не возрастает, что и требовалось доказать. (Надеюсь, нигде не очепятался, тут за размерами и коэффициентами следить — чёрт ногу сломит, не смотря на то, что ничего такого особого в выводе нет).

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

$$\sigma_1=\sigma_2>\sigma_3=\sigma_4>0$$

Я подозреваю, что у любой матрицы 3 на 3, у которой число обусловленности отлично от 1, всегда найдётся строка, удаление которой это число обусловленности уменьшит. Я так же подозреваю, что доказательство этого факта должно быть как-то завязано на размерность, но даже не представляю, с какой стороны подойти. Кто-нибудь, подскажите, пожалуйста?