Метод Качмажа

Метод Качмажа или алгоритм Качмажа — это итерационный алгоритм решения систем линейных уравнений. $Ax=b$. Впервые его открыл польский математик Стефан Качмарж . и был заново открыт в области реконструкции изображений по проекциям Ричардом Гордоном , Робертом Бендером и Габором Херманом в 1970 году, где он получил название «Техника алгебраической реконструкции» (ART). ART включает ограничение положительности, что делает его нелинейным.

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

Он имеет множество применений: от компьютерной томографии (КТ) до обработки сигналов . Его можно получить также, применив к гиперплоскостям, описываемым линейной системой, метод последовательных проекций на выпуклые множества (ПОКС).

Алгоритм 1: алгоритм Качмажа

Позволять $Ax=b$ — система линейных уравнений , пусть $m$ быть числом строк A , $a_{i}$ быть $i$ строка комплексной матрицы -я $A$, и пусть $x^{0}$ — произвольное комплексное начальное приближение решения задачи $Ax=b$. Для $k=0,1,\ldots$ вычислить:

$x^{k+1}=x^{k}+{\frac {b_{i}-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}{\overline {a_{i}}}$ ( 1 )

где $i=k{\bmod {m}}+1,i=1,2,\ldots m$ и ${\overline {a_{i}}}$ обозначает комплексное сопряжение $a_{i}$.

Если система непротиворечива, $x^{k}$ сходится к решению минимальной нормы при условии, что итерации начинаются с нулевого вектора.

Более общий алгоритм можно определить с помощью релаксации параметра $\lambda ^{k}$

$x^{k+1}=x^{k}+\lambda ^{k}{\frac {b_{i}-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}{\overline {a_{i}}}$

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

Алгоритм 2: Рандомизированный алгоритм Качмажа

рандомизированную версию метода Качмажа для переопределенных линейных систем. В 2009 году Томас Стромер и Роман Вершинин представили в котором i -е уравнение выбирается случайным образом с вероятностью, пропорциональной $\|a_{i}\|^{2}.$

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

При таких обстоятельствах $x_{k}$ экспоненциально быстро сходится к решению задачи $Ax=b,$ и скорость сходимости зависит только от масштабированного числа обусловленности $\kappa (A)$.

Теорема. Позволять $x$ быть решением $Ax=b.$ Тогда алгоритм 2 сходится к $x$ в ожидании, со средней ошибкой:

$\mathbb {E} \|x_{k}-x\|^{2}\leq \left(1-\kappa (A)^{-2}\right)^{k}\cdot \|x_{0}-x\|^{2}.$

Доказательство

У нас есть

$\forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}|\langle z,a_{j}\rangle |^{2}\geq {\frac {\|z\|^{2}}{\|A^{-1}\|^{2}}}$ ( 2 )

С использованием

$\|A\|^{2}=\sum _{j=1}^{m}\|a_{j}\|^{2}$

мы можем написать ( 2 ) как

$\forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}{\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\left|\left\langle z,{\frac {a_{j}}{\|a_{j}\|}}\right\rangle \right|^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}$ ( 3 )

Основная суть доказательства состоит в том, чтобы рассматривать левую часть в ( 3 ) как математическое ожидание некоторой случайной величины. А именно, напомним, что пространство решений задачи $j-th$ уравнение $Ax=b$ это гиперплоскость

$\{y:\langle y,a_{j}\rangle =b_{j}\},$

чья норма ${\tfrac {a_{j}}{\|a_{j}\|^{2}}}.$ Определим случайный вектор Z , значения которого являются нормалями ко всем уравнениям $Ax=b$, с вероятностями, как в нашем алгоритме:

