CS Paper Radar

Spectra of Multivariate Vandermonde Matrices and Min-max Error Bounds for the High-dimensional Super-resolution Problem

Nuha Diab, Dmitry Batenkov

cs.IT math.SPmath.NA ·submitted 2026-10-17 12:43 UTC · v1
theory

Abstract

We study multivariate rectangular Vandermonde matrices $U_N$ whose rows are indexed by the grid $G_N=\{-N,\ldots,N\}^d, $ and whose columns correspond to irregularly spaced points on the unit $d$-dimensional torus. Motivated by the problem of super-resolution (recovery of spike trains from low frequency noisy measurements), we consider configurations in which the points form several clusters, with points within each cluster separated by at most $h$ and distinct clusters are well-separated. We show that the column subspaces associated with different clusters are nearly orthogonal, i.e. for $N \rightarrow \infty, Nh \ll 1$, the minimal principal angle between any such pair is at least $ {π\over 2} - \frac{C_1}{N} - C_2Nh - \frac{C_3}{\sqrt{N}}, $ for some constants $C_1,C_2,C_3$ independent of $N$ and $h$. This near-orthogonality enables the spectral analysis of such $U_N$ to be reduced to the analysis of each individual cluster. As a consequence, we derive sharp scaling for all singular values of $U_N$, revealing how the geometry of clustered points controls the conditioning of the high-dimensional super-resolution problems. Then we establish min-max error bounds for the recovery of clustered point sources, requiring only an upper bound on the largest cluster size and no knowledge of the geometry within the clusters. These bounds coincide with the optimal rates known in the one-dimensional setting. Furthermore, when the clustered points are in generic position (i.e. do not lie on a low-dimensional algebraic variety) our results indicate that super-resolution in high dimensions is more stable than in one dimension.

Comment
38 pages, 10 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Hankel/Toeplitz matrix for array signal processing

eess.SP cs.IT ·2026-09-03 ·Wenchong Huang, Kunpeng Li, Ping Liu
theory similarity 0.69
Abstract · 48 pages, 13 figures

In this paper, we introduce generalized Hankel/Toeplitz matrices (GHM/GTM) and the associated generalized Vandermonde decomposition for nonuniform array signal processing and multi-dimensional super-resolution. The proposed framework was discovered from the study of resolution limit theory and extends the classical Hankel/Toeplitz structure by allowing substantially more flexible sampling geometries while preserving the underlying low-rank Vandermonde factorization. Through devising an optimal algorithm based on this GHM framework, we derive the state-of-the-art upper bound estimate for the computational resolution limit (CRL) of source-number detection in general $d$-dimensional super-resolution problems. For segmented sampling sets, whose geometry is closely related to sparse and distributed arrays, we establish deterministic lower bounds for the minimum singular values of the associated generalized Vandermonde matrices and derive corresponding stability and number-detection guarantees for multi-clump source configurations. To address the computational bottleneck of conventional multi-level Hankel constructions in high dimensions, we further introduce randomized GHM constructions whose matrix dimensions scale with the effective degrees of freedom rather than with the full tensor-product grid, together with deterministic recovery guarantees conditional on the realized Vandermonde factors. We also extend the framework to source localization by developing GHM-based MUSIC algorithms for nonuniform measurements, with stability characterized through the conditioning of the generalized Vandermonde factors. Numerical experiments on synthetic data demonstrate that the proposed GHM-based methods achieve competitive resolution and recovery accuracy while substantially reducing matrix size and computational cost, especially in high-dimensional settings.

0.28

How many sorted projections determine n points in k dimensions?

cs.DM math.COcs.ITcs.LG ·2026-11-04 ·Christopher Gorham Lester, Raymond Hau Sørensen
theory similarity 0.59
Abstract · 28 pages, 5 figures

Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points? Two simple bounds are known in every dimension: more than $(k-1)\log_2 n$ directions are always needed, and $(k-1)n+1$ directions in general position always suffice. In the plane much more is known: Matousek, Privetivy and Skovron showed that almost every choice of $O(\log n \log\log n)$ directions suffices. Whether anything similar holds in higher dimensions was left open by Dym, Wellershoff, Tsoukanis, Levy and Balan. We observe that two lemmas of Hair and Sahai, proved for list recovery of random linear codes, answer that question, and by tightening their argument we show that in every dimension almost every choice of $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ directions suffices. For $k\le 10$ this beats the linear bound once $n$ is larger than about 100: for example, 144 directions suffice for multisets of 1000 points in the plane, and an exact computation lowers this to 133. Letting some of the random blocks in their argument fail removes a factor $\log k$: almost every choice of $O(k\log n\log\log n)$ directions suffices, uniformly in $k$ and $n$. We also show that $2k-1$ directions never determine three points, so that the logarithmic lower bound is not tight; that every $m$ directions in the plane fail on some pair of multisets of size $O(1.78^m)$, improving the bound $O(1.80^m)$ of Matousek, Privetivy and Skovron; and that for each $k$, $m$ and $n$, either almost every choice of $m$ directions works or almost none does.

