LoCCA: Localized Chebyshev Cross Approximation for Kernel Matrix Factorization via Nodal Perturbation Stability

1 Introduction

• Kernel matrices are dense, but well-separated submatrices often have numerical low-rank structure, motivating efficient matrix compression.Algebraic methods such as ACA use selected rows and columns, while analytic interpolation yields bases rather than a skeleton representation; hybrid methods seek both properties.Source: §1 · pp. 1–2
• The motivating gap is that displacing ideal-grid nodes onto unstructured point clouds violates standard interpolation results, leaving Chebyshev stability under such perturbations unresolved.Rigid tensor-product grids can also sample empty or nearly singular regions in non-standard geometries.Source: §1 · p. 2
• LoCCA selects physical nearest neighbors of continuous Chebyshev nodes, then applies RRQR to the resulting submatrix to construct a skeleton representation.The two stages are localized node selection (LoC-NS) followed by localized cross-approximation.Source: §1 · pp. 2–3
• The theory bounds perturbed Lebesgue-constant growth, interpolation-operator deviation, and global cross-approximation error, and extends stability to continuous multivariate hypercubes.The stated Lebesgue-constant bound is polynomial-logarithmic in p; the interpolant deviation depends on perturbation distance δ and is polynomial-logarithmic for smooth functions.Source: §1 · p. 3
• Across tested kernels, LoCCA has accuracy and spread comparable to SI without structured grid topologies, while ACA shows wider error distributions and extreme outliers on irregular clouds.The introduction also reports failures of SI in unstructured settings where tensor-product constraints cause sample starvation or geometric misalignment.Source: §1 · p. 3
• LoCCA achieves up to a 10× speedup over ACA with similar accuracy, while eliminating the wide error variance and extreme outlier spikes observed in ACA.Source: §1 · p. 3

2 Preliminaries

• The preliminaries set out notation and structural metrics as prerequisites for analyzing interpolation operators under node perturbations.Frequently used notation is collected in Table 1.Source: §2 · p. 3, Table 1 · p. 3

2.1 Basic Definitions

• Fill distance h_X is the maximum distance from any point in the domain to its nearest point in X; a local neighborhood of size l contains the l nearest points to a target node.The preliminaries also define the continuous supremum norm and numerical rank at tolerance ε.Source: §2.1 · p. 4

2.2 Chebyshev Interpolation and Node Perturbations

• First-kind Chebyshev nodes are roots of a degree-p Chebyshev polynomial and have minimum separation bounded between π²/(2p²) and π²/p².The perturbation setup constrains displaced nodes to remain close to their ideal nodes and preserve separation.Source: §2.2 · p. 4
• The preliminaries establish harmonic-sum bounds for Chebyshev configurations and a grid-receptive sum, with the perturbation threshold yielding a dampened logarithmic bound.These lemmas are stated as ingredients for the later perturbation analysis.Source: §2.2 · p. 5

3.1 Localized Chebyshev Nodes Selection (LoC-NS)

• LoC-NS selects physical points nearest to continuous Chebyshev reference nodes, producing filtered sets that preserve their geometric distribution and contain at most lP points each.The selected points remain within the original unstructured data and are used in the subsequent skeletonization step.Source: §3.1 · p. 6

3.2 Localized Chebyshev Cross Approximation (LoCCA)

• The algorithm is evaluated numerically over a wide range of kernel functions and domains.The experiments primarily focus on kernels of the form K(x, y) = κ(∥x − y∥2).Source: §3.2 · p. 6
• LoCCA builds a cross matrix from the filtered sets and applies RRQR to select row and column skeleton indices for a low-rank cross-approximation.The numerical rank is the larger selected-set size; when the sizes mismatch, the smaller index set is expanded to reduce approximation error.Source: §3.2 · pp. 6–7

4.1 Stability and Error Bounds under Perturbations

• Under the uniform threshold constraint, the perturbed Lebesgue constant satisfies ˜Λp ≤ p^CΛp = O(p^C log p).The authors conjecture that the p^C factor is an artifact and that a tighter logarithmic bound holds, but proving it remains open; Theorem 4.1 suffices for their global matrix convergence guarantees.Source: §4.1 · pp. 7, 9
• For f ∈ C1[−1,1], the interpolant deviation is bounded by ∥Ipf − ˜Ipf∥L∞ ≤ (1 + pCp)δΛp∥f∥C1[−1,1], with Cp growing polynomial-logarithmically.This bound assumes perturbed nodes satisfy the proximity condition and uniform threshold constraint.Source: §4.1 · p. 10

