CS Paper Radar

Multichannel Sampling and Reconstruction in Multidimensional Shift-Invariant Spaces

Riya Ghosh, Satish Mulleti, Chandra Sekhar Seelamantula

eess.SP ·submitted 2026-10-26 18:47 UTC · v1
unusual

Abstract

We develop a multichannel sampling and reconstruction framework for multidimensional principal shift-invariant spaces based on a finite-dimensional polyphase representation. Periodic nonuniform shifts and derivative measurements are modeled as analysis channels, leading to a frequency-domain linear system relating the measurements to the polyphase components of the underlying coefficient sequence. Stable recovery is characterized through uniform singular-value bounds on the associated polyphase matrix, and explicit synthesis kernels are obtained from its Moore Penrose left inverse. The formulation applies to both separable and genuinely non-separable generators and includes several classical one dimensional sampling formulas as special cases. For irregular derivative measurements, where the periodic polyphase structure is no longer directly available, we develop an iterative reconstruction method based on local bivariate Hermite interpolation followed by orthogonal projection onto the shift-invariant space. A sufficient contraction condition is derived to guarantee geometric convergence of the iteration. Numerical experiments demonstrate the reconstruction performance for separable and non-separable generators and illustrate robustness to additive measurement noise and sampling-location perturbations.

Closest papers

Nearest neighbours by meaning across the whole index.

Robust blind unmixing: A geometric approach to overcoming basis variation

cs.LG cs.AI ·2026-10-02 ·Dumitru Mirauta, Vladimir V. Gusev, Michael W. Gaultois, Matthew J. Rosseinsky, Yannis Goulermas
unusual similarity 0.52
Abstract · 40 pages, 16 figures, 5 tables

Signal separation problems are common in science. A prominent example of this occurs during the use of diffraction or spectroscopy to identify the individual components of a mixture by measuring it. In the simplest case, the measured signal is a linear combination of basis patterns corresponding to the constituent parts. The unmixing problem is to infer all or some of these basis patterns and abundances of components from measurements of distinct mixtures. One of the core challenges of this task is the variation of the basis from mixture to mixture due to noise and the exact physics of the measurement process. This is usually addressed with tailored model-based and parametric methods that are then limited in use to specific application domains by the nature of the assumptions made. We propose a novel geometric approach to unmixing problems which views the generation of data during measurement through a metric space lens, thereby shifting the focus from parametrised models to a general relationship between basis transformations and the corresponding geometry. We take advantage of the optimal transport distances to capture commonly occurring basis variations, and use minimisation of in-class variance of candidate solutions to drive the optimisation. We pay special attention to the one-dimensional case due to its practical importance and availability of efficient distance and transport map routines. The effectiveness of our approach is demonstrated on a range of unmixing tasks using random Gaussian mixture models, simulated powder X-ray diffraction, and laboratory hyperspectral imaging datasets.

0.28

Impulse Response Estimation via Laguerre-Fourier Expansion

eess.SP math.CVmath.DS ·2026-08-14 ·Tamás Dózsa, Art J. R. Pelling, Matthias Voigt
similarity 0.51
Abstract

The empirical transfer function estimate (ETFE) is a widely used method for system identification of linear time-invariant (LTI) systems in engineering disciplines such as acoustics, audio engineering, seismography, and tomography. However, ETFE suffers from numerical limitations when the excitation signal is band-limited or vanishes at certain frequencies, which is a common physical constraint of the excitation in practice. In such cases, division in the frequency domain becomes heavily ill-conditioned, and small measurement disturbances or numerical inaccuracies can degrade the solution. This paper presents L-ETFE, a generalization of ETFE based on Laguerre-Fourier expansions that addresses these limitations. After a suitable transformation, the method can yield a well-conditioned circulant problem even when the original ETFE system is ill-conditioned. Solving this problem via classical ETFE yields the discrete Laguerre-Fourier coefficients of the system's transfer function. The desired impulse response (IR) of the system-to-be-identified can then be recovered by a subsequent transformation pipeline. We derive novel and efficient algorithms for performing these transformations and analyse the conditioning of the transformed problem, explicitly characterizing its dependence on the input and a parameter used in the Laguerre-Fourier expansion. We evaluate the method on two simulated discrete-time LTI systems of varying complexity. The experiments demonstrate accurate IR recovery for spectral-zero and band-limited excitation, where standard ETFE fails.