$Z={\frac {a_{j}}{\|a_{j}\|}}$ с вероятностью ${\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\qquad \qquad \qquad j=1,\ldots ,m$

Тогда ( 3 ) говорит, что

$\forall z\in \mathbb {C} ^{n}:\quad \mathbb {E} |\langle z,Z\rangle |^{2}\geq \kappa (A)^{-2}{\|z\|^{2}}$ ( 4 )

Ортогональная проекция $P$ на пространство решений случайного уравнения $Ax=b$ дается $Pz=z-\langle z-x,Z\rangle Z.$

Теперь мы готовы проанализировать наш алгоритм. Мы хотим показать, что ошибка ${\|x_{k}-x\|^{2}}$ уменьшается на каждом шаге в среднем (обусловленном предыдущими шагами) не менее чем в раз $(1-\kappa (A)^{-2}).$ Следующее приближение $x_{k}$ рассчитывается из $x_{k-1}$ как $x_{k}=P_{k}x_{k-1},$ где $P_{1},P_{2},\ldots$ являются независимыми реализациями случайной проекции $P.$ Вектор $x_{k-1}-x_{k}$ находится в ядре $P_{k}.$ Оно ортогонально пространству решений уравнения, на которое $P_{k}$ проекты, который содержит вектор $x_{k}-x$ (напомним, что $x$ является решением всех уравнений). Тогда ортогональность этих двух векторов дает

$\|x_{k}-x\|^{2}=\|x_{k-1}-x\|^{2}-\|x_{k-1}-x_{k}\|^{2}.$

Для завершения доказательства нам нужно оценить $\|x_{k-1}-x_{k}\|^{2}$ снизу. По определению $x_{k}$, у нас есть

$\|x_{k-1}-x_{k}\|=\langle x_{k-1}-x,Z_{k}\rangle$

где $Z_{1},Z_{2},\ldots$ являются независимыми реализациями случайного вектора $Z.$

Таким образом

$\|x_{k}-x\|^{2}\leq \left(1-\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.$

Теперь мы считаем ожидание обеих сторон обусловленным выбором случайных векторов $Z_{1},\ldots ,Z_{k-1}$ (следовательно, мы фиксируем выбор случайных проекций $P_{1},\ldots ,P_{k-1}$ и, следовательно, случайные векторы $x_{1},\ldots ,x_{k-1}$ и мы усредняем по случайному вектору $Z_{k}$). Затем

$\mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}=\left(1-\mathbb {E} _{Z_{1},\ldots ,Z_{k-1},Z_{k}}\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.$

Ввиду ( 4 ) и независимости

$\mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}\leq (1-\kappa (A)^{-2}){\|x_{k-1}-x\|^{2}}.$

Учитывая все ожидания обеих сторон, мы приходим к выводу, что

$\mathbb {E} \|x_{k}-x\|^{2}\leq (1-\kappa (A)^{-2})\mathbb {E} {\|x_{k-1}-x\|^{2}}.\blacksquare$

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

Итерация Качмажа ( 1 ) имеет чисто геометрическую интерпретацию: алгоритм последовательно проецирует текущую итерацию на гиперплоскость, определяемую следующим уравнением. Следовательно, любое масштабирование уравнений не имеет значения; ) также видно из ( 1 , что любое (ненулевое) масштабирование уравнений отменяется. Таким образом, в РК можно использовать $\|a_{i}\|$ или любые другие веса, которые могут иметь значение. В частности, в вышеупомянутом примере реконструкции уравнения были выбраны с вероятностью, пропорциональной среднему расстоянию каждой точки выборки от двух ее ближайших соседей — концепция, введенная Файхтингером и Грёхенигом . Дополнительную информацию по этой теме см. и ссылки в нем.

Алгоритм 3: Алгоритм Гауэра-Рихтарика

В 2015 году Роберт М. Гауэр и Питер Рихтарик разработал универсальный рандомизированный итерационный метод решения совместной системы линейных уравнений $Ax=b$ который включает в себя рандомизированный алгоритм Качмажа как частный случай. Другие особые случаи включают рандомизированный спуск по координатам, рандомизированный гауссовский спуск и рандомизированный метод Ньютона. Блочные версии и версии с выборкой по важности всех этих методов также возникают как частные случаи. Показано, что этот метод демонстрирует экспоненциальное затухание скорости (в ожидании), также известное как линейная сходимость, при очень мягких условиях на пути попадания случайности в алгоритм. Метод Гауэра-Рихтарика — это первый алгоритм, раскрывающий «родственные» отношения между этими методами, некоторые из которых были независимо предложены ранее, а многие из них были новыми.

Информация о рандомизированном Качмаже

Интересные новые сведения о рандомизированном методе Качмажа, которые можно получить в результате анализа метода, включают:

• Общая скорость алгоритма Гауэра-Рихтарика точно восстанавливает скорость рандомизированного метода Качмажа в частном случае, когда он сведен к ней.
• Выбор вероятностей, для которых изначально был сформулирован и проанализирован рандомизированный алгоритм Качмажа (вероятности, пропорциональные квадратам норм строк), не является оптимальным. Оптимальные вероятности являются решением некоторой полуопределённой программы. Теоретическая сложность рандомизированного Качмажа с оптимальными вероятностями может быть сколь угодно лучше, чем сложность для стандартных вероятностей. Однако степень, на которую оно лучше, зависит от матрицы $A$. Существуют задачи, для которых стандартные вероятности оптимальны.
• Применительно к системе с матрицей $A$ который является положительно определенным, рандомизированный метод Качмажа эквивалентен методу стохастического градиентного спуска (SGD) (с очень особым размером шага) для минимизации сильно выпуклой квадратичной функции. $f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.$ Обратите внимание, что поскольку $f$ является выпуклым, минимизаторы $f$ должен удовлетворить $\nabla f(x)=0$, что эквивалентно $Ax=b.$ «Специальный размер шага» — это размер шага, который приводит к точке, которая на одномерной линии, натянутой стохастическим градиентом, минимизирует евклидово расстояние от неизвестного (!) минимизатора $f$, а именно из $x^{*}=A^{-1}b.$ Это понимание достигается благодаря двойному взгляду на итеративный процесс (ниже описанный как «Точка зрения оптимизации: ограничение и аппроксимация»).

Шесть эквивалентных составов

Метод Гауэра-Рихтарика имеет шесть, казалось бы, разных, но эквивалентных формулировок, проливающих дополнительный свет на то, как его интерпретировать (и, как следствие, как интерпретировать его многочисленные варианты, включая рандомизированный метод Качмажа):

• 1. Точка зрения эскиза: эскиз и проект
• 2. Точка зрения оптимизации: ограничение и приближение
• 3. Геометрическая точка зрения: случайное пересечение.
• 4. Алгебраическая точка зрения 1: случайное линейное решение
• 5. Алгебраическая точка зрения 2: случайное обновление
• 6. Аналитическая точка зрения: случайная фиксированная точка.

Опишем некоторые из этих точек зрения. Метод зависит от 2 параметров:

• положительно определенная матрица $B$ что приводит к взвешенному евклидову внутреннему продукту $\langle x,y\rangle _{B}:=x^{T}By$ и индуцированная норма

$\|x\|_{B}=\left(\langle x,x\rangle _{B}\right)^{\frac {1}{2}},$

• и случайная матрица $S$ с таким количеством строк, как $A$ (и, возможно, случайное количество столбцов).

1. Эскиз и проект

Учитывая предыдущую итерацию $x^{k},$ новая точка $x^{k+1}$ вычисляется путем рисования случайной матрицы $S$ (в духе iid из некоторого фиксированного дистрибутива) и установив

$x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\|x-x^{k}\|_{B}{\text{ subject to }}S^{T}Ax=S^{T}b.$

То есть, $x^{k+1}$ получается как проекция $x^{k}$ на случайно нарисованную систему $S^{T}Ax=S^{T}b$. Идея этого метода состоит в том, чтобы выбрать $S$ таким образом, что проекция на нарисованную систему существенно проще, чем решение исходной системы. $Ax=b$. Рандомизированный метод Качмажа получается путем выбора $B$ быть единичной матрицей, и $S$ быть $i^{th}$ единичный вектор координат с вероятностью $p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.$ Различные варианты $B$ и $S$ приводят к различным вариантам метода.

2. Ограничить и приблизить

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

$x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\left\|x-x^{*}\right\|_{B}{\text{ subject to }}x=x^{k}+B^{-1}A^{T}Sy,$

где $y$ также допускается варьировать, и где $x^{*}$ любое решение системы $Ax=b.$ Следовательно, $x^{k+1}$ получается путем сначала ограничения обновления линейным подпространством, охватываемым столбцами случайной матрицы $B^{-1}A^{T}S$, то есть, чтобы

$\left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{ can vary }}\right\},$

