Método Kaczmarz - Kaczmarz method

O método de Kaczmarz ou algoritmo de Kaczmarz é um algoritmo iterativo para resolver sistemas de equações lineares . Foi descoberto pela primeira vez pelo matemático polonês Stefan Kaczmarz e foi redescoberto no campo da reconstrução de imagens a partir de projeções de Richard Gordon , Robert Bender e Gabor Herman em 1970, onde é chamado de Técnica de Reconstrução Algébrica (ART). O ART inclui a restrição de positividade, tornando-o não linear. ${\ displaystyle Ax = b}$

O método de Kaczmarz é aplicável a qualquer sistema linear de equações, mas sua vantagem computacional em relação a outros métodos depende do sistema ser esparso . Foi demonstrado que é superior, em algumas aplicações de imagem biomédica, a outros métodos, como o método de retroprojeção filtrada .

Ele tem muitas aplicações, desde tomografia computadorizada (TC) até processamento de sinais . Pode ser obtido também aplicando aos hiperplanos, descritos pelo sistema linear, o método das projeções sucessivas sobre conjuntos convexos (POCS).

Algoritmo 1: algoritmo de Kaczmarz

Seja um sistema de equações lineares , seja o número de linhas de A , seja a ésima linha da matriz de valor complexo , e seja uma aproximação inicial arbitrária de valor complexo para a solução de . Para computação: ${\ displaystyle Ax = b}$${\ displaystyle m}$${\ displaystyle a_ {i}}$${\ displaystyle i}$ ${\ displaystyle A}$${\ displaystyle x ^ {0}}$${\ displaystyle Ax = b}$${\ displaystyle k = 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 )

onde e denota a conjugação complexa de . ${\ displaystyle i = k {\ bmod {m}}, i = 1,2, \ ldots m}$${\ displaystyle {\ overline {a_ {i}}}}$${\ displaystyle a_ {i}}$

Se o sistema for consistente, converge para a solução da norma mínima , desde que as iterações comecem com o vetor zero. ${\ displaystyle x ^ {k}}$

Um algoritmo mais geral pode ser definido usando um parâmetro de relaxamento${\ 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}}}}$

Existem versões do método que convergem para uma solução regularizada de mínimos quadrados ponderados quando aplicada a um sistema de equações inconsistentes e, pelo menos no que diz respeito ao comportamento inicial, a um custo menor do que outros métodos iterativos, como o método do gradiente conjugado .

Algoritmo 2: algoritmo de Kaczmarz aleatório

Em 2009, uma versão aleatória do método de Kaczmarz para sistemas lineares sobredeterminados foi introduzida por Thomas Strohmer e Roman Vershynin em que a i- ésima equação é selecionada aleatoriamente com probabilidade proporcional a${\ displaystyle \ | a_ {i} \ | ^ {2}.}$

Este método pode ser visto como um caso particular de descida gradiente estocástica .

Sob tais circunstâncias converge exponencialmente rápido para a solução de e a taxa de convergência depende apenas do número da condição em escala . ${\ displaystyle x_ {k}}$${\ displaystyle Ax = b,}$ ${\ displaystyle \ kappa (A)}$

Teorema. Seja a solução de Então o Algoritmo 2 converge para na expectativa, com o erro médio: ${\ displaystyle x}$${\ displaystyle Ax = b.}$${\ displaystyle x}$

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

Prova

Nós temos

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

Usando

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

podemos escrever ( 2 ) como

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

O ponto principal da prova é ver o lado esquerdo em ( 3 ) como uma expectativa de alguma variável aleatória. Ou seja, lembre-se de que o espaço de solução da equação de é o hiperplano ${\ displaystyle j-th}$${\ displaystyle Ax = b}$

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

cujo normal é Defina um vetor aleatório Z cujos valores são os normais para todas as equações de , com probabilidades como em nosso algoritmo: ${\ displaystyle {\ tfrac {a_ {j}} {\ | a_ {j} \ | ^ {2}}}.}$${\ displaystyle Ax = b}$

${\ displaystyle Z = {\ frac {a_ {j}} {\ | a_ {j} \ |}}}$ com probabilidade ${\ displaystyle {\ frac {\ | a_ {j} \ | ^ {2}} {\ | A \ | ^ {2}}} \ qquad \ qquad \ qquad j = 1, \ ldots, m}$

