A Note About Algebraic $(s, t)$-Weak Tractability Of Linear Tensor Product Problems In The Worst-Case Setting

Problematica
Questo articolo affronta la durezza computazionale dei problemi di prodotto tensoriale lineare nell'ambito della complessità basata sull'informazione (IBC), concentrandosi specificamente sul caso del caso peggiore (worst-case). L'oggetto centrale di studio è una sequenza di operatori lineari $S = \{S_d\}_{d \in \mathbb{N}}$, definita come il prodotto tensoriale $d$-esimo di un operatore lineare compatto $S_1$ che agisce tra spazi di Hilbert. La complessità di questi problemi è misurata dalla complessità dell'informazione $n(\varepsilon, S_d)$, definita come il numero minimo di valutazioni di funzionali lineari continui richiesti per approssimare la soluzione entro un errore assoluto $\varepsilon$.

L'articolo investiga specificamente la debole tracciabilità algebrica $(s, t)$ (ALG-$(s, t)$-WT). Un problema si considera ALG-$(s, t)$-WT se il logaritmo della complessità dell'informazione cresce in modo sub-lineare rispetto a $\varepsilon^{-s} + d^t$ quando $\varepsilon^{-1} + d \to \infty$. Sebbene condizioni necessarie e sufficienti per l'ALG-$(s, t)$-WT fossero state precedentemente stabilite per il criterio dell'errore normalizzato e per il criterio dell'errore assoluto quando il quadrato del più grande autovalore $\lambda_1 \leq 1$, rimaneva una lacuna significativa. Nello specifico, per il criterio dell'errore assoluto nel caso in cui $\lambda_1 > 1$, esistevano solo risultati parziali: erano note condizioni necessarie e sufficienti separate, ma non era stata derivata una condizione necessaria e sufficiente unificata sui valori singolari univariati.

Metodologia
Gli autori impiegano un approccio analitico rigoroso basato sulle proprietà spettrali degli operatori sottostanti. La metodologia procede come segue:

1. Normalizzazione: Per gestire il caso $\lambda_1 > 1$, gli autori introducono un problema normalizzato $S' = \{S'_d\}$ dove $S'_1 = \frac{1}{\sqrt{\lambda_1}}S_1$. Questa trasformazione permette agli autovalori dell'operatore normalizzato di soddisfare $\lambda'_1 = 1$, facilitando il confronto con i risultati noti per il criterio dell'errore normalizzato.
2. Limiti della Complessità dell'Informazione: Il documento utilizza la relazione tra la complessità dell'informazione e i valori singolari dell'operatore. Per il criterio dell'errore assoluto, la complessità è legata al conteggio dei multi-indici $(j_1, \dots, j_d)$ tali che il prodotto degli autovalori superi una soglia.
3. Stima Combinatoria: Uno strumento tecnico chiave è il Lemma 2.2, che fornisce un limite superiore per la complessità dell'informazione $n_{NOR}(\varepsilon, S'_d)$ utilizzando permutazioni e combinazioni. Questo limite dipende dal numero di indici in cui gli autovalori sono strettamente minori di 1, indicato con $a_\varepsilon(d)$, e dalla funzione di conteggio univariata $j(\varepsilon)$.
4. Analisi Asintotica: Gli autori analizzano il comportamento asintotico della funzione di conteggio $j(\varepsilon)$ (il numero di autovalori maggiori di $\varepsilon^2$) al tendere di $\varepsilon \to 0$. Essi stabiliscono un'equivalenza tra il tasso di decadimento degli autovalori e la crescita di $j(\varepsilon)$ tramite il Lemma 2.1.
5. Valutazione del Limite: Sostituendo i limiti derivati nella definizione di ALG-$(s, t)$-WT, gli autori valutano il limite del rapporto $\frac{\ln n(\varepsilon, S_d)}{\varepsilon^{-s} + d^t}$ per determinare le condizioni sotto le quali esso si annulla.

Contributi Chiave e Risultati
Il contributo primario di questo lavoro è la risoluzione del problema aperto relativo all'ALG-$(s, t)$-WT per problemi di prodotto tensoriale lineare con $\lambda_1 > 1$ sotto il criterio dell'errore assoluto.

• Teorema 1.1: Il documento stabilisce una condizione necessaria e sufficiente per l'ALG-$(s, t)$-WT in questo specifico setting. Il problema $S$ è ALG-$(s, t)$-WT se e solo se:

  1. $t > 1$; e
  2. I valori singolari univariati $\{\lambda_j\}$ soddisfano la condizione di decadimento:
     $$\lim_{j \to \infty} \frac{(\ln \frac{1}{\lambda_j})^t}{\ln j} = \infty.$$

• Risoluzione della Lacuna: Questo risultato colma la lacuna lasciata dai lavori precedenti (specificamente Siedlecki e Weimar [15]), che avevano fornito condizioni necessarie e sufficienti separate ma non erano riusciti a unificarle in una singola caratterizzazione per $\lambda_1 > 1$.

• Indipendenza dai Parametri: Gli autori evidenziano un risultato interessante: nel caso $\lambda_1 > 1$ con il criterio dell'errore assoluto, la condizione di tracciabilità dipende solo dal parametro $t$ (richiedendo $t > 1$) e dal decadimento degli autovalori. Il parametro $s$ non compare nella condizione necessaria e sufficiente per il decadimento degli autovalori, diversamente dal caso in cui $\lambda_1 \leq 1$ o per il criterio dell'errore normalizzato.

• Relazione con la Tracciabilità Esponenziale: Il documento nota una connessione con la tracciabilità esponenziale (EXP-tracciabilità). Per $\lambda_1 > 1$ e ABS, il problema è ALG-$(s, t)$-WT se e solo se è ALG-$(t, t)$-WT, e se e solo se è EXP-$(s, t)$-WT con $s > t$.

Significatività
L'articolo rivendica la propria significatività fornendo una caratterizzazione completa della debole tracciabilità algebrica per una classe di problemi che era precedentemente solo parzialmente compresa. Dimostrando che la condizione derivata in [15] (che era precedentemente nota solo come necessaria) è anche sufficiente, gli autori chiudono una lacuna teorica nello studio dell'approssimazione multivariata. I risultati chiariscono il ruolo dei parametri $s$ e $t$ e del decadimento spettrale dell'operatore, dimostrando che per $\lambda_1 > 1$, la "maledizione della dimensionalità" può essere superata (nel senso debole) assicurando semplicemente che gli autovalori decadano sufficientemente velocemente rispetto al parametro $t$, a condizione che $t > 1$.