Optimality of Operator-Like Wavelets for Representing Sparse AR(1) Processes

Pedram Pad, Michael Unser

Abstract

It is known that the Karhunen-Lo`{e}ve transform (KLT) of Gaussian first-order auto-regressive (AR(1)) processes results in sinusoidal basis functions. The same sinusoidal bases come out of the independent-component analysis (ICA) and actually correspond to processes with completely independent samples. In this paper, we relax the Gaussian hypothesis and study how orthogonal transforms decouple symmetric-alpha-stable (S$\alpha$S) AR(1) processes. The Gaussian case is not sparse and corresponds to $\alpha=2$, while $0<\alpha<2$ yields processes with sparse linear-prediction error. In the presence of sparsity, we show that operator-like wavelet bases do outperform the sinusoidal ones. Also, we observe that, for processes with very sparse increments ($0<\alpha\leq 1$), the operator-like wavelet basis is indistinguishable from the ICA solution obtained through numerical optimization. Our framework then offers a unified view that encompasses the discrete cosine transform (known to be asymptotically optimal for $\alpha=2$) and Haar-like wavelets (for which we achieve optimality for $0<\alpha\leq1$).

Introduction

In signal processing, the goal of a transform is often to decouple a signal into independent coefficients, facilitating efficient compression and denoising. For Gaussian signals, the Discrete Cosine Transform (DCT) and the Karhunen-Loève Transform (KLT) are the standard choices. However, real-world data—such as natural images or financial time series—often exhibit "spiky" or sparse characteristics that Gaussian models fail to capture. This paper investigates the optimal representation for sparse, first-order autoregressive (AR(1)) processes, demonstrating that operator-like wavelets provide a superior basis compared to traditional sinusoidal transforms.

Modeling Sparsity with S$\alpha$S Processes

To analyze the transition from Gaussian to sparse signals, the authors utilize Symmetric-Alpha-Stable (S$\alpha$S) models. By adjusting the stability parameter $\alpha$, the model spans a range from the Gaussian distribution ($\alpha=2$) to highly sparse, heavy-tailed distributions ($0 < \alpha < 2$).

Realizations of AR(1) processes for different values of alpha, illustrating the increase in sparsity as alpha decreases.

As shown in Figure 1, lower values of $\alpha$ result in signals characterized by long periods of relative inactivity punctuated by sharp innovations. These sparse increments are the primary challenge for global sinusoidal bases like the DCT.

Methodology and Metrics

The study evaluates transform performance using two primary information-theoretic criteria:

  1. Kullback-Leibler (KL) Divergence ($R(\mathbf{H})$): This measures the residual redundancy between coefficients in the transformed domain. A lower $R(\mathbf{H})$ indicates better decoupling.
  2. Stein’s Formula MSE: A metric based on mean-square estimation error in additive Gaussian noise, evaluating how well independent processing of coefficients preserves signal integrity.

The authors compare standard bases (Identity, DCT/KLT, Haar Wavelet) against a numerically optimized Independent Component Analysis (ICA) solution and a specifically engineered "operator-like" wavelet basis designed to invert the signal's generating differential operator.

Key Results: The Superiority of Wavelets

The core finding is a clear phase transition in optimality. While the DCT is asymptotically optimal for Gaussian data ($\alpha=2$), its performance degrades significantly as sparsity increases. Conversely, operator-like wavelets emerge as the optimal basis for sparse signals.

Comparison of the redundancy metric R(H) across different transforms as a function of alpha. Note the convergence of operator-like wavelets to the optimal ICA solution for alpha <= 1.

As illustrated in Figure 6, for highly sparse processes ($0 < \alpha \le 1$), the operator-like wavelet basis becomes indistinguishable from the optimal solution found via ICA. This provides a rigorous mathematical justification for the empirical success of wavelets in processing non-Gaussian data. Furthermore, the authors prove that for any $\alpha < 2$, the redundancy in a DCT representation grows unbounded with signal length, whereas it remains bounded for wavelet transforms.

Conclusion

This work provides a unified theoretical framework linking wavelet theory and information theory. By proving that operator-like wavelets are the optimal decoupling transforms for sparse AR(1) processes, the authors bridge the gap between empirical practice and mathematical theory. Future research will focus on extending these proofs to higher-order differential operators and multi-dimensional signals, potentially leading to new classes of custom wavelets for complex scientific datasets.

Summary updated

Abstract

It is known that the Karhunen-Lo\`{e}ve transform (KLT) of Gaussian first-order auto-regressive (AR(1)) processes results in sinusoidal basis functions. The same sinusoidal bases come out of the independent-component analysis (ICA) and actually correspond to processes with completely independent samples. In this paper, we relax the Gaussian hypothesis and study how orthogonal transforms decouple symmetric-alpha-stable (S$\alpha$S) AR(1) processes. The Gaussian case is not sparse and corresponds to $\alpha=2$, while $0<\alpha<2$ yields processes with sparse linear-prediction error. In the presence of sparsity, we show that operator-like wavelet bases do outperform the sinusoidal ones. Also, we observe that, for processes with very sparse increments ($0<\alpha\leq 1$), the operator-like wavelet basis is indistinguishable from the ICA solution obtained through numerical optimization. We consider two criteria for independence. The first is the Kullback-Leibler divergence between the joint probability density function (pdf) of the original signal and the product of the marginals in the transformed domain. The second is a divergence between the joint pdf of the original signal and the product of the marginals in the transformed domain, which is based on Stein's formula for the mean-square estimation error in additive Gaussian noise. Our framework then offers a unified view that encompasses the discrete cosine transform (known to be asymptotically optimal for $\alpha=2$) and Haar-like wavelets (for which we achieve optimality for $0<\alpha\leq1$).
BibTeX
@article{pad2015optimality,
  author = {Pedram Pad and Michael Unser},
  title = {{Optimality of Operator-Like Wavelets for Representing Sparse AR(1) Processes}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  doi = {10.1109/tsp.2015.2447494},
}

Loading related content...

Figure