Resumo Técnico: Aproximação de Nyström Riemanniana em Variedades

1. Declaração do Problema

Muitos problemas de grande escala em aprendizado de máquina e processamento de sinais são naturalmente formulados com restrições de variedade. Embora a estrutura da variedade permita uma modelagem fiel de geometrias complexas, as operações de álgebra linear associadas nos espaços tangentes frequentemente tornam-se gargalos computacionais, particularmente em cenários de alta dimensão.

Especificamente, métodos iterativos em variedades Riemannianas exigem frequentemente a construção de um operador no espaço tangente $H_x: T_xM \to T_xM$ (tipicamente auto-adjunto e semidefinido positivo, como o Hessiano Riemanniano) e o cálculo de sua inversa ou pseudoinversa. Exemplos incluem a resolução de sistemas lineares para otimização do tipo Newton e a realização de Análise Geodésica Principal (PGA) em tensores de covariância. A formação explícita e a inversão desses operadores são frequentemente proibitivas ou intratáveis. Técnicas existentes, como truncamento espectral, solucionadores multigrid e métodos Riemannianos quasi-Newton, tentam mitigar isso, mas levantam a questão de se é possível construir uma aproximação eficiente com limites de erro prováveis que preserve as propriedades geométricas intrínsecas do operador.

2. Metodologia

2.1 Aproximação de Nyström Riemanniana

Os autores propõem uma aproximação de Nyström Riemanniana livre de coordenadas para operadores auto-adjuntos e semidefinidos positivos (PSD) em uma variedade Riemanniana $(M, g)$ de dimensão $d$.

Dado um ponto $x \in M$ e um operador $H_x$, a aproximação $\hat{H}_{x, B, \Xi}$ é construída usando dois subespaços de dimensão $\ell$, $B, \Xi \subset T_xM$ (onde $\ell \leq d$) e um mapa linear de posto completo $F: B \to \Xi$.

1. Operador de Esboço (Sketching): Um operador de esboço $P_{x, B, \Xi}: T_xM \to T_xM$ é definido como $P_{x, B, \Xi}[v] = F \Pi_B [v]$, onde $\Pi_B$ é a projeção ortogonal sobre $B$. Seu adjunto é $P^*_{x, B, \Xi}[u] = F^* \Pi_\Xi [u]$.
2. Fórmula de Aproximação: A aproximação de Nyström Riemanniana é definida como:
   $$\hat{H}_{x, B, \Xi}[u] = \left( H_x P_{x, B, \Xi} (P^*_{x, B, \Xi} H_x P_{x, B, \Xi})^\dagger P^*_{x, B, \Xi} H_x \right)[u]$$
   onde $(\cdot)^\dagger$ denota a pseudoinversa de Moore–Penrose. Esta formulação efetivamente comprime o sistema linear no subespaço de baixa dimensão $B$, resolve-o ali e eleva o resultado de volta ao espaço tangente.

2.2 Condições de Esboço (Sketching)

Para permitir uma análise de erro aleatorizada, o artigo introduz duas condições de esboço:

• Esboço Gaussiano: Análogo ao caso Euclidiano, onde o mapa $F$ induz uma distribuição Gaussiana nos produtos internos.
• Esboço Haar–Grassmann: Uma condição nova e intrínseca definida diretamente em termos de geometria, sem depender de um sistema de coordenadas específico. Ela requer:
  1. O subespaço $\Xi$ ser Haar-uniforme na variedade Grassmann $\text{Gr}(\ell, T_xM)$.
  2. O componente isométrico da decomposição polar de $F$ ser Haar-uniforme no conjunto de isometrias lineares entre $B$ e $\Xi$.
  3. O fator radial de $F$ satisfazer limites específicos de momentos.

Esta condição é provada ser compatível com transporte: se um operador de esboço satisfaz a condição Haar–Grassmann em $x$, seu transporte para um ponto próximo $x'$ via transporte vetorial isométrico também satisfaz a condição. Isso permite estratégias de "atualização preguiçosa" (lazy refresh) em algoritmos iterativos, onde o esboço é transportado em vez de regenerado a cada passo.

2.3 Algoritmo de Otimização

Os autores propõem um método Newton Cúbico Riemanniano Nyström Aleatorizado (RRNCN).

