CS Paper Radar

Sampling of Signals on Multigraphs: From Removable and Uniqueness sets to Spectral Proxies

Alejandro Parada-Mayorga

eess.SP cs.LG ·submitted 2026-10-19 01:36 UTC · v1
theory

Abstract

In this paper, we study the sampling of bandlimited signals on multigraphs, where several graphs with different shift operators are defined on the same set of nodes. Since the shift operators do not commute in general, they admit only a joint block diagonalization, and the frequencies of the multigraph signal model are matrices rather than scalars. Relying on a formal algebraic convolutional signal model, we introduce a notion of frequency and bandwidth for multigraph signals that does not depend on any individual layer, and we extend the notions of removable and uniqueness sets to multigraphs. We prove that the optimality of a sampling set is determined exclusively by the common Fourier basis and its invariant subspaces, and not by any individual layer, although the individual layers provide computable sufficient conditions that certify a sampling set as a uniqueness set. Since identifying which layers provide reliable certificates requires spectral information, we propose an aggregate operator that pools the information of all the layers, is computable directly from the shift operators, and certifies uniqueness without any assumption on the individual layers. This operator leads to a greedy sampling algorithm that does not require computing the joint block diagonalization. Numerical experiments on multigraphs whose layers order the frequencies inconsistently show that the proposed algorithm selects better-conditioned sampling sets and attains lower reconstruction errors than single-layer methods.

Closest papers

Nearest neighbours by meaning across the whole index.

Graph Spectral Series and Its Signatures

eess.SP ·2026-10-23 ·Feng Ji, Jingyang Dai, Apostolos Evangelidis, Xingchao Jian, Marco Rauscher +1 more
similarity 0.63
Abstract

Bandlimitedness is a central modeling assumption in graph signal processing (GSP), but many graph signals exhibit substantial energy throughout the graph-frequency domain. We introduce a new framework for analyzing such non-bandlimited signals by treating their graph Fourier spectra as ordered sequences and representing them with path signatures. Specifically, motivated by the observation that non-bandlimited graph spectra often display rough, time-series like behavior, we introduce the notion of graph spectral series and develop a signature-based representation that captures global spectral structure without frequency truncation. We establish conditions under which the proposed representation is continuous and characterize its information-preserving properties. We further provide an asymptotic interpretation of graph spectral series for sequences of expanding graphs. Experiments on real-world trend-prediction and change-detection tasks show that signature features can improve performance over representations based directly on the original graph signals. The proposed approach provides a novel principled signature-based tool for analyzing non-bandlimited graph signals.

0.31

Fundamental Limits of Transferability and Equivariance in Algebraic Signal Models I: Finite Dimensions

eess.SP cs.LG ·2026-09-28 ·Alejandro Parada-Mayorga
similarity 0.58
Abstract

We study the fundamental limits of transferability in algebraic signal processing through homomorphisms between algebraic signal models. Homomorphisms are linear maps between the signal spaces of two models that commute with filtering, so filtering a signal and transferring it across domains can be done in either order. The existence of such maps is governed entirely by coincidences among the filtered eigenvalues of the two models' shift operators, but existence alone is insufficient: the space of homomorphisms always contains trivial elements that destroy all information. We introduce the spectral transfer efficiency $η(θ)\in[0,1]$ to quantify information-preserving quality, prove that every homomorphism decomposes into unconstrained blocks over coincidence classes, derive the dimension of the homomorphism space, and characterize exactly when lossless transfer is achievable. Beyond normal shift operators, we quantify a departure-from-normality penalty and show how filter derivatives can repair spectral defectiveness. The theory yields concrete consequences in three settings: for sampling, eigenvalue interlacing converts transferability under subsampling into an explicit filter design constraint; for compressed sensing, $η(θ)$ controls the restricted isometry constant and the coherence of the resulting measurements, and recovery decouples across coincidence classes; and for machine learning, spectral aliasing emerges as the controlled symmetry breaking that makes transfer between mismatched domains possible at all.

0.25

Graph neural networks for sampling-invariant embeddings of organized signal sets

cs.LG cs.AIcs.NEeess.SP ·2026-09-28 ·Martin Bauw, Santiago Velasco-Forero, Jesus Angulo
unusual similarity 0.57
Abstract

