CS Paper Radar

Moments of crosscorrelation demerit factors of binary sequences

Daniel J. Katz, Harmony M. Vargas

cs.IT cs.DMeess.SPmath.COmath.PR ·submitted 2026-09-04 23:25 UTC · v1
unusual

Abstract

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar. The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor. For each positive integer $\ell$, we endow the $2^{2 \ell}$ pairs of binary sequences of length $\ell$ with uniform probability measure and study the distribution of their crosscorrelation demerit factors. Sarwate showed that the mean value is always $1$ regardless of length $\ell$. We develop a method for finding an exact formula for the $p$th central moment (for any positive integer $p$) as a function of $\ell$. Formulae for the variance and third central moment ($p=2$ and $3$) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations. Our theory also shows that all the central moments must be strictly positive for $p\geq 2$ and $\ell \geq 3$.

Comment
32 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A class of Niho type four-valued cross-correlation functions between sequences of different periods

cs.IT ·2026-10-25 ·Yao Yao, Yufei Wang, Yongbo Xia, Nian Li, Xiangyong Zeng
similarity 0.58
Abstract

Determining the cross-correlation distributions between $m$-sequences and their decimated sequences is an important problem in sequence design. For two positive integers $n$ and $k$ with $n=2k$, this paper investigates the cross-correlation function between a binary $m$-sequence $\{u(t)\}$ of period $2^{n}-1$ and its $2^{\gcd(s,k)}+1$ short-period decimated sequences $\{u(dt+l)\}$, where the decimation $d=\frac{2^s}{2^s+1}(2^k-1)+1$ satisfies $1<s<n$ and $v_2(s)>v_2(k)$. The cross-correlation function is proved to be four-valued and its value distribution is completely determined. Several previously known binary cross-correlation functions are included in our result as special cases.

0.26

Frequency Moments Beyond Equality: Streaming Cosine Density Moments

cs.DS ·2026-09-07 ·Qin Zhang
theory similarity 0.57
Abstract · 44 pages

For a stream of nonzero vectors $x_1,\ldots,x_n\in\mathbb{R}^d$, let $u_i=x_i/\|x_i\|_2$. We define the cosine density of the $i$-th stream element by $D_i:=\sum_{j\in[n]}\langle u_i,u_j\rangle$ and study the density moments $M_p:=\sum_{i\in[n]}D_i^p$ in both the signed- and nonnegative-cosine regimes. These quantities are similarity-aware analogues of classical frequency moments: replacing cosine similarity by equality (that is, $D_i = \sum_{j\in[n]} \mathbf{1}\{u_j = u_i\}$) gives $M_p=F_{p+1}$ and, in particular, $M_{-1}=F_0$, the number of distinct elements. We give one-pass streaming algorithms and lower bounds whose dependence on $d$ is tight up to logarithmic factors for $p=-1$, $p=1$, and even $p \ge 2$ (the latter under signed cosine), and whose exponents differ by less than $1/2$ for odd $p \ge 3$ under nonnegative cosine. Our results thus extend several fundamental statistics from the classical data stream literature to cosine similarity, a widely used measure for comparing vector embeddings in modern AI systems. The main challenge in proving a space lower bound for nonnegative cosine is to eliminate unwanted contributions without relying on pairs of opposite vectors. We address this through a construction that we call \emph{equal-sum moment isolation}: two insertion-only prefixes have the same cardinality and vector sum, and a finite-difference comparison cancels the baseline shared by all their vectors while isolating the desired higher-order signal. This proof framework may be useful for other insertion-only streaming lower bounds, where direct cancellation is not possible.

0.45

Extended Proofs for Encrypted Sensing in Bistatic Radar: Unified Analysis and Randomly Activated Arrays

eess.SP ·2026-09-15 ·Tianrui He, Ziheng Zheng, Guozheng Sun, Tianyao Huang, Yimin Liu
similarity 0.52
Abstract

This supplementary material provides the complete mathematical development for the signal-to-noise ratio loss (SNRL) analysis of pulse-wise spatially randomized encrypted sensing. We first derive a reduced model in which the transmit-side randomization is represented by an independent and identically distributed complex spatial coefficient. Based on this model, we establish the almost-sure and mean asymptotic SNRL, derive the leading bias and variance for a finite coherent processing interval (CPI), and obtain closed-form coefficient moments and asymptotic SNRL for independent Bernoulli element activation. These results complement the concise statements and proof sketches in the associated paper.

0.22

On the Optimality of OFDM for Aperiodic Ranging

eess.SP cs.IT ·2026-10-02 ·Yifeng Xiong, Fan Liu, Ya-Feng Liu, Shi Jin, Jianhua Zhang
similarity 0.51
Abstract · 36 pages, 3 figures

