CS Paper Radar

Certified Spherical MUSIC for 3D Localization under Adversarial Subspace Perturbations

Albert Fannjiang, Chuong Nguyen

cs.IT math.CA ·submitted 2026-09-03 01:47 UTC · v2
theory

Abstract

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}}}κ. \]

Comment
Corrected abstract metadata formatting

Closest papers

Nearest neighbours by meaning across the whole index.

Spherical ESPRIT by Paired Small Circles and Infinitesimal Rotations

eess.SP math.CA ·2026-09-26 ·Albert Fannjiang
theory similarity 0.60
Abstract · 40 pages

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.

0.25

Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

cs.CC quant-phmath.AGmath.NT ·2026-08-25 ·Yota Maeda, Hiroshi Yano
theory similarity 0.53
Abstract · 31 pages

We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.

0.28

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

eess.SP math.NA ·2026-11-12 ·Zubair Khalid
theorycode/data similarity 0.52
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

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.52
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

Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation

cs.CG quant-phcs.DS ·2026-10-04 ·Ruizhe Zhang
theory similarity 0.50
Abstract

Estimating the volume of a high-dimensional convex body is a fundamental problem in theoretical computer science. Given a quantum membership oracle for a convex body $K\subset\mathbb{R}^d$, we show that estimating $\mathrm{vol}(K)$ to relative error $\varepsilon$ takes $\widetilde O(d^{5/2}+d^{3/2}/\varepsilon)$ queries. This improves the previous quantum upper bound $\widetilde O(d^3+d^{9/4}/\varepsilon)$ of Chakrabarti et al. (ACM TQC 2023) and Cornelissen--Hamoudi (SODA 2023), and achieves a larger quantum speedup over the currently best classical upper bound $\widetilde O(d^{7/2}+d^3/\varepsilon^2)$ of Jia et al. (JACM 2026). Our quantum algorithm combines two new ingredients: an input-dependent effective spectral-gap analysis of quantum walks based on uniform classical warm-start mixing bounds, and a single quantum estimator for products of normalizer ratios in simulated annealing based on classical bridge sampling. We also prove an $Ω(d)$ quantum query lower bound for constant relative error, improving the previous $Ω(\sqrt d)$ lower bound.

0.23

Improved Algorithms for the Remote Point Problem

cs.CC cs.DS ·2026-09-22 ·Ben Lee Volk
published similarity 0.50
Abstract

The Remote Point Problem (RPP) is an algorithmic problem that asks, given a linear subspace $L \subseteq \mathbb{F}^n$ of dimension $k$, to deterministically find a vector $v \in \mathbb{F}^n$ far in Hamming distance from $L$. This problem was introduced by Alon, Panigrahy and Yekhanin [APY09], motivated in part by the matrix rigidity approach for proving circuit lower bounds. An algorithm is said to achieve remoteness $d$ if it finds a vector $v$ whose Hamming distance from $L$ is at least $d$. We observe that over the rational numbers, the problem admits a deterministic polynomial-time algorithm that achieves optimal remoteness $n-k$. Over finite fields, we obtain a (modest) improvement of a result of Alon, Panigrahy and Yekhanin [APY09], and give an algorithm that achieves remoteness $Ω\left(\frac{n}{\max\{k, \log n\}} \log n\right)$.

0.35

The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration

cs.DS ·2026-09-18 ·Tung Mai, Anup Rao
theory similarity 0.50
Abstract

An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every $0 < δ< 1$, there exists a distribution that gives an OSE with embedding dimension $O((d + \log(1/δ))/\varepsilon^2)$ and column sparsity $s = O(\log(d/δ)/\varepsilon)$, with failure probability at most $δ$. We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.

0.36

SparseStack Is an Optimal Oblivious Subspace Embedding

cs.DS math.NA ·2026-09-02 ·Diar Heidary
theory similarity 0.50
Abstract · The proof was developed with AI systems

We prove that fully independent SparseStack achieves the oblivious subspace embedding parameters conjectured by Nelson and Nguyen (FOCS 2013): $m=O((d+\log(1/δ))/\varepsilon^2)$ rows and $s=O(\log(d/δ)/\varepsilon)$ nonzero entries per column for distortion $\varepsilon$ and failure probability $δ$ on any fixed $d$-dimensional subspace, with explicit constants. The proof turns random-matrix concentration into a problem in finite-dimensional linear algebra. A coupling first reduces the moment estimates to a model with independent finite-valued entries. We represent these variables by multiplication operators, so their matrix moments become exact matrix elements of a deterministic operator on a finite tensor product. The central estimate bounds the contribution of $\ell\ge1$ occupied sites sharing the external factor $\mathbb{R}^d$ by $d+\ell-1$ rather than $d\ell$, yielding additive dependence on the dimension and the moment order. This approach controls both spectral edges without Gaussian comparison. The main theorem has been formally verified in Lean 4.

0.40