Constructive discretization and approximation in reproducing kernel Hilbert spaces

1. Il Problema

Il lavoro affronta due problemi fondamentali nell'analisi numerica e nell'approssimazione funzionale:

1. Discretizzazione delle norme: Come approssimare la norma $L^2$ (o altre norme) di una funzione in uno spazio funzionale (spesso infinito-dimensionale) utilizzando un numero finito di valutazioni puntuali (campioni) e pesi associati. L'obiettivo è garantire che la norma discreta sia equivalente alla norma continua con costanti di equivalenza controllate.
2. Recupero tramite campionamento (Sampling Recovery): Costruire algoritmi di approssimazione (in particolare, approssimazione ai minimi quadrati pesati) che, dati campioni di una funzione sconosciuta $f$, producano un'approssimazione $\tilde{f}$ con un errore di approssimazione vicino all'errore di migliore approssimazione possibile nello spazio scelto.

Storicamente, risultati forti in questo ambito si basavano sul teorema non costruttivo di Kadison-Singer (o sulla sua versione di Marcus, Spielman e Srivastava - MSS), che garantiva l'esistenza di tali punti e pesi ma non forniva un algoritmo efficiente per trovarli. Altri approcci costruttivi (come quello di Batson, Spielman e Srivastava - BSS) esistevano ma erano limitati a spazi finiti o richiedevano fattori di sovracampionamento (oversampling) molto elevati e costanti subottimali.

2. Metodologia

Gli autori generalizzano l'algoritmo di sparsificazione di Batson, Spielman e Srivastava (BSS) per gestire spazi di funzioni più generali, inclusi spazi infinito-dimensionali come gli Spazi di Hilbert a Nucleo Riproduttore (RKHS).

