Спектральная(ое) теорема/разложение в приближённом формате

[grizzly]

(Оффтоп)

amarsianin в сообщении #1120183 писал(а):

g______d в сообщении #1120154 писал(а):

1) Укажите первое (не все, а только первое) утверждение, которое вы считаете неправильным.

Ответьте на вопрос: вычислим ли базис линейного подпространства, если дана (вычислимая) матрица проекии на него?

Напомнило "Розенкранц и Гильденстерн мертвы". Там где главные герои играли в вопросы. Один из любимых эпизодов (там их даже несколько на эту тему :)

[amarsianin]

(Оффтоп)

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

[g______d]

amarsianin в сообщении #1120183 писал(а):

Ответьте на вопрос: вычислим ли базис линейного подпространства, если дана (вычислимая) матрица проекии на него?

Если проекция ортогональная — то да.

-- Пн, 02 май 2016 09:46:25 --

amarsianin в сообщении #1120183 писал(а):

Дайте хоть ссылку уже на вашу причудливую модель вычислимой математики.

Мне не нужна никакая модель "вычислимой математики". Это вопрос классической математики. Еще раз: (классическое) вещественное число $a$ называется вычислимым, если существует алгоритм, генерирующий последовательность рациональных чисел $q_n$, такой что $|q_n-a|<2^{-n}$. И все.

-- Пн, 02 май 2016 09:51:06 --

amarsianin в сообщении #1120024 писал(а):

И, проконсультировавшись ещё на одном форуме

Это здесь, что ли? Лол.

-- Пн, 02 май 2016 10:07:20 --

Собственно, если вам не нравится мой аргумент с вычислимостью базиса с помощью функции $f(n,k)$ (хотя он верный), обратите внимание, что ортогональный проектор — это самосопряженный оператор, спектр которого содержится в множестве $\{0,1\}$. Следовательно, вам фактически дана мощность спектра, а при этом условии базис вычислим.

[amarsianin]

g______d в сообщении #1120203 писал(а):

Если проекция ортогональная — то да.

Интересно. А есть ссылка на такое утверждение?

g______d в сообщении #1120203 писал(а):

Мне не нужна никакая модель "вычислимой математики". Это вопрос классической математики. Еще раз: (классическое) вещественное число $a$ называется вычислимым, если существует алгоритм, генерирующий последовательность рациональных чисел $q_n$, такой что $|q_n-a|<2^{-n}$. И все.

На самом деле, модели её есть. TTE, например. Есть утверждения вычислимой математики, которые в классической просто не верны.

g______d в сообщении #1120203 писал(а):

Лол

(Оффтоп)

А что смешного?

g______d в сообщении #1120203 писал(а):