Sensor networks and radars can deliver signals as organized sets, e.g. ordered signals, signals describing range cells within a grid or signals perceived as graph nodes. Within such sets, individual signals may be characterized by distinct sampling parameters. This paper investigates organized signal sets neural network encoders. In the context of this work, the purpose of such encoders is to project heterogeneously sampled signal sets into an arbitrary fixed-size vectors space. This new representation space is designed so that signal sets can be processed as vectors rid of sampling differences to allow for arbitrary topology-aware processing with no signal processing constraints. Within this representation space designed to reduce the influence of heterogeneous sampling parameters, the relevance of signal sets representations is evaluated by considering signal sets discrimination potential with a focus on waveforms separation. The encoding and embeddings discrimination experiments conducted rely exclusively on synthetic complex-valued radiofrequency signals.

0.24

Planted Cliques and Quantum Symmetry-Adapted Measurements

cs.CC quant-ph ·2026-09-30 ·Vojtech Havlicek, Jordan Docter, Subhash Khot
theory similarity 0.57
Abstract · 21 pages, no figures. Revised it to improve clarity and readability. VH takes responsibility for the previous submission prepared under a ti…

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

0.32

Memorization Capacity of Invariant Convolutional Neural Nets

cs.LG stat.MLmath.ST ·2026-10-28 ·Sjoerd Dirksen, Patrick Finke, Paul Geuchen
theory similarity 0.56
Abstract

Neural networks are powerful memorizers which are often able to interpolate their training data even when the labels have been randomized. While there exists an extensive literature on the memorization capacity of fully connected networks, in practice more specific architectures with problem-dependent properties are preferred, such as convolutional networks for image classification. In this paper we consider convolutional networks which are invariant with respect to a given arbitrary finite group of orthogonal transformations, which may include translations, reflections, and/or rotations of images and invariances of higher order tensors. We prove upper bounds on the size of an invariant convolutional neural network with threshold activations that is required to interpolate a given dataset with two classes. Our bounds are formulated in terms of a complexity measure that takes the invariant structure into account and is instance-specific, i.e., it is related to the mutual arrangement of the classes in the given dataset and their geometric properties rather than the number of samples. Our proof is constructive: for given input data, instances of an interpolating network can be computed via a randomized algorithm with high probability. In numerical experiments we investigate the practical effectiveness of this algorithm.

0.30

A Cheeger Inequality for Hypergraphs and Its Applications

cs.DS math.CO ·2026-09-14 ·Raj Kamal, Amitabha Bagchi
similarity 0.56
Abstract

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon-Boppana bound.

0.24

Finite-Sample and Communication-Efficient Networked Information Aggregation

cs.LG cs.AIcs.GT ·2026-11-08 ·Mohammadhossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam
top venue similarity 0.55
Abstract · Accepted at the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Building on SODA 2026 work Kearns et al. (2026), we study learning in directed acyclic graphs in which each agent observes only a subset of the input coordinates and may use the predictions of its parents as additional features. In the finite-sample protocol, the message sent along each edge is the agent's prediction vector on a shared sample, so the communication cost is linear in the sample size $m$. In this paper we study this model under communication constraints. First, we revisit the finite-sample analysis of the full-message protocol. We identify a gap in the finite-sample proof of Kearns et al. (2026) and develop a different argument that establishes a finite-sample population-risk guarantee along paths satisfying deterministic $M$-coverage. Second, we introduce a shared-sketch protocol in which each agent sends a $k$-dimensional linear sketch of its prediction vector instead of the full $m$-dimensional message, where $k\ll m$. We analyze this protocol through a reduction to least squares on the compressed sample together with an oblivious subspace embedding argument. The resulting bound separates statistics from communication: the statistical term is still governed by the original sample size $m$, while the additional error due to compression is controlled by the sketch dimension $k$. For Gaussian sketches, we obtain an explicit high-probability population-risk bound, showing that row subsampling is not the only possible communication-statistics tradeoff for networked information aggregation.

0.42

$hp$-adaptive trees for graph signal approximation

eess.SP math.NA ·2026-09-10 ·Giacomo Elefante, Wolfgang Erb, Michael Multerer
similarity 0.55
Abstract

Tree-encoded partitionings of graphs are fundamental tools for the decomposition and approximation of graph signals. For the efficient approximation of such graph signals, we develop strategies based on $hp$-refinement by combining domain decomposition with an improved local approximation using polynomials of higher degree. In this way, from a given graph partitioning tree, a more efficient subtree is extracted in which the cost of the signal approximation is considerably reduced by still maintaining the same total error. To this end, we interpret the refinement process as a binary knapsack problem to determine an enhanced partitioning tree. We further study an a-posteriori strategy which prunes the partitioning tree by optimizing the polynomial degrees over the subdomains. To make polynomial basis systems accessible for general graphs or high-dimensional data, we propose local embeddings of graphs into low dimensional Euclidean spaces. We underpin the efficiency of our algorithms with extensive numerical tests which carefully assess the impact of the applied refinements and optimization strategies.

0.28