We study the problem of sampling k-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the co…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
16 results for “Bandlimiting”
In this work, we introduce the concept of bandlimiting into the theory of machine learning because all physical processes are bandlimited by nature, including real-world machine learning tasks. After the bandlimiting constraint is taken into account, our theoretical analysis has shown that all practical machine learnin…
Band-limited SAC improves learning efficiency and stability in simulated environments.
problem Improving sample efficiency and stability in SAC algorithms.
method Artificially bandlimiting the target critic's spatial resolution using a convolutional filter.
result Bandlimited SAC outperforms classic twin-critic SAC in various Gym environments and is more stable.
GNNs outperform NNs in interpolating bandlimited functions on Euclidean cubes.
problem Interpolating bandlimited functions on Euclidean cubes using GNNs vs. NNs.
method Investigates optimal GNN configurations and weights for function interpolation.
result GNNs require fewer weights and samples to interpolate bandlimited functions compared to NNs.
Bandlimited random neural networks may not approximate all functions perfectly.
problem Expressive power of shallow neural networks with bandlimited random weights.
method Ridgelet analysis for deriving approximation error lower bounds.
result Bandlimited random weights can lead to non-zero approximation error.
We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, …
We study signal recovery on graphs based on two sampling strategies: random sampling and experimentally designed sampling. We propose a new class of smooth graph signals, called approximately bandlimited, which generalizes the bandlimited class and is similar to the globally smooth class. We then propose two recovery s…
Graph neural networks can be adapted to new graphs with a limit object called graphon NNs.
problem Transferability of graph neural networks across different graphs.
method Introduced graphon NNs as limit objects of GNNs and proved a bound on the difference between GNN and graphon-NN outputs.
result The bound on the difference between GNN and graphon-NN outputs vanishes with growing number of nodes if the graph convolutional filters are bandlimited.
Neural networks outperform NTK on compositional tasks, revealing a complexity gap.
problem Understanding the performance gap between neural networks and NTK on tasks with compositional structure.
method Characterized Fourier and architectural complexities, and analyzed the minimax rates of the architecture class.
result The NTK estimator is exponentially sub-optimal compared to the minimax floor when complexities decouple.
The aim of this paper is to propose distributed strategies for adaptive learning of signals defined over graphs. Assuming the graph signal to be bandlimited, the method enables distributed reconstruction, with guaranteed performance in terms of mean-square error, and tracking from a limited number of sampled observatio…
Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a feature vector for each object, and run k-means on these features t…
Sampling and Reconstruction of Graph Signals via Weak Submodularity and Semidefinite Relaxationstat.ML
We study the problem of sampling a bandlimited graph signal in the presence of noise, where the objective is to select a node subset of prescribed cardinality that minimizes the signal reconstruction mean squared error (MSE). To that end, we formulate the task at hand as the minimization of MSE subject to binary constr…
In this paper, we study the adversarial attack and defence problem in deep learning from the perspective of Fourier analysis. We first explicitly compute the Fourier transform of deep ReLU neural networks and show that there exist decaying but non-zero high frequency components in the Fourier spectrum of neural network…
Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysismath.PR
Quantifies polynomial approximation rates for smooth functions under various distributions.
problem Approximating smooth functions with polynomials under different distributional constraints.
method Develops a quantitative analogue of Carleman's theorem using complex analysis.
result Establishes superexponential rates of approximation for certain function classes over general distributions.
TKRR improves KRR performance by aligning target functions with kernels.
problem Improving kernel ridge regression performance through target alignment.
method Focuses on truncated kernel ridge regression (TKRR) with an additional spectral truncation parameter.
result TKRR can achieve faster rates than full KRR, reaching parametric rates.
A number of applications in engineering, social sciences, physics, and biology involve inference over networks. In this context, graph signals are widely encountered as descriptors of vertex attributes or features in graph-structured data. Estimating such signals in all vertices given noisy observations of their values…