Source-linked AI summary
Kernel Singular Value Decomposition with Extension to Multiple Data Sources
Xinjie Zeng, Qinghua Tao, Johan Suykens
TL;DR
Classical Mercer-kernel methods are limited for asymmetric relationships and joint learning across multiple data sources. eKSVD extends KSVD with pair-wise source couplings and complementary covariance- and neural-network-based formulations. Experiments report competitive performance and guidance on solver selection, while the NN variant depends heavily on label supervision and hyperparameter tuning.
Problem
Classical Mercer kernels are limited for asymmetric relationships, while learning multiple sources independently can be insufficient when relevant information spans sources.
Source: §1 · p. 1Method
eKSVD extends KSVD to multiple sources by jointly learning nonlinear projections with pair-wise couplings, with dual, covariance-based, and neural-network formulations.
Source: §1 · pp. 1–2, §3 · p. 2, §3.1 · p. 2Results
Experiments on real-world datasets demonstrate competitive performance and provide empirical guidance on solver selection.
Source: §5 · p. 4Takeaways & Limitations
The covariance formulation and NN-based explicit mappings offer complementary approaches, while the experiments provide solver-selection guidance.
Source: §1 · p. 2, §4 · p. 4, §5 · p. 4The NN-based variant relies heavily on label supervision and hyperparameter tuning, and the primal analysis concerns stationarity because its objective is unbounded above.
Source: §3.1 · p. 2, §5 · p. 4
Abstract
from arXiv · showhide
Kernel Singular Value Decomposition (KSVD) learns a pair of singular vectors w.r.t. an asymmetric kernel matrix, which can be induced by two data sources, e.g., the queries and keys in self-attention or the rows and columns of a given matrix. In this work, we extend KSVD to multiple data sources, namely eKSVD, which conducts joint nonlinear feature learning upon asymmetric kernels. In the primal formulation, the projections associated with each data source are jointly learned to capture maximal information, while incorporating pair-wise couplings. With the Lagrangian and its Karush-Kuhn-Tucker (KKT) conditions, the optimization in the dual leads to a generalization of the shifted eigenvalue problem in Lanczos decomposition theorem of KSVD. Further, a covariance-based framework is derived together with using neural networks (NNs) for explicit feature mappings, complementary to the kernel-based interpretation and optimization. Numerical experiments verify the effectiveness of our eKSVD compared to methods based on Mercer kernels for tackling multiple data sources, and our innovation of deploying NNs demonstrates great flexibility for kernel methods.
1. INTRODUCTION
SVD is limited in capturing nonlinear patterns, while asymmetric relationships and multiple data sources motivate extending kernel SVD beyond Mercer kernels and its original two-source setting. The paper introduces eKSVD to jointly learn nonlinear projections across sources with pair-wise couplings, and reports advantages over Mercer-kernel methods.
1. INTRODUCTION
- SVD’s truncated form is an optimal low-rank approximation in Frobenius norm, but SVD lacks flexibility for nonlinear patterns.KSVD extends SVD to feature spaces using asymmetric kernels.Source: §1 · p. 1
- Asymmetry in directed graphs, biclustering, and self-attention is poorly captured by classical Mercer kernels, motivating asymmetric feature learning.KSVD is formulated to accommodate asymmetric kernels.Source: §1 · p. 1
- Learning data sources independently can be insufficient when relevant information spans multiple representations or tasks, motivating joint learning beyond KSVD’s two-source setting.Existing joint kernel methods such as MCCA and MvKPLS remain limited to Mercer kernels.Source: §1 · p. 1
- eKSVD jointly learns nonlinear projections for multiple sources with pair-wise couplings, derives a generalized shifted eigenvalue problem, and reports advantages over Mercer-kernel methods.A covariance-based framework and neural-network feature mappings complement its kernel formulation.Source: §1 · pp. 1–2
2. BACKGROUND
The background connects SVD to a shifted eigenvalue problem and presents KSVD as a two-source nonlinear feature-learning method based on asymmetric kernels. Its dual formulation uses Lagrangian and KKT conditions, with the shifted eigenvalue problem yielding the SVD of the cross-source kernel matrix.
2. BACKGROUND
- The Lanczos decomposition theorem establishes equivalence between SVD solutions and a shifted eigenvalue problem.The theorem represents a nonzero rank-r matrix using rank-r factors with orthonormal bases and a positive diagonal matrix.Source: §2 · p. 2
- KSVD learns nonlinear features for two data sources using an asymmetric kernel and jointly maximizes their projection variances with a coupling term.The sources can be represented by feature maps ϕ and ψ, with projection scores e_i and r_j.Source: §2 · p. 2
- Lagrangian and KKT conditions yield the KSVD dual formulation, whose shifted eigenvalue problem gives the SVD of K_xz.K_xz is the cross-source kernel matrix, with entries defined by similarities between feature-mapped samples from the two sources.Source: §2 · p. 2
3. THE PROPOSED METHODOLOGY
The methodology extends KSVD to multiple data sources through joint projection learning and pair-wise couplings, with kernel and covariance formulations and a neural-network alternative.
3.1. Modeling with LSSVMs
- The LSSVM primal formulation jointly maximizes projection variances across sources while regularizing pair-wise couplings; it reduces to KSVD when Q = 2.Because the objective is unbounded above, the analysis concerns stationary points rather than optimality.Source: §3.1 · p. 2
3.2. Optimization with Kernels
- The dual formulation is an eigendecomposition of a structured matrix of asymmetric kernels, whose entries encode couplings between data sources.The formulation retains eigenvectors associated with the largest positive eigenvalues.Source: §3.2 · pp. 2–3
3.3. Optimization with Covariances
- The covariance formulation provides an alternative optimization framework, and its generally nonsymmetric matrix has real eigenvalues and eigenvectors.Each source covariance matrix is used in the resulting formulation.Source: §3.3 · p. 3
3.4. Optimization with Neural Networks
- The kernel and covariance implementations can face scalability constraints as their matrices grow, motivating parametric neural networks as explicit feature mappings combined with a task loss.The proposed neural objective is min J2 + ηLtask, with η tunable.Source: §3.4 · p. 3
- Solutions to the generalized shifted eigenvalue problem yield a zero value for the primal objective, motivating the neural-network alternative.When retaining multiple components, the objective can be replaced by the sum of the component objectives Jk.Source: §3.4 · p. 3
4. NUMERICAL EXPERIMENTS
Across seven benchmarks, the experiments compare eKSVD implementations with kernel-based feature-learning baselines and evaluate learned features using downstream classifiers. eKSVD performs well on most datasets, while covariance implementations can offer computational advantages when N exceeds the feature dimension.
Experimental setup
- The seven benchmarks span multimedia, text, and digit classification; each uses a 60/20/20 train/validation/test split and five-seed downstream evaluation.Reuters-600 and NUSOBJ have five sources; the other datasets have three.Source: §4 · p. 3
Results and discussion
- On test macro-F1, unsupervised eKSVD beats baselines on most datasets; Neural eKSVD beats them on six, but trails Dual eKSVD on NUSOBJ.Results are averaged over five splits.Source: §4 · p. 4, Table 1 · p. 4
- Neural eKSVD jointly trains explicit feature mappings and a downstream classifier with label supervision; its NUSOBJ result may reflect interactions during joint learning.The implementation uses cross-entropy for classification tasks and treats γ as a learnable parameter.Source: §4 · p. 4
- Given identical feature maps, Covariance eKSVD reproduces Dual eKSVD performance and is faster in training and inference when N exceeds dϕ.Covariance solves a Qdϕ × Qdϕ eigenproblem rather than Dual's QN × QN problem and avoids large-N kernel evaluations at inference.Source: §4 · p. 4, Table 2 · p. 4
- On NUSOBJ, Covariance eKSVD is much faster to train, while its inference-time difference from Nyström-based Dual eKSVD is negligible.For NUSOBJ, N denotes the Nyström subset size; Dual eKSVD performs SVDs on larger feature matrices containing all training samples.Source: §4 · p. 4, Table 2 · p. 4
5. CONCLUSION
The paper concludes that eKSVD extends KSVD to multiple sources through kernel and covariance formulations, with a neural variant for jointly learning explicit mappings and projection weights. Experiments demonstrate competitive performance, while the neural variant remains dependent on labels and hyperparameter tuning.
5. CONCLUSION
- eKSVD extends KSVD to multiple sources under the LSSVM framework, deriving a generalized shifted eigenvalue problem and a complementary covariance formulation.The generalized problem uses cross-source kernel matrices.Source: §5 · p. 4
- The neural variant jointly learns explicit feature mappings and eKSVD projection weights, but relies heavily on label supervision and hyperparameter tuning.The authors identify self-supervised objectives as future work to reduce reliance on labels.Source: §5 · p. 4
- Experiments on real-world datasets demonstrate competitive performance and provide empirical guidance on solver selection.Source: §5 · p. 4