Source-linked AI summary
Fast Time-Domain MLE for Period Estimation of Pulse Trains
Sebastian Schertler, Daniel Guger, Stefan Schuster, Stefan Scheiblhofer, Mario Huemer, Alexander Haberl, Johann Reisinger, Oliver Lang
TL;DR
Periodic pulse-train estimation is accurate in the time domain but computationally costly because the MLE requires extensive grid searches. The paper uses sparsity-aware matrix operations and separates correlation from gathering, reducing runtime and memory for real-time-oriented implementations.
Problem
The time-domain MLE can achieve high estimation accuracy but its computationally expensive grid search limits applicability to long data records and real-time settings.
Method
The paper exploits signal sparsity with sparse matrix multiplication and separates dense projections into sequential correlation and gathering operations.
Results
JIT compilation reduces the uncompiled baseline’s GPU memory requirement by 89%, while compiled correlation and gather uses 167 MB.
Takeaways & Limitations
The resulting implementation is described as highly suitable for real-time industrial tasks, while correlation and gathering scales with the sum of measurements and grid points rather than their product.
Abstract
from arXiv · showhide
Parameter estimation of periodic pulse trains is a critical task in numerous automated sensing and diagnostic applications. While estimation in the time domain provides superior accuracy in low signal-to-noise ratio environments, its high computational complexity frequently precludes its use in real-time systems. This paper investigates algorithmic optimizations to reduce runtime by leveraging recent advancements in computing architectures. Exploiting the inherent sparsity of the signal via sparse matrix multiplication kernels yields a substantial decrease in inference time. Furthermore, by separating the dense matrix projections into sequential cross-correlation and sparse summation steps, we fundamentally reduce both runtime and memory complexity. These optimizations drastically shrink the memory footprint, making time-domain estimation feasible for large datasets in real-time settings.
I. INTRODUCTION
Periodic pulse estimation matters in sensing applications, but the time-domain MLE’s accuracy comes with a computationally expensive grid search. This work targets runtime and memory reductions for parallel hardware.
- Periodic pulse parameter estimation supports industrial production and radar time-of-arrival applications involving short pulses separated by noise-only gaps.
- Frequency-domain methods face wide bandwidths for short pulses, potentially requiring large model orders and substantial zero-padding for resolution.
- The previously derived time-domain MLE asymptotically attains the CRLB but requires a computationally expensive grid search for long data records.
- The proposed work optimizes algorithmic complexity and implementation to reduce runtime and memory on heavily parallelized hardware.
- The signal model contains K periodically shifted, non-overlapping pulses scaled by A, with pulse duration Tp much shorter than period T.
- Because the cost function has limited support and vanishing gradients across much of parameter space, gradient-based optimization is ineffective and fine grids become important.
III. ALGORITHMS AND COMPLEXITY
The complexity analysis examines how runtime and memory scale with grid points, measurements, pulses, and nonzero pulse samples using Big O notation.
- The analysis focuses on runtime and memory requirements as the number of grid points G, measurements N, pulses K, and nonzero samples Np changes.
- Big O notation is used to characterize scaling rather than report a fixed execution time.
- The complexity study is aimed at identifying how algorithmic costs depend on the principal signal and search dimensions.
A. Base algorithm
The baseline algorithm computes intermediate projections and quadratic forms for each parameter setting. Its sensitivity to period mismatch is illustrated as pulse counts increase.
- The baseline first derives v(β) = h(β)^T x and m(β), then forms u(β) = m(β)v(β) before evaluating J(β) = v^T u.
- Avoiding explicit calculation of h(β) also produces bα = u as an intermediate result.
- As pulse count increases, a small difference between assumed period ˜T and true period T causes missed pulses.
B. Leveraging sparsity
Exploiting pulse-train sparsity reduces the computations and runtime of the estimator, while precomputation can further accelerate inference at increased memory cost.
- B. Leveraging sparsity: O(KNp) complexity results from incorporating the signal structure into h(β)^T x.This removes multiplications involving zeros and reduces the required computations.
- B. Leveraging sparsity: Sparse-matrix formats such as CSR reduce runtime by a factor of KNp.
- B. Leveraging sparsity: Precomputing h(β) and (h(β)^T h(β))^-1 can further decrease inference runtime for large data records.The trade-off is increased memory complexity, with h(β)^T requiring O(GKNp).
C. Correlation + Gather
The correlation-and-gather method separates pulse-shape correlation from sparse periodic summation, reducing dependence on the product of measurements and grid points. Its Taylor approximation handles sub-sample shifts but is constrained by pulse bandwidth and phase variation.
- C. Correlation + Gather: The operation h(β)^T x approximately correlates measurements with the known pulse shape and sums the results periodically.
- C. Correlation + Gather: Taylor expansion approximates shifted pulses so correlation can use pulse values and derivatives sampled at ε = 0.
- C. Correlation + Gather: A sparse matrix ẑh(β) ∈ R^N×2 gathers correlation results while decoupling discrete pulse locations from continuous sub-sample shifts.Its columns encode nearest-sample pulse positions and the corresponding shifts ε.
- C. Correlation + Gather: The Taylor approximation is valid only when the maximum sub-sample shift does not significantly change the highest-frequency phase.Higher accuracy requires a higher-order approximation with added runtime complexity.
- C. Correlation + Gather: Runtime complexity changes from dependence on the product GN to linear scaling with their sum after separating correlation and gathering.
IV. IMPLEMENTATION AND RESULTS
The implementation uses PyTorch to benchmark baseline and optimized grid-evaluation strategies across computing devices, while compilation and batching address system-level execution costs.
- IV. IMPLEMENTATION AND RESULTS: PyTorch was selected for optimized matrix multiplication and convolution support across computing devices from different vendors.
- IV. IMPLEMENTATION AND RESULTS: GPU execution benefits from highly parallelized architectures for large-scale matrix multiplications compared with CPUs.
- IV. IMPLEMENTATION AND RESULTS: Memory bandwidth and data transfers can bottleneck performance, motivating whole-pipeline JIT compilation with torch.compile.
- IV. IMPLEMENTATION AND RESULTS: The baseline is implemented either by constructing h(β) during inference or by precalculating it for batched matrix multiplication when memory permits.
- IV. IMPLEMENTATION AND RESULTS: Precalculating constant h(β) enables reuse during inference and can reduce runtime through efficient cuBLAS-backed matrix multiplication.
A. Runtime
Benchmarking shows that batched matrix multiplication outperforms separate grid-point processing on GPUs, while sparse matrices further reduce execution time.
- A. Runtime: Batched matrix multiplication is faster than processing grid points separately when using a GPU.
- A. Runtime: Sparse matrices strongly reduce execution time by reducing the number of multiplications.
- A. Runtime: Compiled correlation plus gather is more than five times faster than the alternatives when a GPU is available.
B. Memory
GPU implementations substantially reduce inference runtime and memory, with correlation and gather achieving the smallest reported VRAM footprint.
- VRAM consumption: 1 GB is consumed by the correlation and gather approach before JIT compilation, compared with over 37 GB for the uncompiled baseline.The baseline stores massive intermediate projection matrices, while the correlation and gather approach avoids that dense representation.
- VRAM consumption: 89% memory reduction is obtained when JIT compilation fuses the uncompiled baseline’s intermediate steps.Dense batched matrix multiplication remains at 13.4 GB because it stores zeros.
- Runtime comparison: Fig. 4 compares standard and JIT algorithm versions on CPU and GPU hardware for inference runtime.The figure evaluates runtime across both processor types and implementation variants.
- VRAM consumption: 167 MB is the minimal VRAM footprint achieved after JIT compilation of the correlation and gather implementation.JIT compilation further optimizes the approach’s sequential operations.
C. Estimation Performance
The implementations exhibit very similar estimation performance, while time-domain signal models outperform multiharmonic estimators in low-SNR regions.
- MSE performance: All previously discussed implementations exhibit very similar MSE performance across the evaluated noise levels.The comparison includes time-domain implementations and multiharmonic pitch-estimator variants.
- MSE performance: In low-SNR regions, time-domain signal models outperform multiharmonic signal-model-based estimators.The figure caption reports that methods not using pulse shortness perform worse at low SNR.
V. CONCLUSION
The proposed optimizations reduce the computational burden of short-periodic-pulse MLE by decoupling grid size from measurement count and using correlation and gather for GPU efficiency.
- V. CONCLUSION: The number of grid points G decouples from the number of measurements N in runtime and memory complexity.This addresses the fine grid resolutions required for accurate short-pulse MLE results.
- V. CONCLUSION: The correlation and gather approach leverages GPU architecture and driver optimizations to provide strong efficiency gains.The conclusion identifies the resulting implementation as highly suitable for real-time industrial tasks.