а затем выбираем точку $x$ из этого подпространства, которое лучше всего аппроксимирует $x^{*}$. Эта формулировка может показаться неожиданной, поскольку выполнить этап аппроксимации кажется невозможным из-за того, что $x^{*}$ неизвестно (ведь это мы и пытаемся вычислить!). Однако это все еще возможно сделать просто потому, что $x^{k+1}$ вычисленный таким образом, аналогичен $x^{k+1}$ рассчитывается по эскизу и формулировке проекта, и поскольку $x^{*}$ там не появляется.

5. Случайное обновление

Обновление также можно записать явно как

$x^{k+1}=x^{k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}\left(Ax^{k}-b\right),$

где $M^{\dagger }$ мы обозначаем псевдообратную матрицу Мура-Пенроуза $M$. Следовательно, метод можно записать в виде $x^{k+1}=x^{k}+h^{k}$, где $h^{k}$ — случайный вектор обновления .

Сдача в аренду $M=S^{T}AB^{-1}A^{T}S,$ можно показать, что система $My=S^{T}(Ax^{k}-b)$ всегда есть решение $y^{k}$, и что для всех таких решений вектор $x^{k+1}-B^{-1}A^{T}Sy^{k}$ то же самое. Следовательно, не имеет значения, какое из этих решений выбрано, и метод также можно записать в виде $x^{k+1}=x^{k}-B^{-1}A^{T}Sy^{k}$. Псевдообратное приводит только к одному частному решению. Роль псевдообратного двояка:

• Это позволяет записать метод в явной форме «случайного обновления», как указано выше:
• Это упрощает анализ благодаря последней, шестой формулировке.

6. Случайная фиксированная точка

Если мы вычтем $x^{*}$ с обеих сторон формулы случайного обновления обозначим

$Z:=A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}A,$

и использовать тот факт, что $Ax^{*}=b,$ мы приходим к последней формулировке:

$x^{k+1}-x^{*}=\left(I-B^{-1}Z\right)\left(x^{k}-x^{*}\right),$

где $I$ является единичной матрицей. Итерационная матрица, $I-B^{-1}Z,$ случайна, отсюда и название этой формулировки.

Конвергенция

Взяв условные ожидания в 6-й формулировке (условно $x^{k}$), получаем

$\mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(I-B^{-1}\mathbb {E} [Z]\right)\left[x^{k}-x^{*}\right].$

Снова взяв ожидание и используя свойство башни ожиданий, мы получаем

$\mathbb {E} \left[x^{k+1}-x^{*}\right]=(I-B^{-1}\mathbb {E} [Z])\mathbb {E} \left[x^{k}-x^{*}\right].$

Гауэр и Рихтарик покажи это

$\rho :=\left\|I-B^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(I-B^{-1}\mathbb {E} [Z]\right),$

где матричная норма определяется выражением

$\|M\|_{B}:=\max _{x\neq 0}{\frac {\|Mx\|_{B}}{\|x\|_{B}}}.$

Более того, без каких-либо предположений о $S$ у одного есть $0\leq \rho \leq 1.$ Взяв нормы и развернув рекуррентность, получаем

Теорема [Gower & Richtarik 2015]

$\left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{0}-x^{*}\|_{B}.$

Замечание . Достаточным условием сходимости ожидаемых остатков к 0 является $\rho <1.$ Этого можно достичь, если $A$ имеет полный ранг столбца и находится в очень мягких условиях на $S.$ Сходимость метода можно установить и без предположения полного ранга столбца другим способом.

Также возможно показать более сильный результат:

Теорема [Gower & Richtarik 2015]

Ожидаемые квадраты норм (а не нормы ожиданий) сходятся с одинаковой скоростью:

$\mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\left\|x^{0}-x^{*}\right\|_{B}^{2}.$

Замечание . Этот второй тип сходимости является более сильным благодаря следующему тождеству что справедливо для любого случайного вектора $x$ и любой фиксированный вектор $x^{*}$:

$\left\|\mathbb {E} \left[x-x^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\|x-x^{*}\right\|^{2}\right]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\right].$

Конвергенция рандомизированного Качмажа

Мы видели, что рандомизированный метод Качмажа является частным случаем метода Гауэра-Рихтарика для $B=I$ и $S$ быть $i^{th}$ единичный вектор координат с вероятностью $p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2},$ где $a_{i}$ это $i^{th}$ ряд $A.$ Непосредственным расчетом можно проверить, что

$\rho =\|I-B^{-1}\mathbb {E} [Z]\|_{B}=1-{\frac {\lambda _{\min }(A^{T}A)}{\|A\|_{F}^{2}}}.$

Алгоритм 4: PLSS-Качмарц

Поскольку сходимость (рандомизированного) метода Качмажа зависит от скорости сходимости, метод может медленно прогрессировать в решении некоторых практических задач. Чтобы обеспечить конечное завершение метода, Йоханнес Бруст и Майкл Сондерс (академический) разработали процесс, который обобщает (рандомизированную) итерацию Качмажа и заканчивается не более чем через $m$ итерации к решению для согласованной системы $Ax=b$. Процесс основан на уменьшении размерности или проекциях. на пространства более низких измерений, отсюда и название PLSS (Проецируемый линейный решатель систем). Итерацию PLSS-Качмарца можно рассматривать как обобщение

$x^{k+1}=x^{k}+A_{:,1:k}^{T}(A_{1:k,:}A_{:,1:k}^{T})^{\dagger }(b_{1:k}-A_{1:k,:}x^{k})$

где $A_{1:k,:}$ это выбор строк с 1 по $k$ и все столбцы $A$. Рандомизированная версия метода использует $k$ неповторяющиеся индексы строк на каждой итерации: $\{i_{1},\ldots ,i_{k-1},i_{k}\}$ где каждый $i_{j}$ находится в $1,2,...,m$. Итерация сходится к решению, когда $k=m$. В частности, поскольку $A_{1:m,:}=A$ он утверждает, что

$Ax^{m+1}=Ax^{m}+AA^{T}(AA^{T})^{\dagger }(b-Ax^{m})=b$

и поэтому $x^{m+1}$ является решением линейной системы. Вычисление итераций в PLSS-Kaczmarz можно упростить и эффективно организовать. Полученный алгоритм требует только матрично-векторных произведений и имеет прямой вид

