WikiDer > Качмарц метод

В Качмарц метод или же Алгоритм Качмарца является итерационный алгоритм для решения системы линейных уравнений ${ displaystyle Ax = b}$. Впервые его открыл польский математик. Стефан Качмарц,^[1] и был заново открыт в области реконструкции изображений по проекциям Ричард Гордон, Роберт Бендер и Габор Герман в 1970 году, где он называется Алгебраическая реконструкция (ИЗОБРАЗИТЕЛЬНОЕ ИСКУССТВО).^[2] ART включает ограничение положительности, что делает его нелинейным.^[3]

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

Он имеет множество приложений, начиная от компьютерная томография (CT) в обработка сигналов. Его можно получить также, применяя к гиперплоскостям, описываемым линейной системой, метод последовательных проекции на выпуклые множества (POCS).^[5][6]

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

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

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

(1)

куда ${ Displaystyle я = к { bmod {м}}, я = 1,2, ldots м}$ и ${ displaystyle { overline {a_ {i}}}}$ обозначает комплексное сопряжение из ${ displaystyle a_ {i}}$.

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

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

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

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

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

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

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

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

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

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

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

У нас есть

${ displaystyle 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)

С помощью

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

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

${ displaystyle 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) как ожидание некоторой случайной величины. А именно, напомним, что пространство решений ${ displaystyle j-th}$ уравнение ${ displaystyle Ax = b}$ это гиперплоскость

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

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

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

Потом (3) Говорит, что

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

(4)

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

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

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

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

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

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

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

${ Displaystyle | x_ {k} -x | ^ {2} = 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}}.}$

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

${ displaystyle 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) и независимость,

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

Принимая во внимание ожидания обеих сторон, мы заключаем, что

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

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

Итерация Качмара (1) имеет чисто геометрическую интерпретацию: алгоритм последовательно проецирует текущую итерацию на гиперплоскость, определяемую следующим уравнением. Следовательно, любое масштабирование уравнений не имеет значения; это также видно из (1), что любое (ненулевое) масштабирование уравнений сокращается. Таким образом, в РК можно использовать ${ Displaystyle | а_ {я} |}$ или любые другие веса, которые могут иметь значение. В частности, в вышеупомянутом примере реконструкции уравнения были выбраны с вероятностью, пропорциональной среднему расстоянию каждой точки выборки от двух ее ближайших соседей - концепция, введенная Файхтингер и Gröchenig. Для получения дополнительной информации по этой теме см.^[12][13] и ссылки в нем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${ displaystyle x ^ {k + 1} = { underset {x} { operatorname {arg min}}} | xx ^ {k} | _ {B} { text {при условии}} S ^ {T} Ax = S ^ {T} b.}$

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

2. Ограничение и приближение

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

${ displaystyle x ^ {k + 1} = { underset {x} { operatorname {arg min}}} left | xx ^ {*} right | _ {B} { text {при условии }} x = x ^ {k} + B ^ {- 1} A ^ {T} Sy,}$

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

${ displaystyle left {h: h = B ^ {- 1} A ^ {T} Sy, quad y { text {может варьироваться}} right },}$

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

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

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

${ displaystyle 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),}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Гауэр и Рихтарик^[14] покажи это

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

где матричная норма определяется как

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

Более того, без каких-либо предположений о ${ displaystyle S}$ надо ${ Displaystyle 0 Leq Rho Leq 1.}$ Взяв нормы и развернув рекуррентность, получим

Теорема [Гауэр и Ричтарик, 2015]

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

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

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

Теорема [Гауэр и Ричтарик, 2015]

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

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

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

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

Сходимость рандомизированного Качмара

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

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

Другие особые случаи

Примечания

Рекомендации

• Качмарц, Стефан (1937), "Angenäherte Auflösung von Systemen linearer Gleichungen" (PDF), Международный бюллетень полонезной академии наук и литературы. Classe des Sciences Mathématiques et Naturelles. Серия А, Математические науки, 35, стр. 355–357
• Чонг, Эдвин К. П .; Зак, Станислав Х. (2008), Введение в оптимизацию (3-е изд.), John Wiley & Sons, стр. 226–230.
• Гордон, Ричард; Бендер, Роберт; Герман, Габор (1970), «Методы алгебраической реконструкции (ART) для трехмерной электронной микроскопии и рентгеновской фотографии», Журнал теоретической биологии, 29 (3): 471–481, Дои:10.1016/0022-5193(70)90109-8, PMID 5492997
• Гордон, Ричард (2011), Остановите рак груди сейчас же! Представление способов визуализации для поиска, уничтожения, лечения и бдительного ожидания рака груди до метастазирования. В: Рак молочной железы - болезнь долей, редактор: Тибор Тот, Springer, стр. 167–203.
• Герман, Габор (2009), Основы компьютерной томографии: Восстановление изображения по проекции. (2-е изд.), Springer
• Цензор, Яир; Зениос, С.А. (1997), Параллельная оптимизация: теория, алгоритмы и приложения, Нью-Йорк: Издательство Оксфордского университета.
• Астер, Ричард; Борчерс, Брайан; Тербер, Клиффорд (2004), Оценка параметров и обратные задачи, Эльзевьер
• Стромер, Томас; Вершинин, Роман (2009), «Рандомизированный алгоритм Качмарца для линейных систем с экспоненциальной сходимостью» (PDF), Журнал анализа Фурье и приложений, 15 (2): 262–278, Дои:10.1007 / s00041-008-9030-4
• Ниделл, Дина; Уорд, Рэйчел; Сребро, Нати (2015), «Стохастический градиентный спуск, взвешенная выборка и рандомизированный алгоритм Качмарца», Математическое программирование, 155: 549–573, arXiv:1310.5715, Дои:10.1007 / s10107-015-0864-7
• Цензор Яир; Герман, Габор; Цзян, М. (2009), «Заметка о поведении рандомизированного алгоритма Качмарца Штромера и Вершинина», Журнал анализа Фурье и приложений, 15 (4): 431–436, Дои:10.1007 / s00041-009-9077-х, ЧВК 2872793, PMID 20495623
• Стромер, Томас; Вершинин, Роман (2009b), «Комментарии к рандомизированному методу Качмарца», Журнал анализа Фурье и приложений, 15 (4): 437–440, Дои:10.1007 / s00041-009-9082-0
• Басс, Ричард Ф.; Gröchenig, Karlheinz (2013), «Соответствующая выборка функций с ограниченной полосой пропускания», Иллинойсский журнал математики, 57 (1): 43–58
• Гордон, Дэн (2017), «Дерандомизационный подход к восстановлению сигналов с ограниченной полосой пропускания в широком диапазоне случайных частот дискретизации», Численные алгоритмы, Дои:10.1007 / s11075-017-0356-3
• Винь Нгуен, Куанг; Лумбанская тюрьма, Форд (2011), Материалы 2-го Международного конгресса по компьютерным приложениям и вычислительным наукам, 2011 г., 2, Springer, стр. 465–469.
• Гауэр, Роберт; Рихтарик, Питер (2015), «Рандомизированные итерационные методы для линейных систем», Журнал SIAM по матричному анализу и приложениям, 36 (4): 1660–1690, arXiv:1506.03296, Дои:10.1137 / 15M1025487
• Гауэр, Роберт; Рихтарик, Питер (2015), «Стохастическое двойное восхождение для решения линейных систем», arXiv:1512.06890 [math.NA]

внешняя ссылка

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