Il convertitore MWC
4.13 Riduzione del modello IMV
Sostanzialmente, il paradigma IMV rappresenta un’estensione diretta del paradigma MMV, dove la cardinalità dell’insieme Λ passi da finita a infinita.
Questa modifica, da un lato avvicina alla realtà sperimentale il modello teorico, dall’altro complica, e non poco, il problema matematico. Infatti, le incognite così come le equazioni sono infinite.
Allo stato dell’arte, un sistema di infinite incognite non può essere analizzato mediante le consuete tecniche risolutive. Pertanto, Eldar e Mishali propongono di riportare il sistema basato sul paradigma IMV ad una versione equivalente ai fini della soluzione, ma dotata di un numero finito di incognite.
4.13.1 Discretizzazione
L’approccio più immediato individua una griglia finita all’interno dell’insieme Λ, del tipo Λ� ⊂ Λ, e trova la soluzione 𝑨𝑨�Λ��, valida solo per 𝜆𝜆 ∈ Λ�. Quindi, per approssimare la soluzione del sistema originario, la procedura termina con l’interpolazione di 𝑨𝑨�Λ�� sull’intero insieme Λ [53].
Però, nulla assicura che il risultato finale coincida con l’effettiva soluzione 𝑨𝑨�(Λ). Anzi, ciò si verifica molto raramente: non di rado, la versione interpolata non rispetta la condizione 𝒚𝒚(Λ) = 𝑨𝑨𝑨𝑨(Λ) quando valutata al di fuori della griglia, ossia per 𝜆𝜆 ∉ Λ�.
Inoltre, la densità della griglia influenza direttamente la complessità computazionale e la bontà della ricostruzione. Per la precisione, i due aspetti vanno in controtendenza ed è difficile trovare un compromesso ottimale: l’incremento della cardinalità di Λ� comporta una migliore aderenza ai dati, ma anche un aggravarsi del carico computazionale [53].
Alla luce di questi difetti, è preferibile evitare il ricorso alla discretizzazione, e concentrare la propria attenzione su riduzioni che, sebbene più complesse, non comportino alcuna perdita di informazione.
4.13.2 Riduzione “esatta”
L’approccio cosiddetto esatto si sviluppa in due stadi successivi: il primo appronta una stima del supporto del segnale originario 𝑆𝑆 = 𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝�𝑨𝑨(Λ)�; il secondo, invece, fornisce la ricostruzione del segnale originario a partire dalla stima di 𝑆𝑆 e dai dati a disposizione 𝒚𝒚(Λ).
Per ipotesi, la soluzione 𝑨𝑨
�
(Λ) è congiuntamente 𝑘𝑘 – sparsa, il che ha due rilevanti conseguenze. In primo luogo, il suo supporto, 𝑆𝑆 = 𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝�𝑨𝑨(Λ)�, non può contenere più di 𝑘𝑘 elementi, ossia |𝑆𝑆| ≤ 𝑘𝑘. In secondo luogo, il teorema T.4.5 assicura che il rango di Kruskal di 𝑨𝑨 è pari almeno a 𝑘𝑘, ossia 𝜎𝜎(𝑨𝑨) ≥ 𝑘𝑘.Definita 𝑨𝑨𝑠𝑠 come la matrice formata dalle sole colonne di 𝑨𝑨 i cui indici appartengano a 𝑆𝑆, è immediato verificare che tali colonne sono linearmente indipendenti. In altri termini, il rango di 𝑨𝑨𝑠𝑠 è pieno ed è valida l’uguaglianza (𝑨𝑨𝑠𝑠)†𝑨𝑨𝑠𝑠= 𝑰𝑰.
A quel punto, la stima del supporto del segnale originario può essere sfruttata per riformulare il sistema in un’espressione più compatta e facilmente risolvibile, che considera solo gli elementi del vettore 𝑨𝑨(𝜆𝜆) i cui indici appartengano a 𝑆𝑆 [63]:
𝒚𝒚(𝜆𝜆) = 𝑨𝑨𝑠𝑠𝑨𝑨𝑠𝑠(𝜆𝜆)
Una semplice operazione di inversione porge la soluzione del sistema [53]: 𝑚𝑚𝑠𝑠(𝜆𝜆) = �(𝑨𝑨𝑠𝑠)†𝒚𝒚(𝜆𝜆) 𝑠𝑠 ∈ 𝑆𝑆
0 𝑠𝑠 ∉ 𝑆𝑆
4.13.3 Primo stadio: conversione IMV – MMV
Come emerge anche dalle precedenti osservazioni, il nodo cruciale è rappresentato dalla stima del supporto del segnale originario. A tal proposito, si osserva che qualsiasi collezione finita di vettori, definita nel sottospazio 𝑠𝑠𝑝𝑝𝑚𝑚𝑠𝑠�𝒚𝒚(Λ)�, contiene sufficienti informazioni per ricostruire con esattezza 𝑆𝑆.
Non si tratta di un’intuizione o di una deduzione dall’esperienza sperimentale, quanto piuttosto di un risultato teorico, dimostrato formalmente dal seguente teorema.
T.4.7 Sia 𝑨𝑨�(Λ) l’unica soluzione 𝑘𝑘 – sparsa del sistema 𝒚𝒚(Λ) = 𝑨𝑨𝑨𝑨(Λ). La matrice 𝑨𝑨 di dimensioni
𝑚𝑚 × 𝑠𝑠 soddisfi il vincolo 𝜎𝜎(𝑨𝑨) ≥ 2𝑘𝑘 − �dim�𝑠𝑠𝑝𝑝𝑚𝑚𝑠𝑠�𝒚𝒚(Λ)� − 1��. Sia 𝑽𝑽 una matrice di 𝑚𝑚 righe, tale che il minimo sottospazio che contenga le sue colonne coincida con 𝑠𝑠𝑝𝑝𝑚𝑚𝑠𝑠�𝒚𝒚(Λ)�. Allora, il sistema lineare 𝑽𝑽 = 𝑨𝑨𝑨𝑨 ha un’unica soluzione 𝑘𝑘 – sparsa 𝑨𝑨
�
, il cui supporto coincide con 𝑆𝑆 [53].Questo enunciato costituisce il fondamento teorico che permette di sostituire ad un sistema basato sul paradigma IMV il suo equivalente basato sul paradigma MMV.
L’unica difficoltà concerne la costruzione di una matrice 𝑽𝑽 tale da soddisfare le ipotesi del T.4.7. Fortunatamente, esiste un altro teorema che risponde perfettamente alle specifiche esigenze del caso. T.4.8 Sia 𝑨𝑨(𝜆𝜆) una funzione continua a tratti per 𝜆𝜆 ∈ Λ tale che 𝒚𝒚(𝜆𝜆) = 𝑨𝑨𝑨𝑨(𝜆𝜆), ed esista finito l’integrale:
𝑸𝑸 = � 𝒚𝒚(𝜆𝜆)𝒚𝒚(𝜆𝜆)𝐻𝐻𝑑𝑑𝜆𝜆
𝜆𝜆∈Λ
Allora, qualsiasi matrice 𝑽𝑽, tale da soddisfare l’uguaglianza 𝑸𝑸 = 𝑽𝑽𝑽𝑽𝐻𝐻, soddisfa anche le ipotesi del teorema T.4.7 [53].
Dall’enunciato discendono alcune osservazioni di carattere prettamente matematico.
La condizione di esistenza e finitezza dell’integrale si traduce nella richiesta che il vettore delle misure 𝒚𝒚(𝜆𝜆) abbia energia finita per ogni 𝜆𝜆 ∈ Λ. Peraltro, 𝑸𝑸 costituisce una matrice semi – definita positiva, ossia può essere sempre scomposta nel prodotto di due matrici del tipo 𝑸𝑸 = 𝑽𝑽𝑽𝑽𝐻𝐻.
4.13.4 Secondo stadio: conversione MMV – SMV
Il primo stadio ha permesso di individuare un sistema equivalente all’originale, ma basato sul paradigma MMV, invece che sul paradigma IMV. Nel secondo stadio, l’obbiettivo finale è del tutto analogo, in quanto si cerca un'altra versione equivalente del sistema, basata però sul paradigma SMV.
Sarebbe semplicistico quanto infruttuoso adottare la medesima riduzione “esatta”. In realtà, la strategia approntata da Eldar e Mishali ricorre a principi probabilistici ed evidenze sperimentali.
D.4.5 Una distribuzione di probabilità 𝒫𝒫 si dice assolutamente continua se qualsiasi valore nullo occorre con probabilità nulla [54]. In maniera equivalente, una distribuzione di probabilità 𝒫𝒫 si dice assolutamente continua se e solo se può essere rappresentata mediante l’integrale di una funzione densità integrabile [55].
Per esempio, la distribuzione gaussiana, o quella uniforme, presentano una funzione densità che è integrabile. Dunque entrambe sono assolutamente continue. Altrettanto non si può dire di alcune distribuzioni di probabilità singolari, come quella discreta.
La D.4.5 viene richiamata anche nel teorema alla base della conversione dal paradigma MMV a quello SMV. T.4.9 Sia dato il sistema 𝒚𝒚(Λ) = 𝑨𝑨𝑨𝑨(Λ) basato sul paradigma MMV, dove 𝒚𝒚(Λ) è una matrice di
dimensioni 𝑚𝑚 × 𝑑𝑑, 𝑨𝑨 è una matrice di dimensioni 𝑚𝑚 × 𝑠𝑠, 𝑨𝑨(Λ) è una matrice di dimensioni 𝑠𝑠 × 𝑑𝑑. Sia 𝑨𝑨
�
(Λ) l’unica soluzione 𝑘𝑘 – sparsa del sistema e sia soddisfatta la condizione 𝜎𝜎(𝑨𝑨) ≥ 2𝑘𝑘.Sia 𝒂𝒂 un vettore, di dimensione 𝑑𝑑, i cui elementi siano tratti in maniera casuale da una distribuzione di probabilità assolutamente continua. Si definiscano i vettori, generati in maniera casuale, 𝒚𝒚 = 𝒚𝒚(Λ)𝒂𝒂 e 𝑨𝑨 = 𝑨𝑨(Λ)𝒂𝒂.
Allora, considerando il sistema 𝒚𝒚 = 𝑨𝑨𝑨𝑨, basato sul paradigma SMV, sono valide le seguenti due osservazioni:
1) Per qualsiasi realizzazione di 𝒂𝒂, 𝑨𝑨� è l’unica soluzione 𝑘𝑘 – sparsa del sistema.
2) Il supporto coincide nei due casi SMV e MMV, ossia l’uguaglianza 𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝(𝑨𝑨�) = 𝑠𝑠𝑢𝑢𝑝𝑝𝑝𝑝�𝑨𝑨�(Λ)� è verificata con probabilità unitaria [53].
L’enunciato descrive nei minimi dettagli il protocollo per combinare in un unico vettore 𝒚𝒚 le colonne della matrice 𝒚𝒚(Λ). A tal proposito, è doveroso sottolineare il ruolo fondamentale giocato dal vettore 𝒂𝒂, i cui elementi fungono da coefficienti della combinazione lineare.
Paradossalmente, la realizzazione casuale si dimostra la migliore scelta possibile, dato che nessuna realizzazione deterministica garantisce con certezza di conservare il supporto. A suffragio di questa affermazione esistono numerose prove.
Un esempio lampante è offerto dall’adozione per 𝒂𝒂 di un vettore unitario, ossia i cui elementi siano tutti pari a 1. In tal caso, se anche ad una sola riga non nulla di 𝑨𝑨(Λ) corrisponde un valore nullo di 𝑨𝑨 = 𝑨𝑨(Λ)𝒂𝒂, la stima del supporto che se ne ricava è errata.