Então ( 3 ) diz que

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

( 4 )

A projeção ortogonal no espaço de solução de uma equação aleatória de é dada por${\ displaystyle P}$${\ displaystyle Ax = b}$${\ displaystyle Pz = z- \ langle zx, Z \ rangle Z.}$

Agora estamos prontos para analisar nosso algoritmo. Queremos mostrar que o erro diminui em cada etapa média (condicionado nas etapas anteriores) por, pelo menos, o factor de A seguinte aproximação é calculado a partir de onde são realizações independentes da projecção aleatória O vector é no núcleo de É ortogonal ao espaço de solução da equação na qual se projeta, que contém o vetor (lembre-se de que é a solução para todas as equações). A ortogonalidade desses dois vetores, então, produz ${\ displaystyle {\ | x_ {k} -x \ | ^ {2}}}$${\ displaystyle (1- \ kappa (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}.}$

Para completar a prova, temos que limitar a partir de baixo. Pela definição de , temos ${\ displaystyle \ | x_ {k-1} -x_ {k} \ | ^ {2}}$${\ displaystyle x_ {k}}$

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

onde estão realizações independentes do vetor aleatório${\ displaystyle Z_ {1}, Z_ {2}, \ ldots}$${\ displaystyle Z.}$

Desse modo

${\ 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}}.}$

Agora consideramos a expectativa de ambos os lados condicional à escolha dos vetores aleatórios (portanto, fixamos a escolha das projeções aleatórias e, portanto, dos vetores aleatórios e fazemos a média sobre o vetor aleatório ). Então ${\ 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}}.}$

Por ( 4 ) e pela independência,

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

Tomando toda a expectativa de ambos os lados, concluímos que

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

A superioridade dessa seleção foi ilustrada com a reconstrução de uma função limitada em banda a partir de seus valores de amostragem não uniformemente espaçados. No entanto, foi apontado que o sucesso relatado por Strohmer e Vershynin depende das escolhas específicas que foram feitas lá na tradução do problema subjacente, cuja natureza geométrica é encontrar um ponto comum de um conjunto de hiperplanos , em um sistema algébrico equações. Sempre haverá representações algébricas legítimas do problema subjacente para o qual o método de seleção em terá um desempenho inferior.

A iteração de Kaczmarz ( 1 ) tem uma interpretação puramente geométrica: o algoritmo projeta sucessivamente a iteração atual no hiperplano definido pela próxima equação. Portanto, qualquer escala das equações é irrelevante; também pode ser visto em ( 1 ) que qualquer escala (diferente de zero) das equações se cancela. Assim, em RK, pode-se usar ou quaisquer outros pesos que possam ser relevantes. Especificamente, no exemplo de reconstrução mencionado acima, as equações foram escolhidas com probabilidade proporcional à distância média de cada ponto de amostra de seus dois vizinhos mais próximos - um conceito introduzido por Feichtinger e Gröchenig . Para obter mais informações sobre o progresso neste tópico, consulte e as referências nele contidas. ${\ displaystyle \ | a_ {i} \ |}$

Algoritmo 3: algoritmo de Gower-Richtarik

Em 2015, Robert M. Gower e Peter Richtarik desenvolveram um método iterativo aleatório versátil para resolver um sistema consistente de equações lineares que inclui o algoritmo de Kaczmarz aleatório como um caso especial. Outros casos especiais incluem descida coordenada aleatória, descida gaussiana aleatória e método de Newton aleatório. Versões em bloco e versões com amostragem de importância de todos esses métodos também surgem como casos especiais. O método é mostrado para desfrutar de decaimento da taxa exponencial (na expectativa) - também conhecido como convergência linear, sob condições muito suaves na forma como a aleatoriedade entra no algoritmo. O método Gower-Richtarik é o primeiro algoritmo a descobrir uma relação de "irmãos" entre esses métodos, alguns dos quais foram propostos independentemente antes, enquanto muitos dos quais eram novos. ${\ displaystyle Ax = b}$

Insights sobre Randomized Kaczmarz

Novos insights interessantes sobre o método de Kaczmarz aleatório que podem ser obtidos a partir da análise do método incluem:

• A taxa geral do algoritmo de Gower-Richtarik recupera com precisão a taxa do método de Kaczmarz aleatório no caso especial quando se reduz a ele.
• A escolha das probabilidades para as quais o algoritmo de Kaczmarz aleatório foi originalmente formulado e analisado (probabilidades proporcionais aos quadrados das normas da linha) não é ótima. Probabilidades ótimas são a solução de um determinado programa semidefinido. A complexidade teórica de Kaczmarz randomizado com as probabilidades ótimas pode ser arbitrariamente melhor do que a complexidade para as probabilidades padrão. No entanto, o quanto ele é melhor depende da matriz . Existem problemas para os quais as probabilidades padrão são ótimas.${\ displaystyle A}$
• Quando aplicado a um sistema com matriz que é definida positiva, o método de Kaczmarz Randomizado é equivalente ao método Stochastic Gradient Descent (SGD) (com um tamanho de passo muito especial) para minimizar a função quadrática fortemente convexa. Observe que, como é convexo, os minimizadores de devem satisfazer , que é equivalente a O "tamanho do passo especial" é o tamanho do passo que leva a um ponto que, na linha unidimensional percorrida pelo gradiente estocástico, minimiza a distância euclidiana do minimizador desconhecido (!) de , a saber, de Este insight é obtido a partir de uma visão dupla do processo iterativo (descrito abaixo como "Ponto de vista da otimização: restrição e aproximação").${\ displaystyle A}$${\ displaystyle f (x) = {\ tfrac {1} {2}} x ^ {T} Ax-b ^ {T} x.}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle \ nabla f (x) = 0}$${\ displaystyle Ax = b.}$${\ displaystyle f}$${\ displaystyle x ^ {*} = A ^ {- 1} b.}$

Seis Formulações Equivalentes

O método Gower-Richtarik goza de seis formulações aparentemente diferentes, mas equivalentes, lançando luz adicional sobre como interpretá-lo (e, como consequência, como interpretar suas muitas variantes, incluindo Kaczmarz randomizado):

• 1. Ponto de vista do esboço: esboço e projeto
• 2. Ponto de vista de otimização: Restringir e aproximar
• 3. Ponto de vista geométrico: intersecção aleatória
• 4. Ponto de vista algébrico 1: solução linear aleatória
• 5. Ponto de vista algébrico 2: atualização aleatória
• 6. Ponto de vista analítico: Ponto Fixo Aleatório

Descrevemos agora alguns desses pontos de vista. O método depende de 2 parâmetros:

• uma matriz definida positiva dando origem a um produto interno euclidiano ponderado e a norma induzida${\ displaystyle B}$${\ displaystyle \ langle x, y \ rangle _ {B}: = x ^ {T} Por}$

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

• e uma matriz aleatória com tantas linhas quanto (e possivelmente um número aleatório de colunas).${\ displaystyle S}$${\ displaystyle A}$

1. Esboço e Projeto

Dada a iteração anterior, o novo ponto é calculado desenhando uma matriz aleatória (de uma forma iid a partir de alguma distribuição fixa) e definindo ${\ displaystyle x ^ {k},}$${\ displaystyle x ^ {k + 1}}$${\ displaystyle S}$

${\ displaystyle x ^ {k + 1} = {\ underset {x} {\ operatorname {arg \ min}}} \ | xx ^ {k} \ | _ {B} {\ text {sujeito a}} S ^ {T} Ax = S ^ {T} b.}$

