Optimal Transport for Time Series Imputation

Authors: Hao Wang, zhengnan li, Haoxuan Li, Xu Chen, Mingming Gong, BinChen, Zhichao Chen
Primary area: learning on time series and dynamical systems
Keywords: Time series, Imputation

Abstract:
Missing data imputation through distribution alignment has demonstrated advantages for non-temporal datasets but exhibits suboptimal performance in time-series applications. The primary obstacle is crafting a discrepancy measure that simultaneously (1) captures temporal patterns—accounting for periodicity and temporal dependencies inherent in time-series—and (2) accommodates non-stationarity, ensuring robustness amidst multiple coexisting temporal patterns. In response to these challenges, we introduce the Proximal Spectrum Wasserstein (PSW) discrepancy, a novel discrepancy tailored for comparing two \textit{sets} of time-series based on optimal transport. It incorporates a pairwise spectral distance to encapsulate temporal patterns, and a selective matching regularization to accommodate non-stationarity. Subsequently, we develop the PSW for Imputation (PSW-I) framework, which iteratively refines imputation results by minimizing the PSW discrepancy. Extensive experiments demonstrate that PSW-I effectively accommodates temporal patterns and non-stationarity, outperforming prevailing time-series imputation methods. Code is available at https://github.com/FMLYD/PSW-I.

Decision: accept (poster)
Reviewer scores: 8, 8, 5

Reviews and discussion:
<thread>
creation date:
1730533491520

thread_type:
official_review

<thread_object>
creator: reviewer_4wtk

<content>
summary:
The paper proposes an optimal transport (OT) based time-series imputation method. The authors claim that naive application of OT does not work for time-series data. The proposed method consider applying OT in the frequency domain of the original data, called pairwise spectrum distance (PSD). Further, to deal with multiple modes, proximal spectral Wasserstein (PSW) distance is also proposed, in which mass constraint is removed to make transportation more flexible.

strengths:
- Using OT to impute time-series data is an interesting approach.

- Empirical evaluation shows high performance.

weaknesses:
- Some technical justification is vague. Clearer descriptions would be desired.

- Introduction is a bit too abstract about the proposed method. It describes what problem is solved in the paper, but does not describe the basic technical idea how it is achieved.

questions:
- In 'Contributions', the authors mention that PSW-I eliminates the need for masking, but PSW-I seems to use masking (eg as shown in Fig3). What does this description mean?

- What does Lemma 3.2 indicate? How do you know 'deviates more from the typical elements of \beta'? Further, how do you know the PSW discrepancy avoid the problem indicated by this lemma? In Theorem C.2, the perturbation in PSW discrepancy is shown. Is it possible to compare this with Lemma 3.2? Even if it is possible, what does it mean? Is it clear how large (or small) perturbation caused by outliers ultimately affect the final imputation?

- Although D_KL is used in (2), T 1_m and T^T 1_n is not a probability distribution (because the normalization (sum equals 1) constraint is removed). How are they normalized?

- What is the definition of the 'DFT matrix' in the gradient? How does the gradient of (2) become \Delta_alpha_i P and \Delta_beta_j P? The second term in (2) disappear? The optimality condition wrt T is considered in this gradient calculation?  

- After (1), D is squared distance, while in definition 3.1 D is distance without square. Which is correct?

Minor issues:

- In the end of p3: Fig. 4 should be Fig 1? In Fig 1(a), the left is W^(F)?

- The first word of Sec3.2: 'time-series' -> 'Time-series'
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681200126

thread_type:
official_review

<thread_object>
creator: reviewer_8unw

<content>
summary:
The paper proposes a time series imputation method based on optimal transport. The key idea is the combination of a frequency-based Wassertein discrepancy  and selective matching regularization. Theoretical justification is also provided. The experimental results show the imputation accuracy outperforms many sota methods.

strengths:
1. An interesting and well-motivated design of the spectral-enhanced Wasserstein distance (WD)
2. A theoretical justified design of proximal spectral WD to account for non-stationarity.
3. seemingly excellent performance in real-world benchmark datasets.

weaknesses:
1. The biggest issue from my end is the lack of standard deviation. From Table 1, the error of the proposed method seems really good, but i am not informed if these results are averaged over multiple train/test runs or just one run. To avoid cherry picking, the authors are encouraged to highlight how these numbers were obtained, what the training/test splits were, and what hyperparameter selection/cross-validation process was involved, etc.  Similar expectations apply to table 3 and 4. 

2. Lack of convergence discussion/analysis. From Fig. 3 and Section 3.4, the imputation procedure seems to repeatedly sample patches from the time series, compute PSW, and use the gradient of the PSW to update the imputation. There seems a lack of convergence guarantees or discussions about this procedure. Can authors provide at least some discussion on this? 

3. Data noise issue. Real time series data often includes noises. That means, just computing the distance after DFT in lin154 might be affected by data noises. Have the authors consider any methods or trade-offs, such as low-pass filters, in your SWD definition, to improve the robustness and/or counteract the noise effect?

questions:
see above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730744230858

thread_type:
official_review

<thread_object>
creator: reviewer_fn5t

<content>
summary:
Providing methods for time series imputations while respecting the temporal dependence.

strengths:
- Very good empirical investigation.

- Clear presentation.

weaknesses:
NA

questions:
- What if the time series components are observed at different temporal frequencies (say days vs. hours, or hours vs. mins)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732695538790

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary by Authors

comment:
We are grateful to all reviewers for their helpful comments regarding our paper. We are pleased that Reviewers 8uNw and 4Wtk appreciate the significance of methodology to enhance time-series imputation, finding our method novel and well-motivated. All reviewers find our empirical results promising. Below is a summary of our responses:

- To Reviewer fN5T: We have discussed a case where the time-series are irregularly sampled, and proposed some feasible extensions of PSW-I to accommodate it.
- To Reviewer 8uNw: We have included experiments across different random seeds, clarified the hyper-parameter selection process, underscored the convergence analysis, and conducted additional experiments with noisy dataset.
- To Reviewer 4Wtk: **After thorough discussion, the only remaining concern was the need to add a clarification on gradient calculation in the main text. This is an actionable item, and we have addressed it by including the necessary clarification on page 5, footnote 1.** Additionally, we have thoroughly refined the technical justifications and the narrative of the introduction to better highlight the fundamental technical concepts. **Therefore, we believe that all concerns raised by Reviewer 4Wtk have now been satisfactorily resolved.**

Please refer to our detailed responses to each point raised. We have also uploaded a revised manuscript with changes highlighted in blue. Hopefully our revisions and clarifications reinforce your confidence and support in our work.

Thank you again for your valuable time and expertise.
</content>
</thread_object>

</thread>
<thread>
creation date:
1744044054998

thread_type:
public_comment

<thread_object>
creator: ~prabhant_singh2

<content>
title:
Code request

comment:
Dear authors,

Thanks for a great paper; it was a really good read. Is it possible to get the code? I noticed that the code on github is deleted, Is there a new repository link?
Thank you
</content>
</thread_object>

</thread>


Metareview:
metareview:
This submission tackles missing data imputation for time series via a new discrepancy measure. They target some difficult issues such as non-stationarity and periodicities, showing that the proposed proximal spectrum Wasserstein allows flexible learning and is amenable to the imputation framework. Reviewers concerns seemed addressed after the rebuttal phase. In particular, they already found the work novel with theoretical support and some questions and technical details were largely resolved.