• O Hessiano Riemanniano $H_x$ é substituído por sua aproximação de Nyström $\hat{H}_{x, B, \Xi}$.
• A direção de busca é computada resolvendo um sistema linear reduzido no subespaço $B$.
• Para garantir convergência global, o método incorpora regularização cúbica, resolvendo um subproblema da forma:
  $$\min_{v \in B} \left( \langle h, v \rangle_x + \frac{1}{2}\langle J[v], v \rangle_x + \frac{\sigma}{6}\|v\|_x^3 \right)$$
  onde $h$ e $J$ são os componentes do gradiente e do Hessiano esboçados.

3. Contribuições Principais

1. Construção Intrínseca: O desenvolvimento de uma aproximação de Nyström Riemanniana livre de coordenadas que preserva propriedades fundamentais do operador, incluindo semidefinição positiva, auto-adjunção e monotonicidade da ordem de Loewner.
2. Esboço Haar–Grassmann: A introdução de uma condição de esboço geométrica que generaliza o esboço Gaussiano para variedades. Esta condição é intrínseca, livre de coordenadas e compatível com transporte vetorial isométrico, abordando a falta de coordenadas canônicas em variedades.
3. Limites de Erro de Aproximação: O estabelecimento de limites de erro de aproximação espectral na norma do operador. Sob a condição Haar–Grassmann, o erro esperado é limitado por uma função dos autovalores de $H_x$ e do tamanho do esboço $\ell$. Especificamente, o erro depende da cauda do espectro e do "rank estável" do operador.
4. Compatibilidade com Transporte: Uma prova de que a condição Haar–Grassmann é preservada sob transporte vetorial isométrico, permitindo a reutilização eficiente de estruturas de esboço através de iterações em algoritmos de otimização.
5. Framework de Otimização: A proposta de um método do tipo Newton aleatorizado utilizando a aproximação de Nyström Riemanniana, acompanhado de análise de complexidade global ($O(d/(\ell \epsilon))$) e taxas de convergência linear local sob convexidade geodésica forte.

4. Resultados

O artigo valida a metodologia proposta através de experimentos numéricos em variedades Simétricas Definidas Positivas (SPD) e Grassmann.

• Análise Geodésica Principal (PGA): Experimentos no conjunto de dados HDM05 (matrizes SPD de tamanho $93 \times 93$) demonstram que a aproximação de Nyström preserva o desempenho estatístico a jusante.
  • Precisão: A precisão de classificação multiclasse (usando regressão logística, SVM e MLP) e as estatísticas $T^2$ de Hotelling permaneceram comparáveis à PGA exata através de tamanhos de esboço $\ell \in \{20, 40, 80\}$.
  • Eficiência: O método reduziu significativamente o uso de memória, exigindo apenas 4,30%–9,64% do aumento de memória associado ao operador exato, mantendo qualidade estatística competitiva.
• Otimização em Variedades SPD: Experimentos em um problema de otimização convexa geodésica para estimativa de covariância mostraram que tamanhos de esboço intermediários (por exemplo, $\ell=80$) ofereceram o melhor compromisso entre qualidade de aproximação e custo computacional por iteração, alcançando convergência mais rápida em tempo de relógio comparado ao método Newton cúbico exato.
• Esboço Transportado em Variedades Grassmann: Experimentos na variedade Grassmann ($n=20000, p=20$) demonstraram que o uso de esboço transportado (atualizando a cada 2–3 iterações) alcançou convergência quase idêntica em termos de iterações ao método de Nyström totalmente atualizado, mas forneceu acelerações significativas no tempo de execução ao evitar o custo de regenerar o esboço a cada passo.

5. Significado e Alegações

O artigo alega estender a teoria clássica de Nyström Euclidiana para o cenário de operadores no espaço tangente em variedades Riemannianas. Seu significado principal reside em fornecer uma técnica de aproximação de baixo rank que é intrinsecamente construída, preservando a estrutura geométrica (propriedade PSD, auto-adjunção) e oferecendo erros de aproximação prováveis sob uma condição de esboço geometricamente natural (Haar–Grassmann).

Os autores enfatizam que esta abordagem permite o cálculo eficiente de operadores no espaço tangente e suas inversas sem formar o operador completo, tornando a otimização e análise de variedades de alta dimensão (como a PGA) computacionalmente viáveis. A compatibilidade com transporte da condição de esboço é destacada como um facilitador chave para algoritmos iterativos práticos, reduzindo a sobrecarga computacional enquanto mantém garantias teóricas. O trabalho preenche a lacuna entre álgebra linear aleatorizada e otimização Riemanniana, oferecendo uma alternativa escalável a métodos exatos de segunda ordem.