4.2 Extension to Multivariate Domains via Tensor-Product Decompositions

• The one-dimensional stability result extends to the hypercube Ω = [−1,1]^d by applying tensor-product interpolation operators along each coordinate direction.The resulting multivariate uniform error bound uses the one-dimensional result and coordinatewise node proximity.Source: §4.2 · pp. 11–12

4.3 Error Bounds and Convergence for Well-Separated Analytic Kernels

• For functions analytic in a Bernstein ellipse and bounded there, Corollary 4.1 applies the perturbed interpolation error result under Theorem 4.2’s assumptions.The proof combines the Chebyshev interpolation error’s geometric decay with the perturbation bound from Theorem 4.2.Source: §4.3 · p. 12
• The LoCCA approximation error is at most C~·ε uniformly for all x and y, with C~ depending polynomial-logarithmically on the skeleton and neighborhood sizes.The approximant is K(x, eNY)K(eNX, eNY)^-1K(eNX, y). The theorem assumes Strong RRQR skeletons, while the numerical implementation uses standard RRQR.Source: §4.3 · pp. 12–13
• Localized CUR yields a residual bounded by a low-degree polynomial times σ_(r+1)(K), while its interpolation matrices have polynomially bounded norms.The residual bound is ∥Eqr(NX, NY)∥2 ≤ p1(nx, ny, r)σ_(r+1)(K); the interpolation matrix norms are bounded by p2(nx, ny, r).Source: §4.3 · p. 13
• The localized skeleton inverse and both LoCCA basis operators are polynomially bounded, controlling the mixed residual terms in the convergence proof.The inverse bound scales as a low-degree polynomial divided by ε, and the ε factor in the CUR residual cancels in mixed terms.Source: §4.3 · pp. 13–14

4.4 Relationship between the Chebyshev grid and its Local neighbors

• For a uniform Cartesian grid in a d-dimensional hypercube, the global l-th neighbor distance is at most Cd,X(l/n)^(1/d).The constant Cd,X depends only on the dimension and domain volume.Source: §4.4 · pp. 14–15

5 Numerical Experiments

• Across 500 random grids, LoCCA’s error spread was compact and comparable to SI’s, while ACA showed wider distributions and extreme outliers.The boxplots summarize relative errors by method and kernel at three target tolerances.Source: §5 · p. 16, Figure 2 · p. 16
• LoCCA closely tracks truncated SVD’s relative-error decay as approximation rank increases, achieving near-optimal approximation.The comparison covers all tested kernels.Source: §5 · pp. 16–17, Figure 3 · p. 17
• Across tested kernels, relative error reaches the 10^-8 target around p ≈ 7; rank initially rises with p, then saturates.Larger p beyond this point increases candidate-set size and factorization cost without additional accuracy or rank reduction.Source: §5 · p. 17, Figure 5 · p. 18
• Runtime scales linearly with N, while LoCCA’s execution time remains flat as rank increases or tolerance tightens.The reported rank- and tolerance-dependent comparison is against ACA.Source: §5 · pp. 17–18, Figure 6 · p. 19
• On both complex geometries, LoCCA maintains error control as N increases, whereas SI exhibits relative errors near O(1).The geometries are disconnected Crescent-and-Core and Concentric Ring-and-Core configurations.Source: §5 · pp. 19–20, Figure 7 · p. 19, Figure 8 · p. 20

6 Conclusion

• LoCCA maps continuous tensor-product Chebyshev nodes to discrete physical nearest neighbors through LoC-NS, bridging function approximation and algebraic skeletonization without rigid tensor-product grids.Source: §6 · p. 20
• The perturbation theory bounds changes in Lagrange interpolants in terms of maximum node displacement δ, extends stability to d-dimensional hypercubes, and guarantees global cross-approximation error control on point clouds under Strong RRQR.The perturbed Lebesgue constant also has an a priori upper bound.Source: §6 · p. 20
• LoCCA achieves approximately a 10× speedup over ACA, with execution time remaining flat across target rank and precision tolerance; it maintains error control where SI has O(1) relative error on non-convex and disconnected geometries.Its skeleton ranks closely mirror the minimal theoretical rank prescribed by optimal truncated SVD.Source: §6 · p. 20
• Proving the sharp logarithmic asymptotic growth of the perturbed Lebesgue constant remains open, although the established bound suffices for the paper’s global matrix convergence guarantees.Numerical experiments suggest the polynomial factor in the current bound may be a surplus estimate.Source: §6 · pp. 20–21

