Popular graph neural networks implement convolution operations on graphs based on polynomial spectral filters. In this paper, we propose a novel graph convolutional layer inspired by the auto-regressive moving average (ARMA) filter that, compared to polynomial ones, provides a more flexible frequency response, is more …
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
48 results for “polynomial filtering”
Paper revisits graph-CNNs using Laplace-Beltrami spectral filters and polynomials.
problem Improving spectral graph convolutional neural networks (graph-CNNs).
method Developed Laplace-Beltrami CNN (LB-CNN) by replacing graph Laplacian with LB operator and approximating spectral filters using Chebyshev, Laguerre, and Hermite polynomials.
result Classification accuracy of LB-CNN is not dependent on the type of polynomials or operators.
Identifies directed graphs from node measurements using polynomial filters.
problem Inferring directed network topology from nodal measurements.
method System identification of graph convolutional filter followed by topology inference.
result Effective recovery of directed graphs from measurements.
The paper introduces a quantum state system to count perfect matchings in graphs.
problem Counting perfect matchings in graphs using quantum state systems.
method Topological quantum field theory (TQFT) and spectral sequences.
result The filtered -color vertex homology for is generated by perfect matchings.
The Hodrick-Prescott (HP) filter is one of the most widely used econometric methods in applied macroeconomic research. Like all nonparametric methods, the HP filter depends critically on a tuning parameter that controls the degree of smoothing. Yet in contrast to modern nonparametric methods and applied work with these…
New algorithm learns linear dynamical systems from measurements.
problem Learning system dynamics from linear measurements efficiently and accurately.
method Method of moments estimator to directly estimate Markov parameters.
result First polynomial time algorithm for learning linear dynamical systems.
PDSim: A Shiny App for Simulating and Estimating Polynomial Diffusion Models in Commodity Futuresq-fin.ST
PDSim simulates and estimates commodity futures prices using polynomial diffusion models.
problem Simulating and estimating commodity futures prices using polynomial diffusion models.
method Developed an R package with a Shiny app for simulation and estimation of commodity futures prices using polynomial diffusion models.
result PDSim is the only package specifically designed for the simulation and estimation of the polynomial diffusion model.
We give a polynomial-time algorithm for learning latent-state linear dynamical systems without system identification, and without assumptions on the spectral radius of the system's transition matrix. The algorithm extends the recently introduced technique of spectral filtering, previously applied only to systems with a…
We present the notion of a filtered bundle as a generalisation of a graded bundle. In particular, we weaken the necessity of the transformation laws for local coordinates to exactly respect the weight of the coordinates by allowing more general polynomial transformation laws. The key examples of such bundles include af…
Proposes a Gaussian process for graph signals using adaptive spectral kernels.
problem Predicting signals on graph nodes with various structures.
method Spectral kernel learning approach that incorporates a polynomial function in the graph spectral domain.
result The model accurately recovers ground truth spectral filters and outperforms in real-world graph data.
The Score Kalman Filtereess.SY
A new filter reduces density fitting to a linear solve, improving performance on nonlinear systems.
problem Nonlinear Bayesian filtering challenges in representing belief distributions.
method Combines score matching with Stein's identity to avoid partition function evaluation.
result The Score Kalman Filter (SKF) outperforms existing methods on nonlinear systems.
Paper describes a state sum formula for a graph coloring polynomial.
problem Counting -face colorings of ribbon graphs for various .
method Combines topological quantum field theory and diagrammatic tensors.
result Describes a state sum formula for the total face color polynomial.
The paper addresses online prediction in marginally stable systems with bounded perturbations.
problem Online prediction in marginally stable linear dynamical systems with adversarial or stochastic perturbations.
method The online least-squares algorithm is used to achieve sublinear regret, with a refined regret analysis and a structural lemma.
result The online least-squares algorithm achieves sublinear regret, with polynomial dependence on the system's parameters.
When is Particle Filtering Efficient for Planning in Partially Observed Linear Dynamical Systems?cs.LG
This paper studies when particle filtering is efficient for planning in partially observed systems.
problem The efficiency of particle filtering for planning in partially observed linear dynamical systems.
method Coupling of ideal and approximate sequences to bound particle complexity.
result Polynomially many particles suffice for stable systems to approximate optimal planning.
Algorithm learns polynomials in Gaussian inputs with reduced sample complexity.
problem Learning polynomials of few relevant dimensions in high-dimensional data.
method Filtered PCA for warm start, geodesic SGD for accuracy.
result Sample complexity roughly , runtime .
We analyze the convergence of (stochastic) gradient descent algorithm for learning a convolutional filter with Rectified Linear Unit (ReLU) activation function. Our analysis does not rely on any specific form of the input distribution and our proofs only use the definition of ReLU, in contrast with previous works that …
No-trick kernel adaptive filtering uses deterministic features for scalability and robustness.
problem Scalability issues in kernel methods for large datasets.
method Deterministic feature-map construction using polynomial-exact solutions.
result Deterministic features outperform random Fourier features in performance and scalability.
Simplifies and optimizes learning from untrusted batches with structure.
problem Learning from untrusted batches with potential structure.
method Synthesizes techniques from JO19 and CLM19, using Haar wavelets and soft filtering.
result Achieves sublinear sample complexity with polynomial time complexity.
We compute different versions of link Floer homology and for any -space link with two components. The main approach is to compute the -function of the filtered chain complex which is determined by the Alexander polynomials of every sublink of the -space link. As an application, Thurst…
Generative model controls heterophily in graph signals.
problem Controlling heterophily in graph signals for better model effectiveness.
method Combines graphon-based generator with spectral filtering of Gaussian node features.
result Establishes theoretical guarantees for heterophily control and convergence.
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.
New method proves cosmetic surgery conjecture for certain knots.
problem Proving the cosmetic surgery conjecture for specific knots.
method Using filtered instanton homology and Chern-Simons filtration.
result Reduced the conjecture to surgeries of on genus 2 knots.
The sigma-point filters, such as the UKF, which exploit numerical quadrature to obtain an additional order of accuracy in the moment transformation step, are popular alternatives to the ubiquitous EKF. The classical quadrature rules used in the sigma-point filters are motivated via polynomial approximation of the integ…
New method controls linear systems with adversarial disturbances.
problem Controlling linear dynamical systems under adversarial conditions.
method Novel convex relaxation using spectral filters from Hankel matrix eigenvectors.
result Polylogarithmic running time improvement over prior methods.
We present an efficient and practical algorithm for the online prediction of discrete-time linear dynamical systems with a symmetric transition matrix. We circumvent the non-convex optimization problem using improper learning: carefully overparameterize the class of LDSs by a polylogarithmic factor, in exchange for con…
This paper extends link invariants using functors on nanophrases.
problem Link invariants are less informative in certain categories.
method Introduces functors from nanophrases to virtual strings, pseudolinks, quasilinks, and free links.
result Extends the Jones pseudolink polynomial to general nanophrases.
We study additive models built with trend filtering, i.e., additive models whose components are each regularized by the (discrete) total variation of their th (discrete) derivative, for a chosen integer . This results in th degree piecewise polynomial components, (e.g., gives piecewise constant co…
Algorithm efficiently learns deep ReLU networks with polynomial runtime in depth and parameters.
problem Learning deep ReLU networks with polynomial runtime.
method Algorithm using filtered PCA and lattice polynomial analysis.
result First nontrivial results for networks of depth more than two with polynomial runtime.
Efficient algorithm predicts unknown linear systems with long-term memory.
problem Predicting unknown and partially observed linear dynamical systems with long-term memory.
method Bounding the generalized Kolmogorov width of the Kalman filter model using spectral methods and conducting tight convex relaxation.
result Competes with Kalman filter in hindsight with only logarithmic regret.
Kronecker trend filtering improves lattice data smoothing.
problem Estimating smooth functions on lattice data.
method Penalized least squares with Kronecker products of univariate trend filtering penalties.
result Kronecker trend filtering outperforms linear smoothers in high dimensions.
We define a hierarchy of special classes of constrained Willmore surfaces by means of the existence of a polynomial conserved quantity of some type, filtered by an integer. Type 1 with parallel top term characterises parallel mean curvature surfaces and, in codimension 1, type 1 characterises constant mean curvature su…
Semi-Supervised Classification on Non-Sparse Graphs Using Low-Rank Graph Convolutional Networkscs.LG
Graph Convolutional Networks (GCNs) have proven to be successful tools for semi-supervised learning on graph-based datasets. For sparse graphs, linear and polynomial filter functions have yielded impressive results. For large non-sparse graphs, however, network training and evaluation becomes prohibitively expensive. B…
We study trend filtering, a recently proposed tool of Kim et al. [SIAM Rev. 51 (2009) 339-360] for nonparametric regression. The trend filtering estimate is defined as the minimizer of a penalized least squares criterion, in which the penalty term sums the absolute th order discrete derivatives over the input points…
Develops polynomial diffusion models for multi-factor commodity futures dynamics.
problem Modeling futures prices using latent state variables for short and long-term stochastic factors.
method Polynomial diffusion models to incorporate non-linear effects, two filtering methods for estimation.
result Accurate estimation of futures prices despite parameter identification issues in polynomial diffusion models.
We show how spectral filters can improve the convergence of numerical schemes which use discrete Hilbert transforms based on a sinc function expansion, and thus ultimately on the fast Fourier transform. This is relevant, for example, for the computation of fluctuation identities, which give the distribution of the maxi…
Proposes a graph dynamics prior for more accurate relational inference.
problem Identifying interactions in dynamical systems from observed dynamics.
method Graph Dynamics Prior (GDP) that uses error amplification in non-local polynomial filters.
result Reconstructs graphs more accurately than previous methods, robust to under-sampling.
Seifert cohomology of treesmath.CO
To every tree we associate a filtered cochain complex. Its cohomology and the corresponding spectral sequence have clear combinatorial description. If a tree is the Dynkin diagram of a simple plane curve singularity, the graded Euler characteristic of this complex coincides with the Alexander polynomial of the link. In…
Study supports recovery of PDEs from noisy data using a specific regularization method.
problem Support recovery of PDEs from a single noisy trajectory.
method Applying ℓ1-regularized Pseudo-Least Squares model to a given data set.
result Support of ℓ1-c coefficients asymptotically converges to the true signed-support of the PDE.
This paper develops an asymptotic expansion technique in momentum space for stochastic filtering. It is shown that Fourier transformation combined with a polynomial-function approximation of the nonlinear terms gives a closed recursive system of ordinary differential equations (ODEs) for the relevant conditional distri…
New methods improve neural connectivity analysis at submillisecond timescales.
problem Limitations of standard spike train analysis methods in terms of temporal resolution and scalability.
method Developed Monte Carlo and polynomial approximation methods for continuous-time neural spike train analysis.
result Superior accuracy and scalability compared to traditional binned GLMs, enabling precise connectivity inference.
Let be a 2-periodic knot in with quotient . We prove a rank inequality between the knot Floer homology of and the knot Floer homology of using a spectral sequence of Hendricks, Lipshitz and Sarkar. We also conjecture a filtered refinement of this inequality, for which we giv…
We examine the relationship between the (untwisted) knot Floer cube of resolutions and HOMFLY-PT homology. By using a filtration induced by additional basepoints on the Heegaard diagram for a knot , we see that the filtered complex decomposes as a direct sum of HOMFLY-PT homologies of various subdiagrams. Jaeger's c…
Many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, call for estimating discrete distributions from data collected in batches, some of which may be untrustworthy, erroneous, faulty, or even adversarial. Previous estimators for this setting ran in e…
PolyNSD improves Neural Sheaf Diffusion with polynomial operators and spectral rescaling.
problem Limitations of common Neural Sheaf Diffusion implementations, including scalability and stability issues.
method Introduces Polynomial Neural Sheaf Diffusion (PolyNSD) with a degree-K polynomial propagation operator and spectral rescaling.
result PolyNSD achieves state-of-the-art results on both homophilic and heterophilic benchmarks with reduced runtime and memory requirements.
Study automorphism groups' action on Jacobi diagrams, leading to new decompositions.
problem Understanding automorphism groups' actions on Jacobi diagrams.
method Analyzing the induced actions on graded vector spaces and constructing polynomial functors.
result Indecomposable decomposition of and polynomial functor construction.
Novel algorithm learns sparse signal representations over topological spaces.
problem Sparse representation of signals over combinatorial topological spaces.
method Leveraging Hodge theory, the paper embeds topology into a dictionary structure via concatenated sub-dictionaries, each as a polynomial of Hodge Laplacians, and optimizes the dictionary coefficients and sparse signal representation via iterative alternating algorithms.
result Efficiently learned sparse representations and underlying relational structure of topological signals.
Samplets and multiwavelets constructed from scattered data converge to specific densities in the limit.
problem Constructing data-adapted multiresolution analyses and multiwavelets with flexible vanishing moments.
method Probabilistic framework for samplet construction; convergence to multiwavelets with broken polynomial densities.
result Samplet construction converges to multiwavelets in the infinite data limit.
Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.