CS Paper Radar

Spherical ESPRIT by Paired Small Circles and Infinitesimal Rotations

Albert Fannjiang

eess.SP math.CA ·submitted 2026-09-26 23:46 UTC · v1
theory

Abstract

We study the recovery of a finite three-dimensional point cloud from its spherical Fourier signal subspace at a fixed wavenumber. Two ESPRIT constructions are analyzed. The first uses finite shifts between paired small circles; the second uses angular derivatives on the whole sphere. Both recover the same commuting coordinate matrices, either through their finite exponentials or directly from a coupled linear system. We prove that the continuous generator system is injective for every distinct point cloud and that one guard harmonic degree preserves the retained equations exactly. For $s$ targets, the cutoff $K\ge s$ gives generic finite identifiability, but not uniform conditioning. We also derive a finite-cutoff perturbation bound. The accuracy of the coordinate estimates is a separate issue. A one-target perturbation calculation shows that the original generator estimate can retain a nonzero bias as the wavenumber increases. To address this bias, we use the generator eigenbasis to separate approximate atoms and recover their locations from amplitude-normalized phases. Under pointwise atom dominance, the resulting error is $O(κ^{-1})$; for a dominant two-atom mixture at fixed separation, it is $O(κ^{-2})$. Experiments on structured point clouds with smooth perturbations compare the two constructions and their use as initializers for a common MUSIC refinement.

Comment
40 pages

Closest papers

Nearest neighbours by meaning across the whole index.

An $O(L^3)$ Spherical Harmonic Transform on $L^2$ Samples

eess.SP math.NA ·2026-11-12 ·Zubair Khalid
theorycode/data similarity 0.63
Abstract · 13 pages, 7 figures, 1 table. Code: https://github.com/zubairkhalid1/osht

For the representation of signals on the sphere band-limited at $L$ using the optimal number of samples, $L^2$, equal to the number of degrees of freedom in harmonic space and placed on $L$ iso-latitude rings, we develop a spherical harmonic transform (SHT) that is theoretically exact, requires no solution of linear systems and no precomputation beyond the placement of the rings, and has complexity $O(L^3)$. The transform rests on the observation that, for each order $m$, the samples on the rings that resolve order $m$ are a complete set of samples for the order-$m$ profile of the signal, so that its values on the remaining rings follow from a closed-form Lagrange basis, the sampling functions of order $m$. We prove that the proposed optimal-dimensionality SHT (OSHT) recovers every band-limited signal exactly in exact arithmetic, so that the $L^2$ samples admit a sampling theorem in the collocation sense. For the final harmonic analysis we give two exact back-ends: Gauss-Legendre quadrature of the interpolated profiles and the algorithm of the equiangular sampling theorem, which applies without change because the rings coincide with its grid. We identify the amplification constant that governs numerical error, show that it replaces the condition number used previously for the placement of rings, propose a placement that minimizes it, and give an error propagation model that explains the growth of error with the band-limit. A multi-pass refinement converges in two passes to the rounding floor of the samples. We also describe a stable log-domain evaluation of the sampling functions, a rescaled Legendre recurrence, and a forbidden-region skipping rule that halves the cost of the elimination. Numerical experiments up to $L=2048$ characterize the accuracy, measured by the maximum and mean coefficient errors and the signal-to-noise ratio, the stability and the computation time.

0.35

Certified Spherical MUSIC for 3D Localization under Adversarial Subspace Perturbations

cs.IT math.CA ·2026-09-03 ·Albert Fannjiang, Chuong Nguyen
theory similarity 0.60
Abstract · Corrected abstract metadata formatting