Perturbation setup

• The perturbed node vector η stays within δ of the Chebyshev nodes ξ, subject to the threshold constraint δ ≤ m/4.Source: A Some Auxiliary Results used in the… · p. 21

Perturbed-node spacing

• A separation margin of at least half the original node spacing bounds the relative spacing change by 4δ/|ξ_k−ξ_j|.The argument uses the proximity condition and log(1+t) ≤ t.Source: A Some Auxiliary Results used in the… · p. 21

Derivative-weight bounds

• The derivative-weight ratio is bounded by a polynomial in p, with uniform constants independent of p, i, and k.The displayed intermediate estimate gives a bound of the form C0 p^α.Source: A Some Auxiliary Results used in the… · p. 21

Chebyshev-node baseline

• For the unperturbed Chebyshev nodes, the derivative-weight ratio is bounded above by p.Source: A Some Auxiliary Results used in the… · p. 21

Experimental setup

• The experiment uses the Runge function on [−1, 1] to test stability and asymptotic convergence under the admissible perturbation condition δ ≤ m/4.Source: B Numerical Investigation of Perturbed… · p. 22

Runge-function interpolation

• Across the full domain and zoomed boundary regions, perturbed interpolation remains well-conditioned, with its deviation from the unperturbed interpolant controlled by δ.The experiment uses p = 15 nodes in Figure 9.Source: Figure 9 · p. 22, B Numerical Investigation of Perturbed… · p. 22

Numerical comparison

• Perturbed Chebyshev interpolation tracks the unperturbed interpolant, while equidistant-node interpolation shows exponential error growth as p increases.Figure 10a supports the tracking comparison; Figure 10b reports the equidistant-node error explosion.Source: Figure 10 · p. 22, B Numerical Investigation of Perturbed… · p. 22

Benchmark setup

• Table 3 reports relative errors and execution times averaged over 10 trials for domains sharing the corner (1, 2), with N = 7072 points per domain.Source: C Tabular Benchmarks on Vertex-Sharing… · pp. 22–23, Table 3 · p. 23

Comparison protocol

• The LoCCA-selected rank is prescribed to ACA and SI for direct comparison; the stated LoCCA setting is p = 45, P = 2025 nodes, and l = 1.Source: C Tabular Benchmarks on Vertex-Sharing… · p. 23

Parameter choice

• The chosen p corresponds to ε = 10^-8, and the passage notes that selecting p for ε = 10^-4 or 10^-6 can yield better LoCCA execution time than ACA.Source: C Tabular Benchmarks on Vertex-Sharing… · p. 23

• LoC-TSVD forms a compressed submatrix from localized neighbors, then uses economy-sized QR and SVD to extract rank-r orthonormal spectral factors in O(P^2N) time and O(PN) space.Source: D Spectral Decomposition using… · p. 23
• LoC-TSVD's relative errors are virtually indistinguishable from exact truncated SVD across listed kernels on uniform and random discretizations.Table 4 covers target tolerances ε ∈ {10^-4, 10^-6, 10^-8}; random-grid metrics average 500 point realizations using the uniform-grid rank.Source: D Spectral Decomposition using… · p. 24, Table 4 · p. 24
• Across 500 random point-cloud realizations, Figure 11 shows LoC-TSVD's error interquartile range tightly mirroring exact SVD's optimal lower bound at ε ∈ {10^-4, 10^-6, 10^-8}.Source: D Spectral Decomposition using… · p. 24
• Figure 12a shows normalized singular values overlaying the exact SVD spectrum, while Figure 12b keeps normalized element-wise error below ε = 10^-8.Source: D Spectral Decomposition using… · p. 24
• LoC-TSVD's subspace error is O(10^-5) to O(10^-3), while orthogonality drift stays near 10^-15 across kernels and tolerances.The thin-QR post-projection yields orthonormal basis columns to floating-point precision despite localized Chebyshev proxy sampling.Source: D Spectral Decomposition using… · p. 24