Euclidean Distance Degrees in Macaulay2

Resumo Técnico: Grau de Distância Euclidiana em Macaulay2

Enunciado do Problema
O grau de distância euclidiana (ED degree) é um invariante fundamental na otimização algébrica, medindo a complexidade de problemas de ponto mais próximo para variedades algébricas reais. Especificamente, para um ponto de dados genérico $u \in \mathbb{R}^n$ e uma variedade $X \subseteq \mathbb{R}^n$, o grau ED é definido como o número de pontos críticos complexos não singulares da função de distância euclidiana ao quadrado $\|x - u\|^2$ (ou uma variante ponderada $\|x - u\|_w^2$) restrita a $X$. Embora muitos modelos científicos e de engenharia sejam expressos por sistemas polinomiais, as ferramentas para computar graus ED para variedades arbitrárias têm sido limitadas. Este artigo aborda a necessidade de uma implementação de software robusta capaz de computar esses graus utilizando técnicas de geometria algébrica simbólica e numérica.

Metodologia
Os autores introduzem o pacote EuclideanDistanceDegree para o sistema de álgebra computacional Macaulay2. O pacote implementa quatro abordagens algorítmicas distintas para computar graus ED, categorizadas pela natureza da variedade de entrada (implícita vs. parametrizada) e pela estratégia computacional (simbólica vs. numérica):

1. Método dos Menores (Simbólico):

   • Abordagem: Este método trata a variedade $X$ como uma variedade complexa definida por um ideal primo $I_X$. Ele constrói uma matriz Jacobiana aumentada $\hat{J}$ anexando um vetor linha derivado do gradiente da distância ponderada à matriz Jacobiana $J$ padrão dos polinômios definidores.
   • Computação: O ideal crítico ponderado é computado via saturação: $C_{X,u,w} = (I_X + \text{menores}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$.
   • Saída: O grau deste ideal fornece o grau ED. Esta abordagem é implementada simbolicamente e pode retornar as equações explícitas do ideal crítico.

2. Método do Núcleo à Esquerda (Numérico/Interseções Completas):

   • Abordagem: Projetado para variedades de grande codimensão onde o método dos menores é computacionalmente proibitivo devido ao passo de saturação e à explosão de menores. Utiliza multiplicadores de Lagrange para resolver diretamente as equações dos pontos críticos.
   • Computação: Para uma interseção completa definida por $f_1, \dots, f_k$, o sistema $G(x, \lambda) = 0$ é formado, combinando os polinômios definidores com a condição do multiplicador de Lagrange $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$.
   • Implementação: Este sistema é resolvido numericamente usando o pacote de software Bertini via continuação de homotopia.

3. Método de Homotopia (Numérico/Além de Interseções Completas):

   • Abordagem: Uma extensão do método do núcleo à esquerda adequada para variedades que não são interseções completas ou para explorar pesos parametrizados.
   • Computação: Emprega um processo de continuação de homotopia de dois estágios. Primeiro, um "sistema inicial" é resolvido usando pesos genéricos para estabelecer um limite inicial para o grau ED. Segundo, uma homotopia de parâmetros rastreia essas soluções para o sistema alvo (pesos ou dados específicos).
   • Eficiência: Isso permite a computação eficiente de graus ED para múltiplas configurações de peso ou dados, pois o estágio inicial precisa ser executado apenas uma vez.

4. Método das Variedades Conormais (Parametrizada):

   • Abordagem: Voltado para variedades dadas por uma parametrização $\phi: \mathbb{C}^d \to \mathbb{C}^n$.
   • Computação: Constrói uma variedade conormal afim encontrando o núcleo da matriz Jacobiana transposta da parametrização. Os pontos críticos são identificados como pares $(x, \lambda)$ que satisfazem um sistema linear específico envolvendo a parametrização e os geradores do núcleo.
   • Implementação: Isso pode ser computado simbolicamente ou numericamente usando o pacote MonodromySolver.

Principais Contribuições

• Pacote de Software: A principal contribuição é o pacote EuclideanDistanceDegree para Macaulay2, que unifica métodos simbólicos e numéricos para a computação do grau ED.
• Diversidade Algorítmica: O pacote fornece implementações para quatro métodos distintos (Menores, Núcleo à Esquerda, Homotopia, Conormal), permitindo que os usuários selecionem a ferramenta mais apropriada com base na estrutura da variedade (ex: codimensão, implícita vs. parametrizada) e no resultado desejado (ex: grau simbólico exato vs. aproximação numérica).
• Interoperabilidade: Os métodos simbólicos incluem uma opção para retornar os polinômios geradores do ideal crítico, facilitando a replicação e a validação cruzada com outro software como HomotopyContinuation.jl.
• Robustez Numérica: O pacote integra-se com o Bertini e o MonodromySolver, oferecendo opções de configuração para lidar com falhas de caminho (ex: caminhos divergindo para o infinito) e suportando cálculos de grau ED unitário, ponderado e genérico.

Resultados e Exemplos
O artigo valida o pacote através de uma gama de exemplos:

• Verificação Simbólica: O pacote computa com sucesso o grau ED unitário (5) e o grau ED genérico (9) para a superfície Dingdong, recuperando as equações do ideal crítico.
• Computação Numérica: Computa o grau ED ponderado (22) para a superfície Daisy usando dados e pesos específicos.
• Eficiência de Homotopia: O pacote demonstra que, após computar um grau ED unitário, os graus ED genéricos subsequentes podem ser computados eficientemente reutilizando o estágio inicial de homotopia. Um experimento em uma elipse produz um grau ED real médio de aproximadamente 3,41 sobre 100 amostras, consistente com as expectativas teóricas.
• Aplicações:
  • Redes Neurais Polinomiais: O pacote computa o grau ED genérico para redes neurais polinomiais rasas (ex: grau 13 para arquiteturas específicas), seguindo trabalhos anteriores sobre neurovariedades.
  • Variedades Multiview: Computa graus ED para variedades multiview afins ancoradas em superfícies racionais, encontrando graus de 8 e 12 para configurações específicas, fornecendo evidência empírica para potenciais generalizações de resultados conhecidos para curvas racionais.

Significância
O artigo posiciona o pacote EuclideanDistanceDegree como uma ferramenta especializada que preenche uma lacuna no cenário da geometria algébrica computacional. Enquanto existem pacotes simbólicos gerais (como AlgebraicOptimization ou ToricInvariants) para configurações específicas, e solvers de homotopia gerais (como Bertini ou PHCpack) para resolução numérica, este pacote oferece uma interface dedicada e amigável especificamente para graus ED. Ele faz a ponte entre a exatidão simbólica e a escalabilidade numérica, permitindo que pesquisadores em otimização algébrica, visão computacional e aprendizado de máquina compreendam melhor a complexidade algébrica de seus modelos ao computar esses invariantes críticos. Os autores observam que, embora nenhum pacote numérico dedicado de ED existisse anteriormente, sua ferramenta aproveita solvers robustos existentes para fornecer um fluxo de trabalho simplificado para esses problemas específicos.