Il prezzo della sparsità: condizioni sufficienti per il recupero di segnali sparsi mediante misure sparse e misure rese sparse

Abstract degli autori

Studiamo il recupero del supporto di segnali binari sparsi a partire da misure lineari rumorose. Per le matrici di misurazione gaussiane sparse, individuiamo condizioni sufficienti sul numero minimo di campioni per il recupero mediante massima verosimiglianza nel regime ad alto rapporto segnale-rumore $ds/p \to \infty$, dove $p$ indica la dimensione del segnale, $s$ il numero delle sue componenti non nulle e $d$ il numero atteso di componenti non nulle per riga della matrice di misurazione. Insieme ai limiti inferiori già noti, questo risultato fornisce una soglia teorico-informativa dell’ordine di $s\log(p/s) / \log(ds/p)$, rendendo esplicito il prezzo della sparsità delle misure. In particolare, mettiamo in evidenza un regime in cui l’aumento del numero di campioni richiesti a causa della sparsità delle misure è logaritmico, mentre il guadagno computazionale è quasi lineare. Studiamo poi il recupero dopo aver reso sparso un disegno gaussiano originariamente denso: le osservazioni sono generate dal disegno denso, mentre la stima utilizza un disegno reso sparso in modo indipendente e una risposta riscalata. Nel regime proporzionale $s=αp$, $d=ψp$, dimostriamo che, per ogni livello di errore prefissato $δ$ e ogni margine $\varepsilon>0$, un numero di campioni dell’ordine di $p/ψ^2$ è sufficiente per il recupero del supporto anche per valori di $ψ$ arbitrariamente piccoli.