0.04

Coded Hankel Polynomial Chaos: Spectral Identification of Dominant Polynomial-Chaos Modes

cs.LG stat.ML ·2026-08-17 ·Zhiliang Deng, Xiaomei Yang
unusual similarity 0.50
Abstract

Identification of dominant polynomial-chaos modes is usually formulated as a sparse-regression problem on a sampled multivariate polynomial dictionary. We develop coded Hankel polynomial chaos (CH-PC), a complementary spectral formulation for dominant-mode identification. A finite generating transform converts PCE coefficients into a coefficient-generating polynomial, and evaluation along a geometric phase orbit produces a finite exponential sum. Its model order and spectral nodes are encoded by low-rank Hankel matrices, while coordinate phase shifts attach root-of-unity labels from which the full polynomial multi-indices are recovered. Coordinate-shifted probes are combined as common-node snapshots, and independent phase encodings provide redundant representations when a single spectral encoding is poorly conditioned. For finite observations, population, finite-data, and observed probes are kept distinct: sampling or quadrature error and observation error enter as separate Hankel perturbations, which are then connected to spectral stability, discrete decoding, and phase voting. For tensor-product candidate sets, the generating kernel factorizes into one-dimensional sums and can be evaluated without assembling the full multivariate PCE design matrix. Numerical experiments on sparse Legendre benchmarks and a stochastic Darcy problem illustrate exact recovery, noise stabilization, unknown-order identification by phase persistence, and dominant-mode recovery for a PDE-generated quantity of interest.

0.27

Basis Selection For Analog Coded Computing Under Differential Privacy Constraints

cs.IT ·2026-10-19 ·Aaditya Sharma, Rimpi Borah, J. Harshan
similarity 0.49
Abstract

In analog coded computing, encoding basis functions are typically chosen to guarantee exact reconstruction and improve numerical stability. However, the same basis functions also determine the statistical geometry of the observations available to colluding workers, and hence directly influence the privacy of the underlying data. This suggests that basis selection should not be viewed solely as a reconstruction or numerical conditioning problem, but rather as a joint privacy and accuracy co-design problem. Motivated by this observation, we revisit Analog Lagrange Coded Computing (ALCC) and show that the full orthogonality constraints imposed by the conventional Lagrange basis are stronger than what is required for exact recovery. We retain only the interpolation constraints necessary for the data bearing basis functions and require the noise bearing basis functions merely to vanish at the data recovery points. This yields a parameterized family of generalized polynomial encoding bases that preserves exact reconstruction while introducing additional design degrees of freedom. We then derive a basis-dependent characterization of differential privacy for colluding workers and formulate a privacy-calibrated numerical optimization problem that jointly selects the data and noise basis functions to reduce reconstruction error while satisfying a prescribed \((ε,δ)\)-DP requirement. The resulting framework therefore treats the encoding basis itself as a privacy-design variable, rather than selecting a fixed closed-form basis a priori. The same design philosophy is also compatible with alternative privacy metrics such as mutual-information leakage. Numerical results show that, at the same privacy level, optimized basis functions substantially reduce floating-point reconstruction error relative to conventional ALCC.

0.29

Efficient Non-Uniform Quantum Hermite Transform through Adaptive Sampling

cs.DC quant-phcs.ET ·2026-09-17 ·Nitay Mayo, Aryeh Lev Zabokritskiy
similarity 0.49
Abstract · 30 pages, including supplementary material. Minor corrections to notation and exposition; improved figure legibility and ancillary documenta…

On the span of the first $N$ oscillator modes, Gauss--Hermite quadrature gives an exact change of basis between mode coefficients and $N$ weighted position space samples. We implement this transform with $O(N\operatorname{polylog}(N,1/\varepsilon))$ logical gates and polylogarithmic quantum width. The operator-error bound $\varepsilon$ holds on arbitrary superpositions and includes all auxiliary registers. The construction uses signed averages on adaptive windows to convert uniform-grid samples into weighted Hermite-root samples. Their varying widths control the amplification cost, giving the near-linear bound.

0.31

Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants

cs.SC ·2026-09-17 ·Vincent Neiger, Mohab Safey El Din, Kevin Tran
similarity 0.48
Abstract

