Abstract
Sparse representation is a fundamental technique in signal processing, yet selecting the optimal number of coefficients ($k$) remains a significant challenge. This paper introduces a principled method for finding a unique and optimal $k$ for one-dimensional time series by leveraging the Minimum Description Length (MDL) principle under a lossless compression constraint. We demonstrate that this optimal sparsity level serves as a powerful feature for detecting physiological changes. Specifically, in a human viral challenge study using wearable sensor data, the variance of the optimal $k$ significantly increases in subjects who become infected ("shedders") compared to "non-shedders." This approach provides a sensitive, information-theoretic metric for anomaly detection and health monitoring.
Introduction
The concept of sparse representation—representing a signal using a minimal number of non-zero coefficients from a dictionary—is central to modern data analysis. However, determining the "right" level of sparsity ($k$) involves a difficult trade-off: a value too small leads to information loss, while a value too large results in overfitting to noise. While overcomplete dictionaries are often used for complex signals, they frequently lack a unique, optimal representation. This research addresses this gap for one-dimensional data by combining orthonormal bases, such as wavelets, with a mathematically rigorous selection criterion rooted in information theory.
Methods: Finding the Optimal Sparsity
The proposed method models a data block as a combination of a sparse wavelet representation (via Discrete Wavelet Transform, DWT) and Gaussian white noise. To select the optimal $k$, the authors employ the Minimum Description Length (MDL) principle. MDL frames model selection as a communication problem: the best model is the one that minimizes the total codelength required to describe both the model and the data given that model.
The core contribution is a mathematical proof (Theorem 1) that defines the optimal $k$ by balancing three components:
- The bits required to identify which $k$ coefficients are non-zero.
- The bits required to store the values of these coefficients.
- The bits required to describe the residual error (noise).
For anomaly detection, the researchers use an "atypicality" framework. A data segment is flagged as an anomaly if it can be described more efficiently using a universal encoder than by an encoder specifically trained on "typical" baseline data.
Experimental Evaluation
The method was evaluated using a human viral challenge study dataset. Participants were exposed to the Human Rhinovirus (HRV) while wearing Empatica E4 devices. The study focused on skin temperature time series, downsampled to one sample every 10 seconds. Participants were categorized as "shedders" (infected) or "non-shedders" based on laboratory viral load tests.
Results and Discussion
The optimal sparsity level $k$ proved to be a highly sensitive indicator of infection. For "shedders," the standard deviation of the optimal $k$ increased by a ratio of approximately 1.7 after viral exposure. In contrast, for "non-shedders," this ratio remained near 1.0, indicating no significant change in signal complexity.
The sensitivity of the MDL-based approach significantly outperformed standard criteria like the Akaike Information Criterion (AIC) or Bayesian Information Criterion (BIC). As shown in the study's comparative analysis, the ratio of $k$ standard deviation for shedders was 1.73 using the proposed method, compared to just 1.05 for AIC and 1.15 for BIC. Furthermore, the atypicality framework successfully identified anomalous segments in infected subjects, all of which occurred post-inoculation, with no false positives in the non-shedder group.
Conclusion
By adhering to a lossless compression constraint, the "optimal" $k$ becomes a stable and unique property of a data segment, transforming sparsity from a compression parameter into a discriminative physiological feature. While currently focused on one-dimensional time series, this work establishes a robust foundation for information-theoretic data discovery. Future research will explore extending these principles to multidimensional data and implementing the algorithms on wearable hardware for real-time health monitoring and early warning systems.
Summary updated