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

1. Il Problema: Recupero di Segnali Sparsi Non Negativi

Il lavoro si concentra sul problema del recupero di segnali sparsi non negativi (Nonnegative Sparse Signal Recovery - NSSR), una variante fondamentale del Compressed Sensing.

• Contesto: In molte applicazioni (elaborazione di immagini mediche, riconoscimento facciale, telerilevamento), i segnali da ricostruire sono sia sparsi (hanno pochi elementi non nulli) che non negativi ($x \ge 0$).
• Formulazione: Dati un vettore di misurazioni $y \in \mathbb{R}^m$ e una matrice di misurazione $A \in \mathbb{R}^{m \times n}$ (con $m \ll n$), il segnale $x$ è ottenuto tramite $y = Ax + e$, dove $e$ è il rumore. L'obiettivo è risolvere il problema di ottimizzazione:
  $$\min_{x \in \mathbb{R}^n} \left\{ \frac{1}{2}\|y - Ax\|_2^2 : \|x\|_0 \le k, x \ge 0 \right\}$$
  dove $\|x\|_0$ conta gli elementi non nulli.
• Sfida: Esistono metodi esistenti basati su Hard Thresholding (soglia dura) e su approcci Newton, ma spesso richiedono condizioni restrittive sui parametri di regolarizzazione o non integrano efficacemente il vincolo di non negatività durante l'iterazione.

2. Metodologia Proposta

Gli autori propongono due nuovi algoritmi che fondono la direzione di Newton, la funzione di attivazione ReLU (Rectified Linear Unit) e l'operatore di soglia dura.

A. NDRT (Newton-Direction-Based ReLU-Thresholding)

Questo algoritmo modifica lo schema iterativo classico dei metodi Newton-based per l'ottimizzazione sparsa.

• Idea chiave: Invece di applicare direttamente la soglia dura al passo di Newton, si applica prima la funzione ReLU ($\Psi(x) = \max\{x, 0\}$). Questo proietta implicitamente il vettore intermedio sull'insieme dei vettori non negativi prima di selezionare i $k$ elementi più grandi.
• Schema iterativo:
  $$x^{(p+1)} = H_k \left( \Psi \left( x^{(p)} + \lambda (A^\top A + \varepsilon I)^{-1} A^\top (y - Ax^{(p)}) \right) \right)$$
  Dove $H_k$ è l'operatore di soglia dura, $\lambda$ è il passo e $\varepsilon$ è un parametro di regolarizzazione.

B. NDRTP (Newton-Direction-Based ReLU-Thresholding Pursuit)

Questa è una variante potenziata di NDRT.

• Miglioramento: Dopo aver selezionato l'insieme di supporto $S^{(p+1)}$ tramite ReLU e soglia dura, l'algoritmo risolve un sottoproblema di Least Squares Non Negativi (NNLS) su tale supporto.
• Vantaggio: Questo passo di "pursuit" (inseguimento) affina i coefficienti risolvendo un problema di ottimizzazione vincolata, migliorando la precisione della ricostruzione rispetto alla semplice soglia.

3. Contributi Chiave e Innovazioni Teoriche

1. Rimozione di Condizioni Restrittive su $\varepsilon$:
   I metodi Newton-based precedenti (es. NSIHT) richiedevano che il parametro di regolarizzazione $\varepsilon$ fosse maggiore del quadrato del più grande valore singolare di $A$ ($\varepsilon > \sigma_1^2$). Questo rendeva la matrice $(A^\top A + \varepsilon I)$ una perturbazione troppo grande dell'Hessiano reale, riducendo l'efficacia del metodo Newton.

   • Contributo: Gli autori dimostrano, tramite un'analisi basata sulla decomposizione spettrale, che $\varepsilon$ può essere scelto come qualsiasi numero positivo arbitrariamente piccolo. Questo permette di trattare $(A^\top A + \varepsilon I)$ come una perturbazione minima, preservando le proprietà quadratiche di convergenza del metodo Newton.

2. Nuove Condizioni di Convergenza:
   Vengono stabiliti teoremi di convergenza (Teoremi 3.2 e 3.5) che garantiscono il recupero esatto (o la convergenza entro un errore legato al rumore) sotto condizioni specifiche sulla Costante di Isometria Restretta (RIC) $\delta_{3k}$ e sui valori singolari della matrice $A$.

   • La condizione per NDRTP è $\delta_{3k} + \sigma_1^2 - \sigma_m^2 < 1/\sqrt{3}$.

3. Analisi del Vincolo di Non Negatività:
   Viene sviluppato un nuovo limite di errore (Teorema 3.4) basato sulle condizioni KKT (Karush-Kuhn-Tucker) per il problema di proiezione non negativa. Questo risultato è fondamentale per dimostrare la convergenza dell'algoritmo NDRTP.

4. Formula Empirica per il Passo $\lambda$:
   Viene proposta una formula empirica per scegliere il passo $\lambda$ in NDRTP basata sulla teoria delle matrici casuali:
   $$\lambda \approx \left(1 + \sqrt{\frac{n}{m}}\right)^2$$
   Questa scelta riduce il costo computazionale evitando il calcolo esplicito dei valori singolari estremi ad ogni iterazione, mantenendo alte prestazioni.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su segnali sparsi non negativi sintetici con matrici di misurazione gaussiane ($m=600, n=2000$).

• Confronto: Gli algoritmi proposti (NDRT e NDRTP) sono stati confrontati con metodi esistenti: RHT, RHTP, NNOMP e NNSP.
• Scenario Senza Rumore:
  • NDRTP mostra le prestazioni migliori, riuscendo a recuperare segnali con livelli di sparsità ($k$) fino a 310 con un tasso di successo > 90%, superando tutti gli altri metodi (il secondo migliore, RHTP, scende sotto il 50% a $k=310$).
  • NDRT performa meglio di RHT e NNOMP, ma leggermente peggio di NNSP e RHTP.
• Scenario con Rumore:
  • NDRTP mantiene una robustezza superiore, degradando meno degli altri algoritmi in presenza di rumore.
  • NNOMP mostra la degradazione più severa a causa della difficoltà nel catturare il supporto corretto sotto rumore.
• Tempo di Calcolo:
  • NDRTP richiede più tempo per iterazione rispetto a metodi puramente basati su soglia (come RHT) a causa della risoluzione del sottoproblema NNLS. Tuttavia, per alti livelli di sparsità, NDRTP è più veloce di NNOMP e NNSP, poiché converge in meno iterazioni.

5. Significato e Conclusioni

Questo lavoro rappresenta un avanzamento significativo nel campo del recupero di segnali sparsi non negativi.

• Integrazione Efficace: Dimostra che l'integrazione della funzione ReLU all'interno di schemi di tipo Newton è non solo fattibile, ma superiore per questo specifico tipo di vincoli.
• Flessibilità Teorica: La rimozione della restrizione $\varepsilon > \sigma_1^2$ è un contributo teorico importante che rende i metodi Newton-based più pratici e stabili numericamente, permettendo di sfruttare appieno le informazioni dell'Hessiano.
• Prestazioni: L'algoritmo NDRTP si posiziona come lo stato dell'arte per il recupero di segnali non negativi, offrendo un compromesso ottimale tra accuratezza di recupero (specialmente ad alti livelli di sparsità) e stabilità in presenza di rumore, giustificando il costo computazionale aggiuntivo.

In sintesi, il paper fornisce sia una solida base teorica che prove empiriche convincenti che i metodi basati su Newton e ReLU superano le tecniche greedy e di soglia tradizionali per il recupero di segnali non negativi.