On the Invariance of Cross-Correlation Peak Positions Under Monotonic Signal Transformations, with Application to Fast Time Difference Estimation

Natsuki Ueno, Ryotaro Sato, Nobutaka Ono · 2025

Read On the Invariance of Cross-Correlation Peak Positions Under Monotonic Signal Transformations, with Application to Fast Time Difference Estimation by Natsuki Ueno, Ryotaro Sato, Nobutaka Ono (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19974.txt.

Introduction

Aligning two signals in time sounds trivial until the signals are warped, and Natsuki Ueno with two co-authors prove a useful invariance. The peak of the cross-correlation between two shifted signals stays put under any monotonic reshaping of the inputs. That theorem grounds a faster way to estimate time differences. Signals can be crushed to low-bit integers first, since reshaping cannot move the peak.

Integer arithmetic replaces costly floating-point work, and number-theoretic tricks speed it further. Tests show shorter processing times than the conventional Fourier approach. Time difference estimation runs inside radar, sonar, and sensor networks. A method that trades precision in values for exactness in timing fits those uses well. The result is a theorem with an algorithm attached.

Catalog record

CREATORNatsuki Ueno, Ryotaro Sato, Nobutaka Ono
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-19974

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Invariance of Cross-Correlation Peak Positions Under Monotonic Signal Transformations, with Application to Fast Time Difference Estimation Natsuki Ueno, Ryotaro Sato, Nobutaka Ono Abstract We present a theorem concerning the invariance of cross-correlation peak positions, which provides a foundation for a new method for time difference estimation that is potentially faster than the conventional fast Fourier transform (FFT) approach for real/complex sequences. This theoretical result shows that the peak position of the cross-correlation function between two shifted discrete-time signals remains unchanged under arbitrary monotonic transformations of the input signals. By exploiting this property, we design an efficient estimation algorithm based on the cross-correlation function between signals quantized into low-bit integers. The proposed method requires only integer arithmetic instead of real-valued operations, and further computational efficiency can be achieved through number-theoretic algorithms. Numerical experiments demonstrate that the proposed method achieves a shorter processing time than conventional FFT-based approaches. I Introduction The estimation of the time difference between two shifted time-series signals [ 1 , 2 ] is a fundamental task in many areas of audio signal processing. Typical applications include the synchronization of signals [ 3 , 4 , 5 , 6 ] , the detection of a specific pattern in audio signals [ 7 ] , and various array signal processing techniques such as source/sensor localization and tracking [ 8 , 9 , 10 ] . One of the most classical yet effective approaches to time difference estimation is the peak detection of the cross-correlation function [ 11 ] . This approach has the advantage of its versatility, as it does not require special assumptions or prior knowledge on target signals. Additionally, the cross-correlation function can be efficiently calculated using fast Fourier transform (FFT) algorithms [ 12 ] , similarly to convolution. The Cooley–Tukey FFT algorithm [ 13 , 14 , 15 ] is one of the most widely used FFT algorithms, and its core concept is still relevant today. For two signals of significantly different lengths, the overlap-add (or overlap-save) method [ 16 , 17 ] is also effective when used with the FFT algorithms. Although there have been several improvements [ 12 ] , a further essential breakthrough in computational efficiency beyond these sophisticated strategies has yet to be realized. Motivated by this background, this paper presents a new theorem useful for detecting the peak positions of cross-correlation functions and proposes a fast time difference estimation method leveraging this theorem. Our theoretical result, derived from the rearrangement inequality [ 18 ] , shows that the peak position of the cross-correlation function between two shifted signals remains unchanged under any monotonic transformations applied to these two signals. Consequently, we can estimate the time difference between two shifted signals by maximizing the cross-correlation function of these signals, which have been quantized into low-bit integers, as shown in Fig. 1 . This cross-correlation-like sequence can be computed only with arithmetic operations on integers instead of real/complex numbers, which significantly reduces computational complexity. Moreover, several number-theoretic algorithms can be employed for even more efficient computation [ 19 , 20 , 21 ] . The validity of our approach was evaluated through experiments, the results of which demonstrated that the proposed method achieved a higher computational speed than the conventional method using the real/complex FFT algorithm within a specific range of signal lengths. Fig. 1: Overview of the proposed framework. Each graph on the third row represents the normalized cross-correlation function between x and y , i.e., (x\star y)/(\|x\|\cdot\|y\|) . II Notations and Preliminaries II-A Notations The sets of natural numbers excluding zero, integers, real numbers, and complex numbers are denoted by \mathbb{N} , \mathbb{Z} , \mathbb{R} , and \mathbb{C} , respectively. For a square-summable sequence x:\mathbb{Z}\to\mathbb{R} , \|x\| denotes the \ell_{2} norm of x . II-B Formulation of Time Difference Estimation Problem Let x,y:\mathbb{Z}\to\mathbb{R} be real-valued discrete-time signals with finite lengths, meaning they have only a finite number of non-zero values. The cross-correlation function between x and y , denoted by x\star y:\mathbb{Z}\to\mathbb{R} , is defined as (x\star y)[n]\coloneqq\sum_{m\in\mathbb{Z}}x[m]\cdot y[m+n]\quad(n\in\mathbb{Z}). (1) Since x and y have finite lengths, the sum on the right-hand side of ( 1 ) always converges, and x\star y also has a finite length. As is well known, the time difference between two shifted signals can be estimated by maximizing their cross-correlation function. In mathematical expression, if x and y satisfy x[n]=a\cdot y[n+\nu]\quad\forall n\in\mathbb{Z} (2) for some \nu\in\mathbb{Z} and a\in(0,\infty) , their cross-correlation function is maximized at \nu , i.e., (x\star y)[n]\leq(x\star y)[\nu]\quad\forall n\in\mathbb{Z}. (3) This property follows immediately from the Cauchy–Schwarz inequality and the unitarity of the time shift operation. II-C Conventional Algorithms Using Real/Complex FFT When x and y have a length of N\in\mathbb{N} , meaning their supports are within a range of N consecutive integers, the “brute-force” computation of x\star y requires \mathcal{O}(N^{2}) multiplications on \mathbb{R} . However, this computational complexity can be reduced by using FFT algorithms with zero padding. For example, the Cooley–Tukey FFT algorithm [ 16 , 17 ] allows the computation of x\star y with \mathcal{O}(N\log N) multiplication on \mathbb{C} (or equivalently on \mathbb{R} ). Additionally, we also mention the prime-factor FFT algorithm [ 14 ] , which utilizes the Chinese remainder theorem, as another type of FFT algorithm, although it can be used in combination with the Cooley–Tukey FFT algorithm. III New Theorem and Its Application to Fast Time Difference Estimation III-A Theoretical Result Our main result, which forms the basis for fast time difference estimation, is summarized as follows. Theorem 1 . Let two finite-length signals x,y:\mathbb{Z}\to\mathbb{R} satisfy ( 2 ) for some \nu\in\mathbb{Z} and a\in(0,\infty) . Then, for any monotonically non-decreasing functions \varphi,\psi:\mathbb{R}\to\mathbb{R} satisfying \varphi(0)=\psi(0)=0 , the cross-correlation function between \varphi\circ x and \psi\circ y is maximized at \nu , i.e., ((\varphi\circ x)\star(\psi\circ y))[n]\leq((\varphi\circ x)\star(\psi\circ y))[\nu]\quad\forall n\in\mathbb{Z}. (4) Remark . This theorem does not guarantee an order-preserving relationship between (\varphi\circ x)\star(\psi\circ y) and x\star y . Their elements are not necessarily in the same order except at the peak position, as illustrated in Fig. 1 . Nevertheless, both functions are maximized at the same position \nu . It is also worth noting that (\varphi\circ x)\star(\psi\circ y) can exhibit multiple peaks, although always including \nu , even when x\star y has only a single peak. Proof. For each fixed n\in\mathbb{Z} , let \Lambda_{n}\subset\mathbb{Z} be the index set of all m\in\mathbb{Z} such that x[m]\neq 0 or y[m+n]\neq 0 . Then, by definition, we have \displaystyle((\varphi\circ x)\star(\psi\circ y))[n]=\sum_{m\in\Lambda_{n}}(\varphi\circ x)[m]\cdot(\psi\circ y)[m+n]. (5) In addition, let M_{n}\in\mathbb{N} be the number of elements in \Lambda_{n} , and u_{n},v_{n}:\{1,\ldots,M_{n}\}\to\mathbb{R} be respectively the descending sorts of (x[m])_{m\in\Lambda_{n}},(y[m+n])_{m\in\Lambda_{n}} . Then, since \varphi\circ u_{n} and \psi\circ v_{n} are also the descending sorts of ((\varphi\circ x)[m])_{m\in\Lambda_{n}} and ((\psi\circ y)[m+n])_{m\in\Lambda_{n}} , respectively, we have \displaystyle\sum_{m\in\Lambda_{n}}(\varphi\circ x)[m]\cdot(\psi\circ y)[m+n] \displaystyle\quad\leq\sum_{m=1}^{M_{n}}(\varphi\circ u_{n})[m]\cdot(\psi\circ v_{n})[m] (6) from the rearrangement inequality (Theorem 368 in [ 18 ] ). On the other hand, from ( 2 ) and the monotonically non-decreasing properties of \varphi and \psi , the two sequences ((\varphi\circ x)[m])_{m\in\Lambda_{n}} and ((\psi\circ y)[m+\nu])_{m\in\Lambda_{n}} are aligned in the same order. Moreover, since \varphi(0)=\psi(0)=0 , these sequences include all non-zero elements of \varphi\circ x and \psi\circ y . Therefore, we have \displaystyle((\varphi\circ x)\star(\psi\circ y))[\nu] \displaystyle=\sum_{m\in\Lambda_{n}}(\varphi\circ x)[m]\cdot(\psi\circ y)[m+\nu] \displaystyle=\sum_{m=1}^{M_{n}}(\varphi\circ u_{n})[m]\cdot(\psi\circ v_{n})[m]. (7) Finally, from ( 5 )–(

Read the complete text