Собственно, если вам не нравится мой аргумент с вычислимостью базиса с помощью функции $f(n,k)$ (хотя он верный

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

g______d в сообщении #1120203 писал(а):

обратите внимание, что ортогональный проектор — это самосопряженный оператор, спектр которого содержится в множестве $\{0,1\}$

Не "содержится", а должен именно совпадать с этим множеством. Если только "содержится", то не верно. Справедливости ради, процедура вычисления базиса при известной мощности спектра подразумевает принцип Маркова, который классически верен, но совершенно бесполезен для реальных расчётов. Потому что нет вычислимой оценки на число итераций, за котрое алгоритм найдёт кратности корней, даже если их три, а мощность, скажем, два.

[g______d]

Так, ну хорошо, пусть у нас есть вычислимый классический ортогональный проектор $P$, т. е. последовательность матриц $P_j$ с рациональными элементами, такая что $\|P-P_j\|<2^{-j}$. Согласны с такой постановкой?

amarsianin в сообщении #1120278 писал(а):

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

Я уже накидал не просто скетч, а достаточно подробный вариант, но вы его пропустили мимо ушей. Там, где было $f(n,k)$.

amarsianin в сообщении #1120278 писал(а):

На самом деле, модели её есть. TTE, например. Есть утверждения вычислимой математики, которые в классической просто не верны.

Без разницы. В сообщении, которое вы цитировали, я абсолютно точно сформулировал, что понимается под вычислимостью.

amarsianin в сообщении #1120278 писал(а):

Не "содержится", а должен именно совпадать с этим множеством.

Без разницы. Существует всего 2 случая, когда не совпадает: $P=0$ или $P=I$. Оба отсекаются при $j>\log_2 n$, где $n$ — размерность всего пространства.

amarsianin в сообщении #1120278 писал(а):

Потому что нет вычислимой оценки на число итераций, за котрое алгоритм найдёт кратности корней, даже если их три, а мощность, скажем, два.

Если вы не можете ее найти, это не значит, что ее нет. Я не знаю никакого принципа Маркова, но вы вряд ли сможете поспорить со следующим явным алгоритмом.

Возьмем $P_j$ из начала поста и пусть $n 2^{-j}<1/2$ (явная оценка). Вычислим сумму диагональных элементов $P_j$ (явно вычисленное рациональное число) и обозначим ее через $q$.

Из самой первой оценки следует $|q-\mathrm{tr}\,P|<1/2$. Кроме того, $\mathrm{tr}\,P\in \mathbb Z$. Возьмем ближайшее целое число к $q$ (явная операция, поскольку $q$ рационально). Оно будет равно $\mathrm{tr}\,P$, т. е. полной кратности собственного значения 1. Вычтем из $n$ — получим кратность нуля.

Т. е. я вам описал, как за $\log_2 n$ операций найти обе кратности (т. е. нуля и единицы в спектре), используя только рациональную арифметику над входными данными (т. е. элементами $P_j$).

[amarsianin]

g______d в сообщении #1120286 писал(а):

Так, ну хорошо, пусть у нас есть вычислимый классический ортогональный проектор $P$, т. е. последовательность матриц $P_j$ с рациональными элементами, такая что $\|P-P_j\|<2^{-j}$. Согласны с такой постановкой?

Я согласен с тем, что интеграл вычислим.

По поводу базиса.

g______d в сообщении #1118240 писал(а):

Лемма: существует вычислимая функция $f(n,k)>0$, такая что у любого $n\times n$ - проектора на подпространство размерности $k$ хотя бы один минор размерности $k$ больше либо равен $f(n,k)$. Опять же, мне лень ее выписывать, но я могу, если надо.

g______d в сообщении #1119908 писал(а):

Про базис: вычислимы все столбцы проектора $P_i$. Среди этих столбцов есть базис. Следовательно, достаточно знать, какие именно столбцы нужно выбирать. Я уже выше писал, как это сделать: с помощью функции $f(n,k)$. Более подробно (я заменю переменную в следующей формуле, чтобы не обозначать той же буквой). У нас есть последовательность рациональных проекторов $P_i^{(m)}$:

$$ \|P_i-P_i^{(m)}\|<2^{-m}. $$

Выберем $m$ так, чтобы все миноры матриц $P_i^{(m)}$ заведомо отличались от соответствующих миноров $P_i$ не более чем на $f(n,k)/2$. Для этого не нужно знать $P_i$, достаточно иметь оценку из предыдущей формулы, разность миноров можно грубо оценить через норму разности матриц с большим (но фиксированным) коэффициентом. Один из миноров $P_i^{(m)}$ будет по абсолютной величине $\ge f(n,k)$ (по построению этой функции). Столбцы, из которых составлен этот минор, и будут нужными столбцами, которые можно пометить и больше не менять.

Вы же и не доказывали лемму. Во-вторых, размерность принята известной.

Я, если честно, не очень понял смысл вашей леммы. Вы даже не берёте проектор как входной параметр?

g______d в сообщении #1120286 писал(а):

Без разницы. В сообщении, которое вы цитировали, я абсолютно точно сформулировал, что понимается под вычислимостью.

Вы должны точно определить, что значит "классическое" действительное число. Если есть алгоритм вычисления рац. аппроксимаций, то число вычислимое, причём тут классическое/неклассическое?

g______d в сообщении #1120286 писал(а):

Если вы не можете ее найти, это не значит, что ее нет. Я не знаю никакого принципа Маркова, но вы вряд ли сможете поспорить со следующим явным алгоритмом.

Принцип Маркова: если бесконечная бинарная последовательность не может состоять из одних нулей, то в ней существует единица. На этот принцип опирается доказательство того факта, что если среди $n$ (вычислимых) действительных чисел только $m \leq n$ различны, то кратность каждого можно вычислить. Не существует вычислимой оценки числа итерацией, через которое ответ будет выдан.

g______d в сообщении #1120286 писал(а):

Возьмем ...

Этот алгоритм работает, если заранее известно, что пределом итераций является идемпотентная матрица, range лин. оболочки которой имеет размерность, равную её следу. Проблема в том, что у вас получается, что базисы собственных подпространств в таком случае вычислимы, разве нет?

[g______d]

amarsianin в сообщении #1120876 писал(а):

заранее известно, что пределом итераций является идемпотентная матрица, range лин. оболочки которой имеет размерность, равную её следу.

Так это заранее и известно; это свойство классических проекторов, а итерации к ним сходятся. Вы уже с этим согласились.

amarsianin в сообщении #1120876 писал(а):

Я, если честно, не очень понял смысл вашей леммы. Вы даже не берёте проектор как входной параметр?

Я не понимаю, что ещё нужно объяснять в формулировке леммы. Существует явно выписываемая функция, такая что для любого ортогонального проектора со следом $k$ выполняется некоторое свойство. Если вы согласитесь со всем остальным, то я, может быть, выпишу вам эту функцию. Проектор не входной параметр, потому что он под квантором.

Смысл леммы в том, что вам нужно найти $k$ линейно независимых векторов из данного набора, если заведомо известно, что там они есть. Или, что то же самое, найти ненулевой минор (если заведомо известно, что он есть). Просто найти ненулевой -- не вычислимая задача. А вот если заведомо известно, что есть минор больший, чем $f(n,k)>0$, то его уже можно найти, достаточно выбрать такую точность, чтобы ошибка вычисления минора заведомо не превосходила $f(n,k)/2$.

amarsianin в сообщении #1120876 писал(а):

Вы должны точно определить, что значит "классическое" действительное число.

Любое определение из курса классического анализа.

amarsianin в сообщении #1120876 писал(а):

Если есть алгоритм вычисления рац. аппроксимаций, то число вычислимое, причём тут классическое/неклассическое?

Тогда вообще без разницы. Алгоритм я описал.

[amarsianin]

g______d в сообщении #1120962 писал(а):

Проектор не входной параметр, потому что он под квантором.

Уже увидел.

g______d в сообщении #1120962 писал(а):

Любое определение из курса классического анализа.

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

g______d в сообщении #1120962 писал(а):

Так это заранее и известно; это свойство классических проекторов, а итерации к ним сходятся. Вы уже с этим согласились.

Нет, я согласился с тем, что интеграл вычислим. Остальное (содержание теоремы 6.17 книги Като) невычислимо. Или по крайней мере это открытый вопрос.

Я понял вашу идею с функцией $f$. Я согласен, что если такая есть (как witness), то ненулевой минор вычислим. Но целый ряд вопросов остаётся открытым. Например, вопрос размерности. Я их перечислил под пунктом 2 выше.

[g______d]

amarsianin в сообщении #1120988 писал(а):

Просто давайте будем подразделять действительные числа на вычисилмые и невычисилмые.

Давайте. Т. е. множество всех вещественных чисел делится на вычислимые и не вычислимые. И те, и другие допускают рациональную аппроксимацию. Если при этом рациональная аппроксимация предъявлена явно и является регулярной (по-видимому, это значит $|a-q_j|<2^{-j}$), то это число вычислимо. Т. е. для доказательства вычислимости того или иного вещественного числа достаточно предъявить рациональную аппроксимацию и доказать, что она является регулярной.

amarsianin в сообщении #1120988 писал(а):

Нет, я согласился с тем, что интеграл вычислим.

Ну так, интеграл вычислим. А тот факт, что он равен классическому проектору, это просто факт классического анализа, вычислимость здесь иррелевантна. Если средствами анализа доказано, что два вещественных числа (или две матрицы) равны, и одно из них вычислимо, то другое тоже вычислимо тем же самым алгоритмом.

amarsianin в сообщении #1120988 писал(а):

Например, вопрос размерности.

Я написал выше точную процедуру и оценку количества итераций для вычисления размерности.

amarsianin в сообщении #1120988 писал(а):

Я согласен, что если такая есть (как witness), то ненулевой минор вычислим.

Вот, кстати, есть простой способ получить эту функцию. Лемма: если есть ортогональный проектор ранга $k$, то сумма квадратов всех его $(k\times k)$-миноров равна единице. Отсюда очевидная нижняя оценка на модуль максимального минора.

[amarsianin]

g______d в сообщении #1120992 писал(а):

Т. е. для доказательства вычислимости того или иного вещественного числа достаточно предъявить рациональную аппроксимацию и доказать, что она является регулярной.

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

g______d в сообщении #1120992 писал(а):

А тот факт, что он равен классическому проектору, это просто факт классического анализа, вычислимость здесь иррелевантна. Если средствами анализа доказано, что два вещественных числа (или две матрицы) равны, и одно из них вычислимо, то другое тоже вычислимо тем же самым алгоритмом.

В прицнипе, эта тафтология. Но нас интересует не это. Нас интересует вычислимое содержание теорема Като о размерности и базисе.

g______d в сообщении #1120992 писал(а):

Я написал выше точную и процедуру и оценку итераций для вычисления размерности.

При условии, что размерность известна заранее.

g______d в сообщении #1120992 писал(а):

Лемма: если есть ортогональный проектор ранга $k$, то сумма квадратов всего его $(k\times k)$-миноров равна единице. Отсюда очевидная нижняя оценка на модуль максимального минора.

Тут ещё зацепка в том, что все трюки со следом, собств. значениями ноль и единица, а также размерностью подпространства опираются на точную фунд. теорему линейной алгебры. Йе и Бишоп, которых я цитировал, не зря определяют свойства проекторов, не прибегая к точным собств. значениям и векторам. В принципе, я бы и не задавал вопрос, если бы они указали, как вычислить размерность и базис:



Причём проекторы $E$, возможно, допускают определение через конутрный интеграл, не знаю. Есть определение через хар. функцию:



Она не является вычислимой функцией, строго говоря, на всём $\mathbb{C}^n$. Но зато вычислима на определённых подножествах.

[g______d]

amarsianin в сообщении #1121011 писал(а):

При условии, что размерность известна заранее.

Нам не нужно, чтобы она была известна. Алгоритм ее на входе не требует. И количество итераций алгоритма не зависит от того, чему именно она равна.

amarsianin в сообщении #1121011 писал(а):

Нас интересует вычислимое содержание теорема Като о размерности и базисе.

Изначально вопрос был о вычислимости приближенных собственных векторов. Алгоритм ровно их и получает.

amarsianin в сообщении #1121011 писал(а):

опираются на точную фунд. теорему линейной алгебры.

amarsianin в сообщении #1121011 писал(а):

Йе и Бишоп, которых я цитировал, не зря определяют свойства проекторов, не прибегая к точным собств. значениям и векторам.

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

[amarsianin]

amarsianin в сообщении #1121011 писал(а):

Нам не нужно, чтобы она была известна. Алгоритм ее на входе не требует. И количество итераций алгоритма не зависит от того, чему именно она равна.

Вы про этот алгоритм:

g______d в сообщении #1120286 писал(а):

но вы вряд ли сможете поспорить со следующим явным алгоритмом.

?

g______d в сообщении #1121025 писал(а):

Изначально вопрос был о вычислимости приближенных собственных векторов. Алгоритм ровно их и получает.

Не только. В полном (приближённом) формате теорема нужна.

g______d в сообщении #1121025 писал(а):

Главное, чтобы процедура вычисления не использовала неконструктивной информации

Наконец-то мы на этом сошлись.

g______d в сообщении #1121025 писал(а):

Сами итерации и их количество зависят только от входных данных.

Я с этим не спорю. Но мы пока что используем слишком много "неконструктивной информации". Что собств. значения - только ноль и единица (я даже не знаю, как это показать без определения собств. вектора или фунд. теоремы линала о ядре, разве что след. теорема может помочь):



Взято отсюда.

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

[g______d]

amarsianin в сообщении #1121041 писал(а):

Вы про этот алгоритм:

Да.

amarsianin в сообщении #1121041 писал(а):

мы пока что используем слишком много "неконструктивной информации".

amarsianin в сообщении #1121041 писал(а):

Что собств. значения - только ноль и единица (я даже не знаю, как это показать без определения собств. вектора или фунд. теоремы линала о ядре

В спецификации алгоритма (т. е. в самом коде и в формуле, оценивающей число итераций) никакой неконструктивной информации не содержится.

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

-- Ср, 04 май 2016 12:32:51 --

amarsianin в сообщении #1121041 писал(а):

Но с чего вдруг она обязана быть равной числу корней хар. полинома внутри контура.

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

[amarsianin]

g______d в сообщении #1121046 писал(а):

Ну так и что, я не вижу в этом никаких проблем.

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

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

[g______d]

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

Мне кажется, что во всех содержательных работах в этой области (например, https://pdfs.semanticscholar.org/a669/d ... 9f0183.pdf) используется, по сути, такой подход.

Спросите у авторов, раз уж вы не верите и раз уж вы им все равно писали.

-- Ср, 04 май 2016 13:21:13 --

Одно дело когда алгоритм разваливается, а другое дело — когда я доказал, что он не разваливается, а вы мне говорите, что я использовал в доказательстве какой-то запрещенный анализ. Первое — реальная проблема в TCS, а второе — схоластика.