Introduction
Segmentation, or change-point detection, is a fundamental task in signal processing, involving the division of sequential data into homogeneous sections. Traditional methods typically minimize squared distances to segment centroids. However, these approaches suffer from two primary weaknesses: extreme sensitivity to outliers and susceptibility to local minima due to non-convexity. This work proposes a convex optimization framework that explicitly models outliers, ensuring both global optimality and robustness.
Methodology
The proposed framework utilizes a convex objective function composed of three distinct terms:
- Data Fidelity: Measures the fit between data points and segment centroids ($\mu_i$).
- Sparsity-Inducing Regularization: Penalizes differences between adjacent centroids ($\mu_{i+1} - \mu_i$), encouraging piecewise constant solutions that define segments.
- Outlier Modeling: Introduces a dedicated variable $z_i$ for each data point to "absorb" errors from anomalous samples. A penalty on $z_i$ ensures that only a small fraction of the data is classified as outliers.
Analytically, solving for the outlier variables transforms the objective into a multidimensional Huber loss, a classic robust statistical tool.
Algorithms
Two primary algorithms are developed:
- ORCS (Outlier-Robust Convex Sequential): Employs an alternating optimization strategy between outlier detection and segment estimation.
- TD-ORCS (Top-Down ORCS): A computationally efficient hierarchical version that greedily splits sequences. It allows direct control over the number of segments ($K$) and outliers ($M$).
Theoretical Recovery
A significant theoretical finding is that specific weighting of the penalty term ($w_i = \sqrt{i(n-i)}$) allows the convex relaxation to exactly recover the optimal solution of the original non-convex problem for the two-segment case.
Experimental Evaluation
The authors evaluated the framework on two speech-related datasets:
- TIMIT Phonetic Corpus: Biphone segmentation with added synthetic transients to simulate outliers.
- Radio Show Recording: A 35-minute recording with complex segments and 5-second bursts of "hammer stroke" noise as non-stationary outliers.
Results
On the TIMIT dataset, the proposed TD-ORCS and its weighted variant (WTD-ORCS) demonstrated superior robustness. While baseline methods like W-LARS saw a significant increase in mean error as outlier contamination reached 30%, the ORCS-based methods maintained a stable and lower error rate.
In the Radio Show task, performance was measured using the R-measure, which is robust to over-segmentation. Standard Bottom-Up (BU) and Bayesian (BCP) methods failed significantly as noise increased, whereas ORCS and TD-ORCS remained steady even with 16% outlier contamination.
Conclusion
This paper introduces a robust, convex approach to sequential data segmentation. By explicitly modeling outliers and utilizing a weighted convex relaxation, the proposed TD-ORCS algorithm provides a reliable and efficient solution for noisy real-world data. Future research may explore more complex noise models and real-time processing capabilities.
Summary updated