Complex Approximate Message Passing with Non-separable Denoising

1. Problema e Motivação

O artigo aborda o problema de inferência de alta dimensão em sinais complexos, especificamente no contexto de Compressed Sensing (CS) e recuperação de sinais estruturados.

• Contexto: O Approximate Message Passing (AMP) é um framework iterativo poderoso para resolver problemas de inversão linear com matrizes de medição aleatórias. A teoria de Evolução de Estado (State Evolution - SE) permite prever com precisão o desempenho assintótico do algoritmo.
• Limitação Atual: Embora existam extensões do AMP para sinais complexos e para funções de denoising (remoção de ruído) não separáveis, faltava uma teoria unificada de evolução de estado para o caso de AMP complexo com denoisers não separáveis.
• Aplicação Chave: O problema motivador é a detecção de preâmbulos em comunicações sem fio baseadas em OTFS (Orthogonal Time-Frequency Space), onde os usuários ativos formam grupos esparsos e os coeficientes do canal dentro de cada grupo também são esparsos. Isso leva ao problema de Sparse Group LASSO (SGL) no domínio complexo.
• Desafio Técnico: Uma abordagem ingênua de converter o sistema complexo ($\mathbb{C}^N$) para real ($\mathbb{R}^{2N}$) falha porque ou destrói a estrutura i.i.d. (independente e identicamente distribuída) da matriz de medição necessária para o AMP, ou desacopla as partes real e imaginária, impedindo o processamento conjunto das dependências estatísticas complexas.

2. Metodologia

Os autores propõem uma abordagem inovadora baseada em levantamento (lifting) e transformação canônica:

• Sistema Augmentado Real: Em vez de tratar o problema diretamente no domínio complexo ou fazer uma conversão simples, eles constroem um sistema real aumentado de dimensão superior.
  • O sinal complexo $x_0 \in \mathbb{C}^N$ é mapeado para uma matriz de estado real $S_0 \in \mathbb{R}^{N \times 2}$.
  • A matriz de medição complexa $A$ é expandida para uma matriz real $W \in \mathbb{R}^{2n \times N}$, onde cada linha de $A$ é decomposta em suas partes real e imaginária, criando um espaço de observação mais rico (4n medições reais para um sistema original de $n$ medições complexas).
• Transformação Canônica (Many-to-One): Eles definem uma transformação linear $R$ (baseada no produto de Kronecker com o vetor $\rho = [1, i]^T$) que mapeia o sistema real aumentado de volta para o domínio complexo.
  • Essa transformação é "muitos-para-um", o que significa que perde informação, mas é projetada para preservar as dinâmicas estatísticas essenciais do AMP.
• Correção de Onsager e Derivadas de Wirtinger:
  • Ao aplicar a transformação canônica ao sistema real aumentado, a correção de Onsager (necessária para remover a correlação entre iterações no AMP) surge naturalmente envolvendo derivadas de Wirtinger.
  • Isso permite lidar com funções não separáveis no domínio complexo sem precisar de provas complexas do zero, aproveitando os resultados existentes do AMP matricial real.
• Redução da Evolução de Estado: A teoria mostra que a evolução de estado do sistema real aumentado (que envolve matrizes $2 \times 2$) colapsa elegantemente para recursões escalares complexas no domínio original, simplificando drasticamente a análise.

3. Principais Contribuições

1. Teoria Unificada de Evolução de Estado: Estabelecimento rigoroso da evolução de estado para o AMP complexo com denoisers não separáveis. Isso preenche uma lacuna teórica importante, permitindo a análise de algoritmos que exploram estruturas conjuntas (como esparsidade de grupo e elemento simultaneamente).
2. Framework de Levantamento e Colapso: Desenvolvimento de um método sistemático para analisar sistemas complexos através de sistemas reais aumentados, utilizando uma transformação canônica que preserva a estrutura de simetria rotacional das distribuições gaussianas complexas.
3. Generalização para Matrizes: Extensão do framework para o caso de AMP matricial, onde múltiplos vetores de características são estimados simultaneamente. Isso é crucial para problemas com múltiplas medições ou canais.
4. Aplicação ao Complex Sparse Group LASSO (SGL):
   • Derivação do operador proximal fechado para o SGL complexo.
   • Cálculo explícito das derivadas de Wirtinger necessárias para a correção de Onsager neste contexto não separável.
   • Demonstração de que o SGL complexo é uma instância válida e necessária para problemas como detecção de preâmbulo em OTFS.

4. Resultados Experimentais

Os autores validaram a teoria através de experimentos numéricos:

• Validação da Evolução de Estado: As previsões teóricas da evolução de estado (curvas de erro quadrático médio - NMSE) corresponderam com alta precisão aos resultados empíricos obtidos em simulações com dimensões finitas ($N=1000$).
• Convergência: O AMP complexo proposto convergiu significativamente mais rápido (em cerca de 15 iterações) do que o algoritmo ISTA (Iterative Soft Thresholding Algorithm) complexo, mantendo o mesmo ponto fixo ótimo.
• Comparação de Desempenho: O Complex SGL (proposto) superou consistentemente três variantes de base em toda a faixa de SNR (Relação Sinal-Ruído):
  • Complex LASSO: Ignora a estrutura de grupo.
  • Complex GL (Group LASSO): Ignora a esparsidade intra-grupo.
  • Real SGL: Trata as partes real e imaginária como problemas independentes, falhando em capturar as dependências de fase e acoplamento inerentes aos sinais complexos.
• Conclusão Experimental: A abordagem proposta, que explora conjuntamente a esparsidade de grupo, a esparsidade intra-grupo e a estrutura complexa, fornece ganhos significativos de desempenho.

5. Significado e Impacto

Este trabalho é fundamental para o avanço do processamento de sinais em comunicações modernas e sistemas de radar/sonar:

• Fundamentação Teórica: Fornece a base matemática necessária para projetar e analisar algoritmos AMP em cenários complexos e estruturados, onde as soluções anteriores eram insuficientes ou heurísticas.
• Aplicabilidade Prática: Oferece um caminho para otimizar a detecção de usuários em redes sem fio de próxima geração (como 6G com OTFS) e estimação de canais, permitindo a recuperação de sinais com menos medições e maior robustez ao ruído.
• Extensibilidade: O framework abre portas para futuras extensões, incluindo matrizes de medição estruturadas (não apenas i.i.d.), modelos de observação generalizados (como medições quantizadas) e a "desdobramento" (unrolling) do AMP em arquiteturas de aprendizado profundo (Deep Unfolding) para domínios complexos não separáveis.

Em resumo, o artigo resolve um problema teórico de longa data ao unificar o AMP complexo com denoisers não separáveis, demonstrando que a construção de um sistema real aumentado, combinada com uma transformação canônica inteligente, permite a derivação de equações de evolução de estado escalares precisas e a obtenção de ganhos práticos significativos em problemas de recuperação de sinais estruturados.