0.50

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.59
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18

Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy

cs.LG ·2026-08-14 ·Johanna Hillebrand, Jan Höckendorff, Jürgen Kusche, Kelin Luo, Heiko Röglin +3 more
theory similarity 0.59
Abstract

Constrained optimization extends classical optimization by integrating side information, making it widely applicable across scientific and engineering domains. Consider a setting where we measure variables at different physical locations. When grouping these measurements, we often want clusters that are both internally similar and physically coherent. Thus, we have a constrained clustering problem where the constraint models coherence. Motivated by an application in geodesy, where contiguous regions of the sea surface must be identified for principal component analysis, we introduce the Connected Subspace Clustering problem: given high-dimensional points and a connectivity graph, partition them into $k$ connected clusters, minimizing their total squared distance to the clusters' best-fit $m'$-dimensional affine subspaces. We prove that, even for $m' = 0$ and a grid graph with holes, the problem is NP-hard to approximate within $Ω(n^{1/2-\varepsilon})$ for every $\varepsilon>0$, where $n$ is the number of measurements. We then introduce an efficient Lloyd-style heuristic that alternates subspace fitting with an iterative merging procedure to enforce connectivity. Our method returns exactly $k$ connected regions by construction, whereas unconstrained methods leave up to $1{,}966$ disconnected fragments at higher cost. In a study of 160 configurations on global sea level time series, our merging-based repair is the strongest of four strategies in $73.75\%$ of cases, and consistently outperforms competitors such as (connected) Ward's method across all tested cluster counts. The resulting regions isolate signals aligning with climate indices such as the El Nino-Southern Oscillation and Indian Ocean Dipole. Although developed for geodesy, the approach applies to other spatially embedded multivariate time series, such as climate fields, remote sensing, neuroimaging, and sensor networks.

0.04

Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS

cs.LG math.OC ·2026-11-11 ·Alberto Del Pia, Dekun Zhou
hot direction similarity 0.57
Abstract

In sparse principal component analysis (SPCA) with several components, each must be sparse and all must be pairwise orthogonal. When the supports of the components overlap, these two requirements interact. For a covariance matrix of fixed rank, polynomial-time algorithms with optimality or approximation guarantees are known for one component, and for several components with disjoint supports or with a common support. We study the general model, with individual sparsity constants and arbitrary support overlaps. We are given a rational $n\times r$ matrix $R$ and $d$ sparsity constants $s_i \le n$, and the goal is to find an $n\times d$ matrix $X$ with orthonormal columns that maximizes $\|R^\top X\|_F^2$, such that column $i$ has at most $s_i$ non-zero entries. Here $RR^\top$ plays the role of the covariance matrix and has rank at most $r$. We show that SPCA is NP-hard even when $r = d = 2$, but admits a fully polynomial-time approximation scheme (FPTAS) when $r$ and $d$ are fixed. The returned solution has exactly orthonormal columns, and its entries are real algebraic numbers in an exact representation. For fixed $ε$, the number of steps of the algorithm is linear in $n$ up to a polylogarithmic factor. Our approach reduces SPCA to a sparse version of the orthogonal Procrustes problem, that is, to maximizing a linear function over the feasible region of SPCA. We show that this problem is NP-hard even for $d = 2$, and we give an FPTAS for it when $d$ is fixed. This FPTAS combines approximate dynamic programming over the rows, two-column updates that restore exact orthogonality, and an exact computation of the few variables for which these updates are not available.

0.33

Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

cs.CG math.MG ·2026-10-16 ·Nikita Muravya, Aleksandr Bespalov, Anna Vozianova
theory similarity 0.56
Abstract

A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4/5<\varepsilon<1$, dimension $O((N/k)\log N+kρ_k^4\log N/(\varepsilon-4/5)^2)$ suffices, where $ρ_k$ is the largest ratio, over all points, between the distance to the $k$th closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in $[1,Φ]$, where $Φ\ge5$ is fixed, the worst-case dimension is $Θ(N)$ for $0<\varepsilon<4/5$, lies between $Ω(\sqrt N)$ and $O(\sqrt N\log N)$ for $4/5<\varepsilon<12/13$, and is $Θ(\log N)$ for $\varepsilon>(Φ^2-1)/(Φ^2+1)$. For $Φ>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $Ω(\sqrt N)$ lower bound for $4/5<\varepsilon<12/13$, while Hadamard matrices give explicit linear lower bounds for $\varepsilon<4/5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\varepsilon<1$. Finally, for every fixed $0<\varepsilon<3/5$, we show that the quadratic dependence on the parameter $C$ in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

0.22

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

cs.DS math.FA ·2026-09-16 ·Tarun Kathuria
similarity 0.56
Abstract · The author explicitly reserve all rights in this work. No permission is granted for the reproduction, storage, or use of this document for t…

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

0.56

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.55
Abstract · 13 pages; comments welcome!

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

0.10