Ou seja, é obtido como a projeção de no sistema esboçado aleatoriamente . A ideia por trás deste método é escolher de forma que uma projeção no sistema esboçado seja substancialmente mais simples do que a solução do sistema original . O método de Kaczmarz randomizado é obtido escolhendo- se ser a matriz de identidade e o vetor de coordenadas unitárias com probabilidade. Diferentes escolhas e levar a diferentes variantes do método. ${\ displaystyle x ^ {k + 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. Restringir e aproximar

Uma formulação do método aparentemente diferente, mas totalmente equivalente (obtida por meio da dualidade de Lagrange) é

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

onde também pode variar, e onde está qualquer solução do sistema Portanto, é obtido primeiro restringindo a atualização para o subespaço linear estendido pelas colunas da matriz aleatória , ou seja, para ${\ displaystyle y}$${\ displaystyle x ^ {*}}$${\ displaystyle Ax = b.}$${\ displaystyle x ^ {k + 1}}$${\ displaystyle B ^ {- 1} A ^ {T} S}$

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

e então escolher o ponto deste subespaço que melhor se aproxima . Esta formulação pode parecer surpreendente, pois parece impossível realizar a etapa de aproximação devido ao fato de que não é conhecido (afinal, é isso que estamos tentando calcular!). No entanto, ainda é possível fazer isso, simplesmente porque computado desta forma é o mesmo que computado via esboço e formulação do projeto e já que não aparece lá. ${\ displaystyle x}$${\ displaystyle x ^ {*}}$${\ displaystyle x ^ {*}}$${\ displaystyle x ^ {k + 1}}$${\ displaystyle x ^ {k + 1}}$${\ displaystyle x ^ {*}}$

5. Atualização aleatória

A atualização também pode ser escrita explicitamente como

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

onde por denotamos a pseudo-inversa de Moore-Penrose da matriz . Portanto, o método pode ser escrito na forma , onde é um vetor de atualização aleatório . ${\ displaystyle M ^ {\ dagger}}$${\ displaystyle M}$${\ displaystyle x ^ {k + 1} = x ^ {k} + h ^ {k}}$${\ displaystyle h ^ {k}}$

Deixando que se mostre que o sistema sempre tem uma solução , e que para todas essas soluções o vetor é o mesmo. Portanto, não importa qual dessas soluções é escolhida, e o método também pode ser escrito como . O pseudo-inverso leva apenas a uma solução particular. O papel do pseudo-inverso é duplo: ${\ displaystyle M = S ^ {T} AB ^ {- 1} A ^ {T} S,}$${\ displaystyle My = S ^ {T} (Ax ^ {k} -b)}$${\ displaystyle y ^ {k}}$${\ displaystyle x ^ {k + 1} -B ^ {- 1} A ^ {T} Sy ^ {k}}$${\ displaystyle x ^ {k + 1} = x ^ {k} -B ^ {- 1} A ^ {T} Sy ^ {k}}$

• Ele permite que o método seja escrito na forma explícita de "atualização aleatória" como acima,
• Isso torna a análise simples por meio da sexta formulação final.

6. Ponto Fixo Aleatório

Se subtrairmos de ambos os lados da fórmula de atualização aleatória, denote ${\ displaystyle x ^ {*}}$

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

e usar o fato de que chegamos à última formulação: ${\ displaystyle Ax ^ {*} = b,}$

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

onde está a matriz de identidade. A matriz de iteração, é aleatória, daí o nome desta formulação. ${\ displaystyle I}$${\ displaystyle IB ^ {- 1} Z,}$

Convergência

Ao tomar as expectativas condicionais na 6ª formulação (condicional em ), obtemos ${\ displaystyle x ^ {k}}$

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

Tomando a expectativa novamente e usando a propriedade da torre das expectativas, obtemos

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

Gower e Richtarik mostram que

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

onde a norma da matriz é definida por

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

Além disso, sem quaisquer suposições sobre alguém, tomando as normas e desenrolando a recorrência, obtemos ${\ displaystyle S}$${\ displaystyle 0 \ leq \ rho \ leq 1.}$

Teorema [Gower & Richtarik 2015]

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

Observação . Uma condição suficiente para os resíduos esperados convergirem para 0 é Isso pode ser alcançado se tiver uma classificação de coluna completa e sob condições muito suaves A convergência do método pode ser estabelecida também sem a suposição de classificação de coluna completa de uma maneira diferente. ${\ displaystyle \ rho <1.}$${\ displaystyle A}$${\ displaystyle S.}$

Também é possível mostrar um resultado mais forte:

Teorema [Gower & Richtarik 2015]

As normas quadradas esperadas (em vez de normas de expectativas) convergem na mesma taxa:

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

Observação . Este segundo tipo de convergência é mais forte devido à seguinte identidade que vale para qualquer vetor aleatório e qualquer vetor fixo : ${\ displaystyle x}$${\ displaystyle x ^ {*}}$

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

Convergência de Kaczmarz Randomizado

Vimos que o método de Kaczmarz aleatório aparece como um caso especial do método de Gower-Richtarik para e sendo o vetor de coordenadas unitárias com probabilidade onde está a linha de Pode ser verificado por cálculo direto que ${\ 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}}}.}$

