# Finite-Band Polynomial Seed Bank

- ID: 1603
- Canonical URL: https://synthcore.org/idea/1603/finite-band-polynomial-seed-bank
- API JSON: https://synthcore.org/api/idea/1603.json
- API Markdown: https://synthcore.org/api/idea/1603.md
- Verification status: unverified
- Source: [arXiv:2607.05294](https://arxiv.org/abs/2607.05294)
- Category: architecture
- Solves: speedup, scalability, memory
- ML areas: graph-nn, ssm, initialization, inference-speedup
- Math tags: spectral-theory, linear-algebra, approximation-theory, numerical-analysis
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Construct one reference Lanczos basis for a symmetric propagation operator H, then derive several seed-specific spectral responses for Q_a(H)x_0 through finite-band polynomial connectors. With degree-r seeds, each transformed basis vector uses at most 2r+1 neighboring reference basis vectors, avoiding a separate Lanczos factorization for every seed.

## Mathematical statement

Let H be a self-adjoint matrix, x_0 a reference cyclic vector, and d\mu(E) its spectral measure. Let P_n be monic orthogonal polynomials for \mu, with squared norms h_n, and let the reference Lanczos recurrence be H P_n(H)x_0=b_{n+1}P_{n+1}(H)x_0+a_nP_n(H)x_0+b_nP_{n-1}(H)x_0. For a polynomial Q of degree r, the prepared seed x_Q=N_Q^{-1/2}Q(H)x_0 has reweighted measure d\mu_Q(E)=|Q(E)|^2d\mu(E)/N_Q, where N_Q=\langle x_0,Q(H)^2x_0\rangle. The new monic orthogonal polynomial \widetilde P_n for \mu_Q is a finite connector of the reference polynomials: \widetilde P_n(E)=\sum_{j=0}^{2r}\Gamma_{n,n+j}P_{n+j}(E), with \Gamma_{n,n}=1. For a factored Q with roots \xi_a, the coefficients are determined by the finite Christoffel system imposing zeros and derivative constraints at repeated roots. This finite bandwidth, rather than a generic dense basis change, is the computational property transferred to the neural module.

## Key formulas

- $$d\mu_Q(E)=\frac{|Q(E)|^2}{N_Q}\,d\mu(E),\qquad N_Q=\langle x_0,Q(H)^2x_0\rangle$$
- $$H P_n(H)x_0=b_{n+1}P_{n+1}(H)x_0+a_nP_n(H)x_0+b_nP_{n-1}(H)x_0$$
- $$\widetilde P_n(E)=\sum_{j=0}^{2r}\Gamma_{n,n+j}P_{n+j}(E),\qquad \Gamma_{n,n}=1$$
- $$\begin{pmatrix}P_n(\xi_1)&\cdots&P_{n+2r-1}(\xi_1)\\ P_n'(\xi_1)&\cdots&P_{n+2r-1}'(\xi_1)\\ \vdots&&\vdots\\ P_n(\xi_r)&\cdots&P_{n+2r-1}(\xi_r)\\ P_n'(\xi_r)&\cdots&P_{n+2r-1}'(\xi_r)\end{pmatrix}\begin{pmatrix}\Gamma_{n,n}\\ \vdots\\ \Gamma_{n,n+2r-1}\end{pmatrix}=-\frac{1}{h_r}\begin{pmatrix}P_{n+2r}(\xi_1)\\ P_{n+2r}'(\xi_1)\\ \vdots\\ P_{n+2r}(\xi_r)\\ P_{n+2r}'(\xi_r)\end{pmatrix}$$

## Implementation notes

Integrate the method as a spectral propagation block in a graph neural network or linear state-space layer. Inputs are a symmetric normalized graph operator H, node features X, a reference seed x_0, propagation depth L, and a bank of learned low-degree polynomials Q_a(E)=\sum_{k=0}^r q_{a,k}E^k, initially with r=1 or r=2. Run Lanczos once on H and x_0, storing the tridiagonal coefficients a_n,b_n and reference responses Z_n=P_n(H)X. Estimate the moments needed for N_{Q_a}=\langle x_0,Q_a(H)^2x_0\rangle from the Lanczos tridiagonal or from short recurrence evaluations. For each seed, construct a small connector system from the orthogonality conditions under the reweighted measure; if Q_a is represented by roots, use the displayed Christoffel zero and derivative constraints, otherwise estimate the Gram matrix G_{ij}=\int Q_a(E)^2P_i(E)P_j(E)d\mu(E) by Gauss quadrature from the Lanczos tridiagonal. Solve for the coefficients \Gamma_{a,n,n+j}, then form Ztilde_{a,n}=N_{Q_a}^{-1/2}\sum_{j=0}^{2r}\Gamma_{a,n,n+j}Z_{n+j}. Concatenate the seed channels or combine them with a learned softmax gate before the graph readout. Pseudocode is: build T from a_n,b_n; compute quadrature nodes and weights; evaluate P_n and Q_a; solve each small connector system; apply the width-2r sliding transform to Z; normalize and gate. The mathematics supplies the finite-band form and normalization, while quadrature and connector conditioning are estimated numerically. First test on a 2-layer GCN or spectral graph model on Cora with L=32 and four degree-2 seeds. Compare against independently rerunning Lanczos for each seed and against ordinary Chebyshev features. Measure preprocessing time, peak memory, output relative error, and validation accuracy. A useful success criterion is at least 3x lower basis-construction cost, less than 1e-3 relative feature error versus separate Lanczos, and equal or improved validation accuracy.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.