Resumo Técnico: Problemas de Proximidade de Matrizes Generalizadas II

Definição do Problema

Este artigo estende o estudo dos problemas de proximidade de matrizes generalizadas, originalmente abordados em [13]. O problema fundamental busca uma matriz $X$ que minimize a distância a uma matriz dada $A$ sob restrições específicas. A forma generalizada considerada aqui envolve três matrizes dadas $A, B, C$ e minimiza a função objetivo:
$$\min_{X \in S} \|A - BXC\|$$
onde $S$ representa um conjunto viável definido por várias restrições (por exemplo, posto, norma, simetria, estrutura, positividade). O artigo investiga especificamente três extensões à formulação padrão da norma de Frobenius ($\|\cdot\|_F$) encontrada em [13]:

1. Termos Afins: Incorporação de termos afins, como $dx^TE$ ou $Dxe^T$, na função objetivo.
2. Produtos de Kronecker: Substituição de produtos matriciais padrão por produtos de Kronecker (por exemplo, $B \otimes X \otimes C$) e generalização de restrições de posto para posto de Kronecker.
3. Normas de Schatten: Generalização da norma de Frobenius para normas arbitrariamente invariantes ortogonalmente, especificamente as normas de Schatten $p$ ($\|\cdot\|_{\sigma,p}$).

Metodologia

O artigo emprega uma abordagem dual: derivar soluções de forma fechada para casos específicos e desenvolver um algoritmo iterativo de ordem zero para o caso geral.

1. Soluções de Forma Fechada

Os autores identificam quatro variantes específicas do problema que admitem soluções de forma fechada, estendendo os resultados de [13]:

• Proximidade Generalizada Afim: Problemas envolvendo termos como $\|A - BXC + Dxe^T\|_F$. Estes são transformados em problemas de proximidade de matrizes generalizados padrão usando operadores de projeção (Proposição 3.2).
• Produto de Kronecker Separável: Minimização de $\|A - B \otimes X \otimes C\|_F$. Isto é resolvido introduzindo um operador de reorganização $R$ que transforma a estrutura de Kronecker em um problema padrão de proximidade de matrizes (Proposição 3.3).
• Posto de Kronecker Generalizado: Minimização de $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ sujeito a $\text{rank}_\otimes(X) \le r$. Isto reduz-se a um problema padrão com restrição de posto via operador de reorganização e propriedades da decomposição em valores singulares (SVD) de produtos de Kronecker (Proposição 3.4, Algoritmo 1).
• Rastros Parciais Prescritos: Minimização de $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ sujeita a uma restrição de rastro parcial $\text{tr}_P(X(W \otimes I)) = \lambda W$. Isto é reduzido a um problema de autovalor prescrito ou a um problema com restrição de posto (Proposição 3.5, Corolário 3.6).

2. Inexistência de Resultados do Tipo Mirsky

O artigo investiga se o teorema de Eckart–Young–Mirsky (que afirma que a melhor aproximação de posto-$r$ é independente da norma invariantemente ortogonalmente utilizada) se estende ao problema generalizado $\min_{\text{rank}(X) \le r} \|A - BXC\|$.

• Resultado: Os autores provam que nenhum resultado do tipo Mirsky se aplica quando $B$ e $C$ não são matrizes identidade.
• Evidência: Através de um contraexemplo (Exemplo 4.2), eles demonstram que o minimizador para o problema generalizado com restrição de posto depende da norma de Schatten específica ($p=1, 2, \infty$) escolhida. Isto contrasta com o problema padrão de aproximação de posto, onde a solução é universal em todas as normas invariantes ortogonalmente.

3. Algoritmo Iterativo (Algoritmo 3)

Para casos onde soluções de forma fechada não existem (especificamente para normas de Schatten gerais e restrições complexas), os autores propõem um algoritmo iterativo baseado no método de projeção de Dykstra (Algoritmo 2), especializado para normas de Schatten (Algoritmo 3).

• Mecanismo: O algoritmo alterna entre dois passos:
  1. Atualização de $X$: Resolve um problema de proximidade de matrizes generalizado na norma de Frobenius (usando métodos de [13] ou as soluções de forma fechada derivadas na Seção 3).
  2. Atualização de $Y$: Resolve um problema de operador proximal para a norma de Schatten $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$. Os autores derivam atualizações explícitas de forma fechada para os valores singulares de $Y$ para $p=1$ (norma nuclear), $p=\infty$ (norma espectral) e $p \in (1, \infty)$ geral (Lemas 5.5–5.7).
• Característica Chave: O algoritmo é de ordem zero; não computa gradientes ou subgradientes explícitos. Baseia-se puramente em operações de álgebra linear numérica (SVDs e multiplicações de matrizes).
• Convergência: O algoritmo é provado convergir para um minimizador global a partir de qualquer ponto inicial. A taxa de convergência é sublinear (devido à falta de convexidade forte nas normas de Schatten para $p \neq 2$), embora experimentos numéricos sugiram comportamento quase linear na prática.

Resultados Chave

• Expansões de Forma Fechada: O artigo fornece soluções explícitas para variantes afins, de produto de Kronecker separável, de posto de Kronecker e de rastro parcial do problema de proximidade generalizado.
• Limitação Teórica: Estabelece que a universalidade da solução através de diferentes normas invariantes ortogonalmente (teorema de Mirsky) decai na presença de multiplicadores não identidade $B$ e $C$.
• Desempenho Algorítmico:
  • Velocidade: Em experimentos numéricos (Seção 6), o Algoritmo 3 supera significativamente solvers de otimização convexa de propósito geral (especificamente CVX com o solver SCS). Para dimensões grandes, o CVX frequentemente falha em convergir dentro de limites de tempo razoáveis, enquanto o Algoritmo 3 converge rapidamente.
  • Precisão: O Algoritmo 3 alcança precisão de máquina ($\approx 10^{-15}$) no erro direto, enquanto o CVX exibe erros flutuantes (variando de $10^{-7}$ a $10^3$) e frequentemente falha em satisfazer restrições (por exemplo, em tarefas de identificação de sistemas).
  • Versatilidade: O algoritmo lida com sucesso com objetivos convexos não padrão (por exemplo, norma de Schatten $3/2$) e restrições não convexas (por exemplo, restrições de posto, autovalores prescritos) que são inacessíveis a solvers padrão como o CVX.

Significado e Alegações

O artigo alega avançar o campo dos problemas de proximidade de matrizes ao:

1. Estender a Solvabilidade: Fornecer soluções de forma fechada para novas classes de problemas envolvendo termos afins e estruturas de Kronecker.
2. Clarificar Limites Teóricos: Demonstrar as limitações de estender teoremas clássicos de aproximação (Mirsky) para configurações generalizadas.
3. Oferecer uma Alternativa Robusta: Propor um algoritmo iterativo que é globalmente convergente, livre de gradientes e computacionalmente superior a solvers de propósito geral.
4. Destacar Exploração Estrutural: Os autores enfatizam que explorar estruturas matriciais específicas via álgebra linear numérica (como feito em [13] e neste trabalho) produz melhor desempenho e aplicabilidade mais ampla (incluindo casos não convexos) do que confiar exclusivamente em frameworks gerais de otimização convexa.

O trabalho é apresentado como uma sequência de [13], mantendo a filosofia de resolver problemas de otimização sem computações de derivadas, aproveitando assim a rica estrutura dos espaços matriciais.