вопрос по линейной алгебре

[kobak]

Вопрос к друзьям-математикам. Пусть у нас есть вещественная симметричная положительно определенная билинейная форма S (т.е. попросту вещ. сим. пол. опр. матрица S; без ограничения общности можно считать, что диагональная с положительными значениями). Пусть есть такой базис V, состоящий из единичных, но не ортогональных, векторов (т.е. квадратная матрица V со всеми столбцами нормы 1), в котором S диагональна как билинейная форма, т.е. V^TSV — диагональная матрица. Верно ли, что trace(V^TSV) ≤ trace(S)? Как это доказать?

Предполагаю, что это должно быть либо очевидно (с правильной точки зрения), либо сразу следовать из какого-то стандартного результата, но я осел и никак не могу разобраться. Как говорит мой двухлетний сын — хилфэ! (Недавно, впрочем, начал говорить: «Папа, помогите!»)

Comments

[rus4.livejournal.com]

Верно, да. Через |f| обозначим норму вектора f.

Лемма 1. Пусть A --- симметричный положительный оператор, f - ненулевой вектор. Тогда (Af,f)*(A^{-1} f,f)\geq (f,f)^2.

Доказательство. Пусть A=B^2, где B тоже положителен, тогда надо доказать |Bf|*|B^{-1} f|\geq |f|^2, но по неравенству Коши-Буняковского |Bf|*|B^{-1} f| \geq(Bf, B^{-1} f)= (f,f), что и требовалось.

Лемма 2. Если у некоторой положительной симметричной матрицы на диагонали стоят единицы, то у обратной матрицы все диагональные элементы хотя бы 1.

Доказательство. Следует из леммы 1, примененной к базисным векторам.

Теперь пусть V^TSV=diag (c_1,...c_n). Тогда (SVe_i,Ve_j)= c_i delta(i,j), то есть Sf_i=c_i g_i, где f_i=Ve_i, g_i --- биортогональная система к (f_i). Обозначим g_i=\sum W_{ik} f_k, тогда умножая на f_j получаем, что матрицы W и F обратны, где F_{i,j}=(f_i,f_j) - матрица Грама для векторов единичных f_i. Применяя к матрице F лемму 2 получаем, что все диагональные элементы матрицы W хотя бы 1. Считая след матрицы S в базисе (f_i) получаем, что он равен \sum c_i W_{i,i}, что стало быть не меньше, чем \sum c_i=trace( V^TSV).

[kobak.livejournal.com]

Федя, спасибо огромное! Сижу разбираюсь с доказательством; вроде бы все понятно вплоть до последнего предложения, но вот его пока не понимаю: а почему след матрицы S в базисе (f_i) равен \sum c_i W_{i,i} ?

[rus4.livejournal.com]

ну потому что след это сумма диагональных элементов, то есть сумма(по i) коэффициентов при f_i в разложении Sf_i по базису (f_1,...,f_n)

[kobak.livejournal.com]

Действительно! Класс, спасибо. Локально теперь все понятно, глобально -- еще надо поразмыслить.