We study the expected aperiodic autocorrelation sidelobes of random communication symbols transmitted through a unitary modulation matrix. We consider proper sub-Gaussian constellations, namely those with fourth absolute moment $μ_4<2$ and zero pseudo-variance, including the commonly used uniform square quadrature amplitude modulation (QAM) and uniform phase-shift keying (PSK) constellations. For every prescribed lag, we determine the exact minimum expected sidelobe level (ESL) and a unitary modulation attaining it by applying a normalized inverse discrete Fourier transform (IDFT) separately on each chain of sample indices spaced by that lag. The full orthogonal frequency division modulation (OFDM) modulation attains this minimum if and only if the lag divides the block length $N$. Combining this criterion with the complete characterization of the minimizers at lag one, we show that a unitary modulation minimizes the ESL simultaneously over the first $r$ positive lags, called the prefix $\{1,\ldots,r\}$ with $1\le r<N$, if and only if every lag in that prefix divides $N$. In particular, simultaneous optimality over all positive lags is impossible for $N\ge 3$. We also prove that OFDM globally minimizes the partial expected integrated sidelobe level (EISL), defined as the sum of the ESLs over a selected subset of positive lags, for every such prefix. This also resolves the full EISL conjecture when $r=N-1$.

0.25

Comment on "Symmetric Pseudo-Random Matrices"

cs.IT math.PRmath.NT ·2026-09-25 ·Chin Hei Chan
published similarity 0.48
Abstract · 6 pages, no figures; Comment on IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 3179-3196, Apr 2018 (arXiv:1702.04086)

In 2018, Soloveychik, Xiang and Tarokh considered a pseudo-random symmetric circulant matrix constructed from binary Golomb sequences of length $n=2^m-1$, and claimed a proof that its empirical spectral distribution converges almost surely to the semicircle law as $n$ grows to infinity by the method of moments. In this comment note we show that their argument contains several technical flaws and inappropriate applications of technical lemmas. Instead we demonstrate that the eigenvalues of the matrix are simply a normalized twisted Kloosterman sum varying over the multiplicative character, to which we apply Katz's result directly to establish the asymptotically semicircle spectral distribution deterministically.

0.37

Harmonic higher weight distributions, Simonis' approach of MacWilliams identity and moments

cs.IT math.COmath.NT ·2026-08-16 ·Himadri Shekhar Chakraborty, Mehedi Hasan Tanver
theory similarity 0.47
Abstract · 19 pages

We present a combinatorial proof of Simonis type MacWilliams identity for harmonic higher weight distributions of linear codes. Furthermore, we investigate the statistical moments of the harmonic higher weight enumerators for random linear codes. Defining the enumerators via rank functions of the generator matrices of linear codes, we prove that its expectation vanishes for all non-trivial harmonic functions due to the inherent symmetry of random matrices, and we also derive an explicit, non-trivial formula for the covariance.

0.38

Universality of approximate message passing under a fourth-moment tail condition

cs.IT math.PRmath.ST ·2026-10-20 ·Ripunjay Dwivedi, Taejoon Kim
theory similarity 0.46
Abstract · 35 pages, no figures

We prove state evolution for approximate message passing (AMP) with rectangular random matrices whose entries are independent, centered, and variance-normalized. The row and column dimensions grow with a ratio that converges to a positive finite limit. The entry laws may differ across coordinates and dimensions, and we assume uniform integrability of the fourth powers of the rescaled entries. For entries sampled independently from a fixed law, a finite fourth moment suffices, with no requirement for higher moments. The nonlinearities are continuously differentiable and globally Lipschitz, with bounded continuous first state derivatives. The signal and noise have independent and identically distributed coordinates with finite moments of all orders, and are independent of each other and of the matrix. At every fixed number of iterations, empirical averages of pseudo-Lipschitz functions of order two converge in probability to the limits specified by Gaussian state evolution. These averages include empirical second moments and products of trajectory coordinates. The proof combines an aggregate bound on third derivatives with randomized Lindeberg replacement and operator-norm truncation, without matching third moments or invoking a non-Gaussian universality theorem. We also show that independence of complementary projected components for every deterministic rank-one constraint pair characterizes Gaussian entries. This identifies the limitation of extending Gaussian conditioning identities to independent non-Gaussian matrices. Finally, a variance-profile example shows that average variance normalization alone does not ensure the homogeneous state evolution limits.

0.24

A positive resolution of the gap-entropy conjecture

cs.LG stat.ML ·2026-09-09 ·P. M. Aronow, Nathan Kallus, Patrick Lopatto
theory similarity 0.46
Abstract

We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.

0.50