Newton-Direction-Based ReLU-Thresholding Methods for Nonnegative Sparse Signal Recovery

1. O Problema

O artigo aborda o problema de recuperação de sinais esparsos não negativos. Este é um caso fundamental na teoria da Compressão Sensorial (Compressive Sensing), onde o objetivo é reconstruir um sinal $x \in \mathbb{R}^n$ (que é esparsos, ou seja, possui poucos elementos não nulos, e não negativo, $x \ge 0$) a partir de um número limitado de medições ruidosas $y \in \mathbb{R}^m$, onde $m \ll n$.

O problema é formulado como uma otimização esparsa com restrição de não negatividade:
$$\min_{x \in \mathbb{R}^n} \left\{ \frac{1}{2}\|y - Ax\|_2^2 : \|x\|_0 \le k, x \ge 0 \right\}$$
onde $A$ é a matriz de medição, $k$ é o nível de esparsidade e $\|x\|_0$ é a norma $\ell_0$ (contagem de entradas não nulas).

2. Metodologia Proposta

Os autores propõem a fusão de três conceitos principais: métodos de tipo Newton, a função de ativação ReLU (Rectified Linear Unit) e operadores de limiarização (thresholding).

Algoritmos Propostos

Dois algoritmos são desenvolvidos:

1. NDRT (Newton-Direction-Based ReLU-Thresholding):

   • É uma modificação do esquema de limiarização dura (hard thresholding) baseado em Newton.
   • Em cada iteração, calcula-se uma direção de Newton modificada: $u^{(p+1)} = x^{(p)} + \lambda(A^\top A + \varepsilon I)^{-1}A^\top(y - Ax^{(p)})$.
   • Aplica-se a função ReLU ($\Psi(u) = \max(u, 0)$) para garantir a não negatividade.
   • Aplica-se o operador de limiarização dura $H_k$ para manter apenas as $k$ maiores entradas não negativas, zerando as demais.

2. NDRTP (Newton-Direction-Based ReLU-Thresholding Pursuit):

   • Uma versão aprimorada do NDRT.
   • Após selecionar o conjunto de suporte (índices das $k$ maiores entradas) via ReLU e limiarização, o algoritmo resolve um subproblema de Mínimos Quadrados Não Negativos (NNLS) restrito a esse suporte.
   • Isso refina a estimativa do sinal, geralmente levando a uma convergência mais rápida e precisa.

Avanço Teórico nos Parâmetros

Um ponto crucial da metodologia é a análise de convergência. Trabalhos anteriores (como NSIHT/NSHTP) exigiam que o parâmetro de regularização $\varepsilon$ fosse muito grande ($\varepsilon > \sigma_1^2$, onde $\sigma_1$ é o maior valor singular de $A$) para garantir a convergência da série de potências da matriz.

• Inovação: Os autores utilizam uma análise baseada em decomposição espectral para provar que o algoritmo converge mesmo com $\varepsilon$ arbitrariamente pequeno. Isso permite que a matriz $(A^\top A + \varepsilon I)$ seja uma perturbação mínima da Hessiana real, preservando as vantagens de convergência quadrática do método de Newton.

3. Contribuições Principais

• Novos Algoritmos: Introdução do NDRT e NDRTP, integrando a direção de Newton com a função ReLU para lidar nativamente com a restrição de não negatividade.
• Análise de Convergência Relaxada: Demonstração teórica de que a condição restritiva $\varepsilon > \sigma_1^2$ pode ser removida. O parâmetro $\varepsilon$ pode ser pequeno, o que é teoricamente superior para aproximações de Newton.
• Limites de Erro e Condições Suficientes: Estabelecimento de condições suficientes para a recuperação exata baseadas na Constante de Isometria Restrita (RIC, $\delta_k$) e nos valores singulares da matriz de medição.
  • Para o NDRT, a condição é $\delta_{3k} + \sigma_1^2 - \sigma_m^2 < \frac{\sqrt{5}-1}{2} \approx 0.618$.
  • Para o NDRTP, a condição é $\delta_{3k} + \sigma_1^2 - \sigma_m^2 < \frac{1}{\sqrt{3}} \approx 0.577$.
• Fórmula Empírica para Passo: Proposição de uma fórmula prática para o tamanho do passo $\lambda$ baseada na teoria de matrizes aleatórias: $\lambda \approx \lfloor (1 + \sqrt{n/m})^2 \rfloor$, reduzindo o custo computacional de calcular valores singulares exatos.

4. Resultados Numéricos

Os autores realizaram simulações extensas comparando NDRT e NDRTP com métodos existentes (RHT, RHTP, NNOMP, NNSP).

• Cenários: Testes em ambientes sem ruído e com ruído ($y = Ax + 10^{-4}h$).
• Desempenho de Recuperação:
  • O NDRTP demonstrou o melhor desempenho, alcançando taxas de sucesso superiores a 90% para níveis de esparsidade ($k$) significativamente mais altos do que os concorrentes (ex: $k=310$ vs. $k=290$ para o segundo melhor).
  • O NDRT superou métodos como RHT e NNOMP, mas teve desempenho inferior ao NDRTP e ao NNSP em níveis de esparsidade muito altos.
• Robustez ao Ruído: Todos os algoritmos (exceto NNOMP, que degradou severamente) mantiveram estabilidade sob ruído, com o NDRTP mantendo a liderança.
• Tempo Computacional:
  • O NDRTP é mais lento que o NDRT devido à resolução do subproblema NNLS, mas é mais rápido que NNOMP e NNSP em níveis de esparsidade altos.
  • O custo por iteração é maior, mas a precisão superior compensa o tempo em cenários de alta esparsidade.

5. Significância e Conclusão

O trabalho é significativo porque oferece uma abordagem teoricamente sólida e empiricamente superior para a recuperação de sinais não negativos. Ao integrar a função ReLU diretamente no esquema de Newton, os autores eliminam a necessidade de projeções complexas ou restrições de parâmetros excessivamente conservadoras.

A principal conclusão é que o NDRTP representa o estado da arte atual para esse problema específico, oferecendo a maior capacidade de recuperação de sinais esparsos não negativos, especialmente em cenários onde a esparsidade é alta e a matriz de medição possui propriedades de isometria restrita específicas. A capacidade de usar um parâmetro de regularização $\varepsilon$ pequeno torna o método mais fiel à geometria do problema original de otimização.