• Generalizzazione dell'algoritmo BSS: L'algoritmo originale seleziona punti e pesi iterativamente per mantenere controllati gli autovalori di una matrice. Gli autori estendono questo concetto a operatori lineari in spazi infinito-dimensionali.
• Decoupling dei limiti: Introducono due famiglie di funzioni distinte:
  • Una famiglia $a$ (di dimensione finita $m$) per controllare il limite inferiore (legato alla stabilità dell'approssimazione nello spazio di approssimazione $V_m$).
  • Una famiglia $b$ (potenzialmente infinito-dimensionale) per controllare il limite superiore (legato alla stabilità globale nello spazio $H$).
• Dimensione Effettiva: Sostituiscono la dimensione $M$ (che potrebbe essere infinita) con una "dimensione effettiva" $M_{eff} = \text{Tr}(J)/\lambda_{\max}(J)$, dove $J$ è l'operatore di Gram associato alla famiglia $b$. Questo permette di trattare spazi infinito-dimensionali purché l'operatore di embedding abbia traccia finita.
• Potenziali e Verificatori: La prova si basa sulla definizione di potenziali inferiori ($\Phi$) e superiori ($\Psi$) e sull'uso di "verificatori" ($L$ e $U$) per selezionare i punti $x_i$ e i pesi $w_i$ in modo che i potenziali non aumentino durante l'aggiunta di aggiornamenti di rango uno.
• Troncamento Costruttivo: Per rendere l'algoritmo implementabile in spazi infinito-dimensionali, gli autori propongono una strategia di troncamento della base di funzioni. Dimostrano che, sotto opportune ipotesi di regolarità (decadimento dei coefficienti di Fourier e limiti $L^\infty$ sulla base), l'errore di troncamento è controllabile e l'algoritmo rimane efficiente.
• Campionamento Christoffel: Per la selezione dei punti candidati, suggeriscono l'uso della densità di Christoffel associata allo spazio $V_m$, dimostrando che questo porta a un tasso di accettazione dei punti sufficiente per garantire la complessità computazionale polinomiale.

3. Contributi Chiave

1. Teorema 3 (Generalizzazione BSS): Un risultato di algebra lineare che garantisce l'esistenza di punti e pesi per discretizzare le norme in spazi di funzioni, rendendo il limite superiore indipendente dalla dimensione dello spazio (dipendendo invece dalla dimensione effettiva). Questo risultato è costruttivo e calcolabile in tempo polinomiale.
2. Miglioramento delle Costanti e del Sovracampionamento: Rispetto ai lavori precedenti (es. [14]), il nuovo approccio riduce drasticamente il fattore di sovracampionamento necessario. Mentre lavori precedenti richiedevano $n/m \ge 10^7$, il nuovo metodo funziona già con $n/m = 2$ (o anche $n=m$ in certi casi), migliorando significativamente le costanti negli errori di approssimazione.
3. Algoritmo Costruttivo per RKHS: Forniscono un algoritmo (Algorithm 1) che costruisce i punti di campionamento e i pesi per spazi di funzioni di mixed smoothness (es. spazi di Sobolev misti), un caso in cui non esisteva precedentemente una costruzione polinomiale nota per raggiungere l'ordine ottimale.
4. Discretizzazione con Pesi Uguali: Dimostrano risultati per la discretizzazione unilaterale con pesi uguali (Proposizione 8), estendendo risultati noti a spazi $L^p$ per $p \ge 2$.

4. Risultati Principali

• Discretizzazione delle Norme (Corollario 6): Per ogni spazio $V_m$ e RKHS $H$, esistono $n$ punti e pesi tali che la norma $L^2$ è equivalente alla norma discreta pesata con costanti dipendenti da $m/n$ e dalla dimensione effettiva di $H$.
• Errori di Approssimazione (Corollario 10 e 11): Gli errori dell'approssimazione ai minimi quadrati pesati sono limitati dall'errore di migliore approssimazione nello spazio $V_m$, moltiplicato per fattori che dipendono dalle costanti di discretizzazione. Questo vale anche in presenza di rumore nei dati.
• Numeri di Campionamento (Corollario 12): I numeri di campionamento lineare $g_n(B_H, L^2)$ per la palla unitaria di un RKHS sono limitati da una combinazione dei valori singolari dell'embedding $H \to L^2$. In particolare, per decadimento esponenziale dei valori singolari, il nuovo bound offre un miglioramento asintotico rispetto ai risultati precedenti.
• Complessità Computazionale (Teorema 21): L'algoritmo proposto ha una complessità computazionale polinomiale in $n$ (e lineare nella dimensione di troncamento $N$). Per spazi di funzioni con regolarità mista $H^\alpha_{mix}$, l'algoritmo raggiunge il tasso di convergenza ottimale $O(m^{-\alpha} (\log m)^{\alpha(d-1)})$.

5. Significato e Impatto

Questo lavoro rappresenta un passo significativo verso l'implementazione pratica di algoritmi di approssimazione ottimali in spazi di funzioni ad alta o infinita dimensionalità.

• Rimozione della Non-Costruttività: Sostituisce l'uso del teorema di Kadison-Singer (non costruttivo) con un algoritmo esplicito e implementabile, rendendo i risultati teorici accessibili nella pratica computazionale.
• Efficienza: La riduzione del fattore di sovracampionamento da ordini di grandezza elevati a fattori piccoli (es. 2) rende questi metodi applicabili a problemi reali dove il costo di valutazione della funzione è elevato.
• Versatilità: Il metodo si applica a una vasta gamma di spazi funzionali, inclusi quelli con regolarità mista (mixed smoothness), che sono cruciali per la risoluzione di equazioni differenziali alle derivate parziali in dimensioni elevate.
• Validazione Numerica: La sezione 6 conferma sperimentalmente che l'algoritmo funziona bene in pratica, mostrando una distribuzione dei punti che riflette la struttura geometrica dello spazio (es. distribuzione uniforme per basi trigonometriche, concentrazione ai bordi per polinomi di Legendre/Chebyshev) e un tasso di accettazione dei punti molto superiore ai limiti teorici inferiori.

In sintesi, il paper fornisce un ponte solido tra la teoria dell'approssimazione in spazi infinito-dimensionali e l'implementazione algoritmica efficiente, offrendo nuovi strumenti per l'analisi numerica moderna.