algorithm PLSS-Kaczmarz is
    input: matrix A right hand side b
    output: solution x such that Ax=b

    x := 0, P = [0]
    for k in 1,2,...,m do
        
        a := A(ik,:)'                   // Select an index ik in 1,...,m without resampling
        d := P' * a        
        c1 := norm(a)
        c2 := norm(d)
        c3 := (bik-x'*a)/((c1-c2)*(c1+c2))
        p := c3*(a - P*(P'*a))
        P := [ P, p/norm(p) ]           // Append a normalized update
        x := x + p

    return x

Ссылки

• Качмарц, Стефан (1937), «Angenäherte Auflösung von Systemen Linearer Gleichungen» (PDF) , Международный бюллетень Польской академии наук и литературы. Класс математики и естественных наук. Серия А, Математические науки , вып. 35, с. 355–357
• Чонг, Эдвин КП; Зак, Станислав Х. (2008), Введение в оптимизацию (3-е изд.), John Wiley & Sons, стр. 226–230.
• Гордон, Ричард ; Бендер, Роберт ; Герман, Габор (1970), «Методы алгебраической реконструкции (ART) для трехмерной электронной микроскопии и рентгеновской фотографии», Journal of Theoretical Biology , 29 (3): 471–481, Bibcode : 1970JThBi..29..471G , doi : 10.1016/0022-5193(70)90109-8 , PMID   5492997
• Гордон, Ричард (2011), Остановите рак груди сейчас! Представляя пути визуализации для поиска, уничтожения, лечения и бдительного ожидания преметастазного рака молочной железы. В: Рак молочной железы – долевая болезнь, редактор: Тибор Тот , Спрингер, стр. 167–203.
• Герман, Габор (2009), Основы компьютерной томографии: реконструкция изображения по проекции (2-е изд.), Springer, ISBN  9781846287237
• Цензор, Яир ; Зениос, С.А. (1997), Параллельная оптимизация: теория, алгоритмы и приложения , Нью-Йорк: Oxford University Press.
• Астер, Ричард; Борчерс, Брайан; Тербер, Клиффорд (2004), Оценка параметров и обратные задачи , Elsevier
• Стромер, Томас; Вершинин, Роман (2009), «Рандомизированный алгоритм Качмарца для линейных систем с экспоненциальной сходимостью» (PDF) , Журнал анализа и приложений Фурье , 15 (2): 262–278, arXiv : math/0702226 , doi : 10.1007/s00041 -008-9030-4 , S2CID   1903919
• Ниделл, Дина; Сребро, Нати; Уорд, Рэйчел (2015), «Стохастический градиентный спуск, взвешенная выборка и рандомизированный алгоритм Качмарца», Mathematical Programming , 155 (1–2): 549–573, arXiv : 1310.5715 , doi : 10.1007/s10107-015-0864- 7 , С2КИД   2370209
• Цензор, Яир; Герман, Габор ; Цзян, М. (2009), «Заметка о поведении рандомизированного алгоритма Качмарца Стромера и Вершинина», Journal of Fourier Analysis and Applications , 15 (4): 431–436, doi : 10.1007/s00041-009-9077 -x , PMC   2872793 , PMID   20495623
• Стромер, Томас; Вершинин, Роман (2009b), «Комментарии к рандомизированному методу Качмажа», Журнал анализа и приложений Фурье , 15 (4): 437–440, doi : 10.1007/s00041-009-9082-0 , S2CID   14806325
• Басс, Ричард Ф .; Грехениг, Карлхайнц (2013), «Соответствующая выборка функций с ограниченной полосой», Illinois Journal of Mathematics , 57 (1): 43–58, arXiv : 1203.0146 , doi : 10.1215/ijm/1403534485 , S2CID   42705738
• Гордон, Дэн (2017), «Подход к дерандомизации для восстановления сигналов с ограниченной полосой пропускания в широком диапазоне частот случайной выборки», Numerical Algorithms , 77 (4): 1141–1157, doi : 10.1007/s11075-017-0356-3 , S2CID   1794974
• Винь Нгуен, Куанг; Лумбанская тюрьма, Форд (2011), Труды 2-го Международного конгресса по компьютерным приложениям и вычислительной науке 2011 г. , том. 2, Спрингер, стр. 465–469.
• Гауэр, Роберт; Рихтарик, Питер (2015a), «Рандомизированные итеративные методы для линейных систем», SIAM Journal on Matrix Analysis and Applications , 36 (4): 1660–1690, arXiv : 1506.03296 , doi : 10.1137/15M1025487 , S2CID   8215294
• Гауэр, Роберт; Рихтарик, Питер (2015b), «Стохастическое двойное восхождение для решения линейных систем», arXiv : 1512.06890 [ math.NA ]
• Бруст, Йоханнес Дж; Сондерс, Майкл А. (2023), «PLSS: проектируемый решатель линейных систем», SIAM Journal on Scientific Computing , 45 (2): A1012–A1037, arXiv : 2207.07615 , Bibcode : 2023SJSC...45A1012B , doi : 10.1137/22M1509783

Внешние ссылки

• [1] Рандомизированный алгоритм Качмажа с экспоненциальной сходимостью.
• [2] Комментарии к рандомизированному методу Качмажа.