Я несколько дней назад задал этот вопрос на math.SE (http://math.stackexchange.com/questions/876801), впервые там зарегистрировавшись. Мне ничего путного не ответили. Вы, вроде бы, активно участвуете на mathoverflow; исходно я не решился туда писать, т.к. решил, что мой вопрос слишком элементарный (впрочем, я не очень понимаю, где проходит граница элементарности для mathoverflow). Как быть: мне самому ответить на свой вопрос на math.SE, сославшись на Вас? м.б., Вы захотите прямо там написать ответ? или же стоит попытаться перевести вопрос на mathoverflow (хоть и не знаю как), чтобы Вы на него ответили там?

[rus4.livejournal.com]

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

[kobak.livejournal.com]

Ага, так стало еще понятнее; спасибо! Я позволил себе исправить несколько теховских опечаток в Вашем ответе там. Про mathoverflow буду иметь в виду. Меня отпугнули грозные предупреждения про "research-level mathematics"; но я уже полистал вопросы и вижу, что там не только про схемы и стеки, попадается и обычная линейная алгебра.

[am.livejournal.com]

Предложеное док-во rus4, наверное, простейший путь. Краткий пересказ без ТеХа:
Доказывается что trace(D) ≤ trace(U'DU), диагон. D=V'SV, U - обратная к V.
trace(U'DU)=trace(UU'D)=сумма_по_всем_элем((UU').*D), где .* - поэлементное
произведение (Адамара). Т.е. неравенство следует из Леммы 2 rus4 для диагон.
элементов UU'=(V'V)^(-1).
Кстати, если дана полож. опред. симм. матрица в блочном виде:
A B
B' C
где A=1 скаляр, C тоже полож. опред. симм., то первый эл. обратной матрицы будет равен (A-BC^(-1)B')^(-1)>1 -- из преобр. Шура, или разложения Холецкого, см. например: http://www.cis.upenn.edu/~jean/schur-comp.pdf

[kobak.livejournal.com]

Ага, только в Вашем пересказе не сразу понятно, почему верна исходная посылка tr(S) = tr(U'DU). Это разве очевидно? По-моему, тут нужно вычисление tr(S) = tr(USV) = tr(SVU) = tr(U'V'SVU) = tr(U'DU), как у rus4 в его версии док-ва на math.SE (http://math.stackexchange.com/questions/876801).

[am.livejournal.com]

Ok. Если V квадратная и обратимая, то все проще: из V'SV=D следует S = U'DU, где U=V^(-1).

[kobak.livejournal.com]

И правда! Спасибо.

[kobak.livejournal.com]

А вот, кстати, зачем мне это понадобилось: http://stats.stackexchange.com/questions/67342/pca-lda-linear-discriminant-analysis-proportion-of-variance.

[am.livejournal.com]

Похожие вопросы обсуждаются в этой книге (http://gen.lib.rus.ec/book/index.php?md5=B501C2E8DB9CF4112062C635E0ACA2F2) на стр.106 и дальше.
(Кстати, здесь (http://stats.stackexchange.com/questions/8625/deriving-total-within-class-between-class-scatter-matrix) в формулах должно быть N_i вместо N).

[kobak.livejournal.com]

Ага. Ну это вообще много где обсуждается, но вот конкретно вопрос о сумме дисперсий проекций на всех дискриминантые оси (мой пункт 3 в ответе на SE), связанный с математическим вопросом, который я задал тут, -- этот вопрос я в литературе не встречал.

[am.livejournal.com]

Что касается Вашего неравенства, то мне кажется сейчас, что когда-то давно я подобное видел где-то в interior-point methods & ellipsoid methods (безотносительно к PCA, LDA, CCA) и методах проекционного градиента для QP-solvers. Так же, могло быть где-то в теории и практике матричных неравенств, т.к., например, любая линейная функция от симметричной матрицы X есть f(X)=tr(CX), (с симметричной C), а некоторые полезные в той теории функции бывают вида tr(V^TXV)... Есть еще Sylvester's law of inertia (http://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia) (c.f. Olga Taussky (https://www.math.wisc.edu/~hans/paper_archive/other_papers/hs057.pdf)), что имеет косвенное отношение.
Подобные и родственные вопросы рассмотрены подробно в главе 7: Horn and Johnson (1985) "Matrix Analysis".

[fainohino.livejournal.com]

Today was an extraordinary day, Clooney said There were millions of people that marched Б not just in Paris but around the world They were Christians and Jews and Muslims; they were leaders of countries all over the world And they didnБt march in protest Б they marched in support of the idea that we will not walk in fear Je suis Charlie In its unedited form, the 42-second film shows two masked gunmen в brothers Cherif and Said Kouachi в as they walk toward a prone police officer, later identified as 42-year-old Ahmed Merabet The standard would need approval from Congress, where lawmakers have struggled to come up with a way to replace a patchwork of differing state regulations БEven though much of the hospital equipment is no longer here, these special buildings are able to speak volumes, Б said Superintendent John Piltzecker of the Statue of Liberty National Monument and Ellis Island БThe National Park Service is pleased to work with Save Ellis Island in their efforts to bring visitors to the South Side to learn more about the island s unique story through this special tour programБ
http://huntingcoloradostyle.com/content/rhinocort-uk-gb-without-prescription-rhinocort-no-prescription-quick-delivery

[etencetom.livejournal.com]

главное опыт - его не взять


http://huntingcoloradostyle.com/content/purim-wholesale-cheap-uk-gb-purim-overnight-delivery-without-rx
;
http://huntingcoloradostyle.com/content/retin-gut-preis-bestellen-deutschland-retin-shipped-no-rx