When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the half-gcd algorithm. These problems have various applications in algebraic computations and bear strong connections to linearly recurrent sequences, structured matrices, and continued fractions. This article first gives a collection of algorithmic reductions, showing that rational reconstruction and XGCD can be solved via the computation of bases of relations modulo a freely-chosen polynomial $M(x)$. In particular, one recovers the folklore idea that bases of Padé approximants (i.e., $M(x) = x^d$) can be used to perform quasi-linear rational reconstruction or XGCD, extending to fast algorithms the well-known link between the Berlekamp-Massey algorithm and the extended Euclidean algorithm. One highlight of these reductions is that, instead of approximants, one may rely on Cauchy interpolants (i.e., $M(x)$ vanishes at chosen points). In a second part, this article describes divide-and-conquer algorithms for approximants and interpolants along with complexity analyses showing an explicit leading constant in front of the dominant term. For interpolants, the best leading constant is obtained through a variant that stores polynomials represented by evaluations, and exploits fast extrapolation in order to avoid repeated conversions to the monomial basis; this requires special points, in geometric or arithmetic progression, or FFT points when the base field allows them. Combining the analyses with the reductions leads to the best complexity bounds we are aware of for rational reconstruction and XGCD. Perhaps surprisingly, even Padé approximants or Berlekamp-Massey-like computations, which intrinsically involve $M(x) = x^d$, are accelerated by reducing them to Cauchy interpolation at well-chosen points.

0.26

Dynamics-Aware Sampling and Recovery for Tensor-Valued Dynamical Systems

cs.IT math.NA ·2026-10-25 ·Seok-Young Chung, Longxiu Huang, Yisen Wang
theory similarity 0.48
Abstract · 55 pages, 9 figures

We study sampling and recovery for tensor-valued dynamical systems evolving under the t-product, using partial spatial observations over time. Although the t-product Fourier transform yields slicewise matrix dynamics, recovery does not generally decouple across slices. Eigenvalues shared across Fourier-domain frontal slices couple the corresponding eigenspaces into aggregated spectral blocks, which determine the tensor-specific recovery geometry and space--time tradeoff. We establish deterministic identifiability conditions for the initial tensor state. In the diagonalizable case, these are frame conditions on the aggregated blocks. We extend them to non-diagonalizable systems through generalized eigenspaces and Jordan structure. A temporal--spectral factorization of the finite-horizon stacked recovery system underlying Tensor Dynamical Sampling (DS) yields a decoupled two-stage formulation once the temporal threshold is reached. Under independent spatial subsampling, we prove high-probability recovery guarantees using empirical Gram matrices on the aggregated blocks. The bounds depend on aggregated multiplicities, incoherence, and population conditioning. Stability estimates separate the spatial frame factor from the temporal Vandermonde factor and show that increasing temporal depth may worsen numerical conditioning even after identifiability is ensured. We implement Tensor DS and evaluate it on synthetic and real data. Phase transitions track the predicted blockwise sampling thresholds, and stability experiments illustrate Vandermonde conditioning. Experiments on sea surface temperature and turbulence velocity data show that a learned t-product system operator generally yields more accurate and structurally faithful reconstructions than vectorized low-rank, Tucker-type, graph-regularized, graph-spectral, and vectorized dynamical sampling baselines.

0.28

Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity

eess.SP math.OC ·2026-10-13 ·Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang
similarity 0.48
Abstract

This paper studies the spectral compressed sensing problem, which aims to recover an $r$-spectrally-sparse signal of length $N$ from linear compressive measurements. We reformulate the problem as the recovery of a low-rank Hankel matrix. Motivated by this formulation, we propose a Lifted Restricted Isometry Property (LRIP) for the measurement matrix and show that Gaussian measurement matrices satisfy LRIP under certain conditions. Unlike classical RIP, LRIP imposes a rank constraint in the lifted matrix domain while taking measurements in the signal domain through the adjoint Hankel operator. To solve the resulting nonconvex problem efficiently, we introduce a Fast Iterative Hard Thresholding (FIHT) algorithm. Based on LRIP, we show that FIHT converges linearly to the true signal with high probability using $\mathcal{O}(r \ln r \ln^2 N)$ scaled Gaussian measurements, which is near-optimal up to log factors and improves the state-of-the-art order of $r^2$ for nonconvex Hankel methods. Extensive numerical results demonstrate the superiority of FIHT as compared to state-of-the-art convex methods in terms of phase transitions, computational time, and robustness to noise.

0.40