We study an oracle subspace-perturbation model for 3D localization. The procedure is given an $s$-dimensional subspace $\widetilde{\mathcal U}$ and a deterministic error bound \[ \varepsilon_{\mathrm{sub}} = \left\|P_{\widetilde{\mathcal U}}-P_{\mathcal U}\right\|_2, \] where $\mathcal{U}$ is an $s$-dimensional subspace of far-field patterns with wavenumber $κ$, and $P_{\mathcal{V}}$ denotes orthogonal projection onto a subspace $\mathcal{V}$. Under explicit separation and conditioning hypotheses for arbitrary point clouds, we prove that the perturbed spherical MUSIC objective \[ \widetilde{q}({\mathbf z}) = 1-\left\|P_{\widetilde{\mathcal{U}}}\varphi_{\mathbf z}\right\|_2^2 \] has a unique strongly convex well in every ball $B_{γ/κ}(x_j)$ and a uniform value gap outside the union of the certified wells. A fixed-step gradient map with $h\asympκ^{-2}$ leaves each well invariant and converges linearly to its unique minimizer. Consequently, thresholding on an $O(κ^{-1})$-mesh, followed by gradient descent and duplicate removal, recovers all relevant minima with localization bound \[ \mathfrak{R}(\varepsilon_{\mathrm{sub}}) \lesssim \frac{\varepsilon_{\mathrm{sub}}}κ. \] The arbitrary-cloud frame analysis yields the sufficient condition \[ κδ_X\gtrsim s^{2/3} \] through an absolute coherence row sum and Gershgorin's theorem. We construct lower-frame counterexamples below the $s^{1/6}$ scale, upper-frame counterexamples below the $s^{1/3}$ scale, and examples showing that $2/3$ is optimal for the absolute-row-sum argument. Finally, for parameter classes containing a uniformly admissible one-point displacement path, we prove \[ \mathfrak{R}(\varepsilon_{\mathrm{sub}}) \sim \frac{\varepsilon_{\mathrm{sub}}}κ. \]

0.43

Finite-Modal Realization and Operator-Norm Convergence of a Source-to-Observation Electromagnetic Scattering Green Operator

cs.IT math-ph ·2026-09-08 ·Zhukang Wang, Da Li, Ruifeng Li, Jinyan Ma, Jiarun Hu +5 more
similarity 0.57
Abstract · 31 pages, 12 figures; supplementary material included

Source-to-observation operators provide reusable environment-level descriptions for multi-query electromagnetic (EM) prediction and communication-mode analysis. However, in practical multiple-scattering models, these operators are represented with finitely many angular modes, and agreement for selected excitations or between successive truncation orders does not establish uniform accuracy of the full map or reliability of its singular channels. To close this gap, we formulate the environment-induced response as a scattering Green operator on fixed continuous source and observation spaces and derive an exact trace-space factorization that reconstructs the Maxwell scattered field. For fixed, pairwise-disjoint enclosing trace spheres and a well-posed collective problem, nested vector spherical wave function (VSWF) realizations converge in operator norm. A structural bound separates external modal tails from collective-resolvent sensitivity, and operator-norm convergence guarantees uniform convergence of the singular values. We further construct a finite metric core that preserves the nonzero singular values of each finite-order operator and reconstructs matched orthonormal source--field channels without introducing external-support discretization degrees of freedom (DoF) into the spectral problem. Full-wave benchmarks verify the finite-order implementation. A controlled near-resonant two-sphere study shows that adjacent-order agreement can precede resolution of the dominant high-order collective direction. It further shows that only part of the internal amplification appears in externally accessible gains and that resonance promotes a distinct high-order channel pair above an otherwise preserved low-order family. The resulting framework provides a convergent, metric-consistent finite-modal representation of multiple-scattering source-to-observation operators and their accessible channels.

0.28

Identifiable but Hard to Estimate: Rotation in Equally Spaced Overcomplete ICA

cs.LG cs.ITstat.ML ·2026-11-09 ·Wenjun Xiao, Yinghao Fang, Hanxin Chen, Sihan Jia, Vince D Calhoun +1 more
similarity 0.53
Abstract

How many observations are needed to estimate a common rotation in two-dimensional overcomplete independent component analysis? We study equally spaced mixing columns with known source count, common source law, and column norm. For a fixed non-Gaussian fourth-order Gram-Charlier source law, the rotation is identifiable modulo the column spacing. Yet the sample size for fixed relative angular accuracy grows exponentially with the source count. We characterize this sample size, up to absolute constants, by the reciprocal of the squared Hellinger distance between two rotations separated by half the column spacing. An explicit radially weighted phase estimator attains this scale uniformly over the rotation family, using the observation radius to prevent cancellation in the mean of an angular harmonic. We also determine the exact exponential decay rate of single-observation total variation for the same pair. This gives bounds on the sample size exponent; its exact value remains open. Finally, a noisy binary-source example shows how an exact zero line of the observed characteristic function can have an exponentially small normal derivative.

0.23

Algorithmic threshold for high-dimensional projection pursuit I: general theory

cs.CC math.PRcond-mat.dis-nnmath-ph ·2026-08-29 ·Brice Huang, Mark Sellke, Nike Sun
highly cited similarity 0.53
Abstract · 295 pages. All ideas in this paper are human-generated, and all the writing was done by the human authors. AI was used in the writing of thi…