Outros Casos Especiais

Notas

Referências

• Kaczmarz, Stefan (1937), "Angenäherte Auflösung von Systemen linearer Gleichungen" (PDF) , Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques , 35 , pp. 355-357
• Chong, Edwin KP; Zak, Stanislaw H. (2008), An Introduction to Optimization (3ª ed.), John Wiley & Sons, pp. 226–230
• Gordon, Richard ; Bender, Robert ; Herman, Gabor (1970), "Técnicas de reconstrução algébrica (ART) para microscopia eletrônica tridimensional e fotografia de raios-x", Journal of Theoretical Biology , 29 (3): 471-481, doi : 10.1016 / 0022-5193 (70) 90109 -8 , PMID  5492997
• Gordon, Richard (2011), Pare o câncer de mama agora! Imaginando caminhos de imagem para pesquisar, destruir, curar e esperar vigilante do câncer de mama pré-metástase. In: Breast Cancer - A Lobar Disease, editor: Tibor Tot , Springer, pp. 167–203
• Herman, Gabor (2009), Fundamentals of computerized tomography: Image reconstruction from projection (2ª ed.), Springer, ISBN 9781846287237
• Censor, Yair ; Zenios, SA (1997), Otimização paralela: teoria, algoritmos e aplicações , Nova York: Oxford University Press
• Aster, Richard; Borchers, Brian; Thurber, Clifford (2004), Parameter Estimation and Inverse Problems , Elsevier
• Strohmer, Thomas; Vershynin, Roman (2009), "A randomized Kaczmarz algorithm for linear systems with exponential convergence" (PDF) , Journal of Fourier Analysis and Applications , 15 (2): 262-278, arXiv : math / 0702226 , doi : 10.1007 / s00041 -008-9030-4 , S2CID  1903919
• Needell, Deanna; Ward, Rachel; Srebro, Nati (2015), "Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm", Mathematical Programming , 155 (1-2): 549-573, arXiv : 1310.5715 , doi : 10.1007 / s10107-015-0864- 7 , S2CID  2370209
• Censor, Yair; Herman, Gabor ; Jiang, M. (2009), "Uma nota sobre o comportamento do algoritmo de Kaczmarz aleatório de Strohmer and Vershynin", Journal of Fourier Analysis and Applications , 15 (4): 431-436, doi : 10.1007 / s00041-009-9077 -x , PMC  2872793 , PMID  20495623
• Strohmer, Thomas; Vershynin, Roman (2009b), "Comments on the randomized Kaczmarz method", Journal of Fourier Analysis and Applications , 15 (4): 437–440, doi : 10.1007 / s00041-009-9082-0 , S2CID  14806325
• Bass, Richard F .; Gröchenig, Karlheinz (2013), "Relevant sampling of band-limited functions", Illinois Journal of Mathematics , 57 (1): 43–58, arXiv : 1203.0146 , doi : 10.1215 / ijm / 1403534485 , S2CID  42705738
• Gordon, Dan (2017), "A derandomization approach to recovery bandlimited signs across a wide range of random sampling rates", Numerical Algorithms , 77 (4): 1141–1157, doi : 10.1007 / s11075-017-0356-3 , S2CID  1794974
• Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Proceedings of the 2011 2nd International Congress on Computer Applications and Computational Science , 2 , Springer, pp. 465-469
• Gower, Robert; Richtarik, Peter (2015), "Randomized iterative methods for linear systems", SIAM Journal on Matrix Analysis and Applications , 36 (4): 1660–1690, arXiv : 1506.03296 , doi : 10.1137 / 15M1025487 , S2CID  8215294
• Gower, Robert; Richtarik, Peter (2015), "Stochastic dual ascent for solving linear systems", arXiv : 1512.06890 [ math.NA ]

links externos

• [1] Um algoritmo de Kaczmarz aleatório com convergência exponencial
• [2] Comentários sobre o método de Kaczmarz randomizado