We study a null model of high-dimensional projection pursuit: we are given $M$ points sampled i.i.d. from a standard gaussian in $N$ dimensions, where $M,N\to\infty$ with $M/N\toα\in(0,\infty)$. Our goal is to characterize the possible empirical distributions of these points' projections along a data-dependent direction $x$, which ranges over either the sphere $S_N=\sqrt{N}\mathbb{S}^{N-1}$ or cube $Σ_N=\{-1,+1\}^N$. We consider this problem in an algorithmic setting, where $x$ must be the output of an algorithm with dimension-free Lipschitz dependence on the input; this class of algorithms includes general gradient-based methods such as Langevin dynamics and approximate message passing (AMP). Our main result exactly characterizes the set of empirical distributions attainable by this class in terms of a one-dimensional stochastic control problem. As a consequence of our main result, we obtain exact algorithmic thresholds for optimizing the Hamiltonian of a spherical or Ising perceptron model with general bounded continuous activation. For the spherical problem, independent work of Montanari and Zhou (2024) characterized the empirical distributions attainable by a related two-stage AMP algorithm, also in terms of stochastic control. Our proof of hardness builds on the branching overlap gap property introduced in earlier work by the first two authors. Our main innovation is to develop stochastic control theory within the branching OGP framework, significantly expanding the settings in which it locates an exact algorithmic threshold. Notably, our methods apply even though the non-algorithmic problem of characterizing all feasible projections remains a major outstanding challenge. For the matching algorithmic result, we construct a new incremental AMP algorithm that acts on a Brownian-bridge revelation of the gaussian disorder and simulates the same family of controlled SDEs.

0.59

Optimal random quantisers for spherically symmetric distributions

cs.LG math.STstat.ML ·2026-10-08 ·Luc Pronzato, Anatoly Zhigljavsky
theory similarity 0.52
Abstract

Zador's celebrated theorem is a cornerstone of optimal quantisation: it establishes both the weak limit of the empirical distribution of an optimal $n$-point quantiser in $R^d$ and the decay rate of the associated $L_s$-mean quantisation error. In large dimension, however, observing this asymptotic behaviour requires an astronomically large sample size. We prove that, for spherically symmetric target distributions, optimisation over all spherically symmetric distributions is a convex problem and derive an equivalence theorem that both characterises global optimality and yields a constructive algorithm. We show that, for moderate $n$, random quantisers uniformly distributed on a sphere of suitably chosen radius $R$ perform exceptionally well and, over a broad range of values of $n$, are numerically certified to be optimal among all random quantisers. Their expected distortion has an explicit integral representation that can be evaluated to arbitrary precision, and we prove concentration across random quantisers: the distortion variance tends to zero as $n\to\infty$ for fixed $d$. For $s=2$, both the optimal radius and the associated minimum expected distortion admit exact expressions. For general $s$, the optimal radius can be determined efficiently, and extreme-value theory provides useful approximations when $n$ grows with $d$. Depending on this growth rate, $R$ either converges to zero or approaches a positive limit that is independent of $s$.

0.57

A Mathematical Theory of Near-Field Super-Resolution

cs.IT math.NT ·2026-09-25 ·Sajad Daei, Gabor Fodor, Mikael Skoglund
similarity 0.52
Abstract

Finite-aperture near-field sensing leads to a super-resolution geometry fundamentally different from the translation-invariant Fourier setting. In the Fresnel regime, wavefront curvature introduces a range-dependent quadratic aperture phase, so distinguishability is governed by incomplete quadratic exponential sums of the form \( \sum_{n=0}^{N_r-1} a_n e^{i(ω_1 n+ω_2 n^2)} \), rather than by angular separation alone. We develop a deterministic recovery theory for sparse measures with ranges on a finite grid and continuous angles, and introduce a support-uniform quadratic-phase aperture criterion replacing classical minimum separation. Under this criterion, total-variation minimization exactly recovers every sparse measure in the admissible support class, uniformly over all nonzero complex amplitudes. The proof develops nonasymptotic support-uniform bounds for finite quadratic sums and combines them with a gauged Hermite dual certificate controlling interpolation, local curvature, and off-support leakage. We further construct a finite-harmonic Bessel-Vandermonde lift with explicit truncation error. In the far-field limit, the quadratic phase disappears and the theory reduces to Fourier-type angular super-resolution.

0.27

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics

cs.LG cs.DSmath.PRmath.ST ·2026-10-28 ·Aniket Das, Tselil Schramm
similarity 0.51
Abstract · Companion paper to arXiv:2610.16705 (Part I). 71 pages, 1 figure

We consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in $\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. Continuing the program initiated in Part I [arXiv:2610.16705], we show that spherical Langevin dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Together with Part I, our results demonstrate that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.

0.14