REVIEW 3 major objections 4 minor 43 references
Kernel Recursive Least Squares Dictionary Learning Algorithm
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper proposes an online dictionary learning algorithm for kernel sparse representations that updates a virtual dictionary recursively with each new sample or mini-batch, and claims it matches the accuracy of batch-trained…
desk verdict A genuinely new RLS-based online kernel dictionary update with mostly careful derivations, but the normalization step is algebraically inconsistent and the experiments need statistical rigor. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The mechanism that carries the argument is the recursive update of $C = (W\Lambda W^{\top} + \xi I)^{-1}$, the inverse regularized Gram matrix of the sparse coefficient vectors. Using the Matrix Inversion Lemma, a new sample or mini-batch is incorporated as $C_{i+1} = \lambda^{-1}(C_i - u\alpha u^{\top})$, where $u = C_i w$ and $\alpha = (\lambda I_M + w^{\top} u)^{-1}$, and analogous rank-update formulas maintain the profile matrices $U$, $K$, $D$, and $\Psi$. The profile, the stored set of retained samples and their associated matrices, is controlled by a coherency-based growing rule and a row-norm-based pruning rule, and because the only matrices to be inverted are $M\times M$ for a mini-batch of size $M$, the per-iteration complexity drops to $O(L^2)$ for $M=1$ instead of requiring inversion of the full kernel matrix.
What would settle it
Train the same KRLS algorithm on a dataset where the informative samples arrive late or are initially rejected by the coherency threshold, and compare the steady-state classification accuracy or representation error against the batch KMOD dictionary trained on the same data; a clear accuracy gap persisting after many batches would indicate that the profile abstraction rules keep an unrepresentative subset.
Extended reading notes
Core claim
The paper's central claim is that the kernel dictionary learning problem admits a recursive least squares solution: given sparse representation coefficients for the stored samples, the optimal dictionary can be updated by low-rank corrections derived from the Matrix Inversion Lemma, rather than by gradient steps. The authors derive closed-form update equations for the inverse Gram matrix $C$, the dictionary Gram matrix $\Psi$, and the profile matrix $U$, and show that for a single sample these updates require only matrix-vector products. They state that this is the first online kernel dictionary learning algorithm based on the RLS method, and that it inherits the faster convergence of RLS relative to gradient-based alternatives. On four datasets, the resulting dictionaries yield classification accuracy that rises steadily toward the batch KMOD benchmark and exceeds the accuracy of the other online algorithms tested, while taking less training time per mini-batch.
Load-bearing premise
The paper assumes that the heuristic rules for deciding which samples to keep in memory preserve enough information that the smaller set of samples represents the data as well as the full set would.
Editorial extensions
If this is right
- A single new sample can be absorbed with only matrix-vector operations, making kernel dictionary learning practical for streaming data and for datasets too large for batch training.
- Classification accuracy increases steadily with the number of mini-batches and approaches the batch KMOD benchmark, so the method can serve as a substitute when full retraining is infeasible.
- The recursive least squares basis gives faster convergence than gradient-based online kernel dictionary learning methods, which matters when training time or data is limited.
- The algorithm is not restricted to a particular kernel, so it can be applied with any positive-definite kernel function.
Reading between the lines
- One extension the paper leaves implicit is using the forgetting factor to track non-stationary data, where the dictionary should adapt as the underlying distribution drifts.
- The same recursive update equations could be applied to regression or reconstruction tasks, since the objective is representation error rather than classification specifically.
- Alternative profile-selection criteria, such as distance to the span of the current dictionary, could be plugged into the growing and pruning steps without changing the update equations.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes KRLS DL, an online kernel dictionary learning algorithm that extends the recursive least squares dictionary learning method to reproducing kernel Hilbert spaces. The dictionary is represented implicitly through a profile of selected training samples, and the author derives recursive update equations, based on the matrix inversion lemma, for adding and removing samples, for pruning and growing the profile, and for dictionary normalization. The algorithm is evaluated on four classification datasets (USPS, ISOLET, EEG, DistNet) and compared with three existing online kernel dictionary learning algorithms and the batch KMOD algorithm, reporting improved accuracy and lower training time.
Significance. If the derivation is correct, the paper makes a useful contribution: it is, to my knowledge, the first online kernel dictionary learning algorithm based on recursive least squares, and the detailed appendix derivations plus the available code are strengths. The recursive updates for adding and removing samples (Sections 3.1 and 3.2) are carefully derived and, taken in isolation, are mathematically sound. The reported efficiency gains are potentially significant for online and real-time applications. However, the paper currently contains an internal inconsistency in the normalization step that affects the core recursive state, and the experimental section lacks the statistical rigor needed to support the strong 'outperforms' claim. These issues, while fixable, are load-bearing for the paper's central claims.
major comments (3)
- [Section 3.4, Eq. (48)] The normalization update breaks the defining identity C^{-1}=WΛW^T+ξI. After setting D_n=DS^{-1}, W_n=SW, C_n=S^{-1}CS^{-1}, and U_n=S^{-1}U, one obtains C_n^{-1}=SC^{-1}S=S(WΛW^T+ξI)S=W_nΛW_n^T+ξS^2, which is not equal to W_nΛW_n^T+ξI unless S=I. Consequently, the recursive updates in Eqs. (27), (30), (33), and (36), which all rely on the identity C^{-1}=WΛW^T+ξI, no longer update the correct inverse after normalization is applied. Algorithm 1 (Step 5) and the statement in Section 4 that the necessity of normalization is checked whenever the profile is pruned mean that the reported experiments may be affected by this inconsistency; the manuscript does not specify the threshold that triggers 'necessary', so the reader cannot determine whether normalization was actually applied in the reported runs.
- [Section 4.2 and 4.3] The experimental comparison is not rigorous enough to support the central claim of outperforming existing online kernel dictionary learning algorithms. The statement 'Each algorithm is implemented with its own parameter values that result in higher accuracy' is not a controlled tuning protocol; it introduces a potential bias in favor of the proposed method. Figures 1 and 2 show only averaged classification accuracy over folds, without error bars, standard deviations, or statistical significance tests. The differences between KRLS and the other algorithms may be within fold variance, especially in the EEG and DistNet panels where accuracies are close. Table 2 reports average training times without variance or a clear statement on how many repetitions were used. The paper should either provide error bars and significance tests or temper the claim accordingly.
- [Section 3.3 (Profile Growing and Pruning)] The profile abstraction criteria are heuristic and are not shown to preserve the representational quality of the dictionary. The growing rule (Eq. 44, coherency threshold δ) and the pruning rule (removing samples with smallest row norm of B_i = U_i^T W_i) are plausible but unproven; the paper only checks non-singularity conditions for pruning, not whether the selected samples remain representative of the data subspace. Since the claim that KRLS approaches the batch KMOD accuracy depends on these criteria, the paper should either provide a theoretical justification (e.g., a bound on the approximation error introduced by growing/pruning) or an empirical ablation showing that the results do not degrade when these steps are varied.
minor comments (4)
- [Notation review] The notation review states that 'N is the dimensionality of the feature space or the number of elements in each data vector'; this appears to be a typo, since N is used throughout as the dimensionality of the input space. Please correct the wording.
- [Eq. (24)] The set Ω_i is described in words but never formally defined; a precise definition would help the reader understand the rolling regularization factor ξ_i and its role in the recursive updates.
- [Figure 1 and Figure 2] The captions are minimal and do not indicate the hyperparameter settings for each algorithm or the number of repetitions; adding standard deviation bands and stating the hyperparameter values used would improve reproducibility.
- [Section 4.2] The paper reports Q=30, L_max=200, M=10, γ=0.1, and s=5 without sensitivity analysis; a brief discussion of how these choices affect the results would strengthen the empirical claims.
Circularity Check
No significant circularity: the recursive updates are derived from the stated LS objective via the matrix inversion lemma, and the only self-citations are non-load-bearing prior-work context.
full rationale
The paper's derivation chain is self-contained. Section 2 defines the kernelized least-squares dictionary learning objective (Eq. 8) and obtains D*=(ΦW^T)(W W^T + γ I)^{-1} (Eq. 9) by standard normal equations. Section 3 then derives recursive updates for C, U, D, and Ψ using the matrix inversion lemma (Eqs. 25-33); appendix A shows the algebra explicitly. The representer-theorem form D=ΦU^T is imported from the external KMOD paper [21], and the recursive update structure is inspired by RLS DL [34] and KRLS [39], but no conclusion is forced by a self-citation. The paper's own [34] (Skretting) and [7] (Skretting and Husøy) are used as building blocks or subroutines, not as evidence for the claimed novelty or for the correctness of the new update equations. Profile growing and pruning are acknowledged heuristics with explicit conditions; their lack of an optimality proof is a limitation, not circularity. One internal-consistency concern belongs to correctness, not circularity: after normalization (Eq. 48), C_n=S^{-1}CS^{-1} is not generally equal to (W_n Λ W_n^T + ξ I)^{-1}, so the recursive C update would need re-derivation after normalization. This is an algebraic issue in the implementation as written, but it does not make the paper's predictions equivalent to its inputs. The experimental comparison is against external benchmarks with a common KORMP sparse coder, so the reported improvements are not forced by construction.
Assumptions & free parameters
free parameters (8)
- Regularization parameter γ =
0.1
- Forgetting factor λ schedule =
linearly from 0.98 to 1 over first 80% of batches
- Coherency threshold δ =
not specified in text
- Dictionary size Q =
30
- Maximum profile size L_max =
200
- Mini-batch size M =
10
- Sparsity level s =
5
- Number of training mini-batches =
60 in figures
assumptions (5)
- domain assumption The optimal dictionary in the RKHS can be expressed as D* = ΦB (representer theorem form).
- domain assumption The kernel function is a Mercer kernel, inducing a reproducing kernel Hilbert space.
- domain assumption The alternating optimization between sparse approximation and dictionary update converges.
- ad hoc to paper The profile growing and pruning criteria preserve dictionary quality.
- standard math The matrix inversion lemma is valid for the involved matrices.
Cite this review
Pith. "Pith review of Kernel Recursive Least Squares Dictionary Learning Algorithm." pith.science (2026). https://pith.science/paper/GB6UL63X
@misc{pith2026250701636,
author = {Pith},
title = {Pith review of: Kernel Recursive Least Squares Dictionary Learning Algorithm},
year = {2026},
howpublished = {\url{https://pith.science/paper/GB6UL63X}},
note = {Machine review of arXiv:2507.01636}
}
read the original abstract
We propose an efficient online dictionary learning algorithm for kernel-based sparse representations. In this framework, input signals are nonlinearly mapped to a high-dimensional feature space and represented sparsely using a virtual dictionary. At each step, the dictionary is updated recursively using a novel algorithm based on the recursive least squares (RLS) method. This update mechanism works with single samples or mini-batches and maintains low computational complexity. Experiments on four datasets across different domains show that our method not only outperforms existing online kernel dictionary learning approaches but also achieves classification accuracy close to that of batch-trained models, while remaining significantly more efficient.
Figures
Reference graph
Works this paper leans on
-
[1]
Sparse representation for signal classifi- cation,
K. Huang and S. Aviyente, “Sparse representation for signal classifi- cation,” Advances in neural information processing systems , vol. 19, pp. 609–616, 2006
work page 2006
-
[2]
Dictionaries for sparse representation modeling,
R. Rubinstein, A. M. Bruckstein, and M. Elad, “Dictionaries for sparse representation modeling,” Proceedings of the IEEE , vol. 98, no. 6, pp. 1045–1057, 2010. 27
work page 2010
-
[3]
A survey of sparse rep- resentation: algorithms and applications,
Z. Zhang, Y. Xu, J. Yang, X. Li, and D. Zhang, “A survey of sparse rep- resentation: algorithms and applications,” IEEE access, vol. 3, pp. 490– 530, 2015
work page 2015
-
[4]
Sparse representation for computer vision and pattern recognition,
J. Wright, Y. Ma, J. Mairal, G. Sapiro, T. S. Huang, and S. Yan, “Sparse representation for computer vision and pattern recognition,”Proceedings of the IEEE , vol. 98, no. 6, pp. 1031–1044, 2010
work page 2010
-
[5]
Matching pursuits with time-frequency dictionaries,
S. G. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Transactions on signal processing , vol. 41, no. 12, pp. 3397–3415, 1993
1993
-
[6]
Atomic decomposition by basis pursuit,
S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM review, vol. 43, no. 1, pp. 129–159, 2001
2001
-
[7]
Partial search vector selection for sparse signal representation,
K. Skretting and J. H. Husøy, “Partial search vector selection for sparse signal representation,” in Nordic Signal Processing Symposium (NOR- SIG), pp. 1–6, IEEE, 2008
work page 2008
-
[8]
Method of optimal directions for frame design,
K. Engan, S. O. Aase, and J. H. Husoy, “Method of optimal directions for frame design,” in 1999 IEEE International Conference on Acous- tics, Speech, and Signal Processing. Proceedings. ICASSP99 (Cat. No. 99CH36258), vol. 5, pp. 2443–2446, IEEE, 1999
work page 1999
Show all 43 references
-
[9]
K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,
M. Aharon, M. Elad, and A. Bruckstein, “K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,” IEEE Transactions on signal processing, vol. 54, no. 11, pp. 4311–4322, 2006
2006
-
[10]
Shawe-Taylor, N
J. Shawe-Taylor, N. Cristianini, et al., Kernel methods for pattern anal- ysis. Cambridge university press, 2004
2004
-
[11]
Kernel methods in machine learning,
T. Hofmann, B. Sch¨ olkopf, and A. J. Smola, “Kernel methods in machine learning,” The annals of statistics , vol. 36, no. 3, pp. 1171–1220, 2008
2008
-
[12]
Kernel sparse representation based model for skin lesions segmentation and classification,
N. Moradi and N. Mahdavi-Amiri, “Kernel sparse representation based model for skin lesions segmentation and classification,” Computer meth- ods and programs in biomedicine , vol. 182, p. 105038, 2019
2019
-
[13]
Automatic lumen border detection in ivus images using dictionary learning and kernel sparse representation,
J. Tong, K. Li, W. Lin, X. Shudong, A. Anwar, and L. Jiang, “Automatic lumen border detection in ivus images using dictionary learning and kernel sparse representation,” Biomedical Signal Processing and Control, vol. 66, p. 102489, 2021. 28
2021
-
[14]
Image quality assessment us- ing kernel sparse coding,
Z. Zhou, J. Li, Y. Quan, and R. Xu, “Image quality assessment us- ing kernel sparse coding,” IEEE Transactions on Multimedia , vol. 23, pp. 1592–1604, 2020
2020
-
[15]
Optimal dis- criminative feature and dictionary learning for image set classification,
G. Zhang, J. Yang, Y. Zheng, Z. Luo, and J. Zhang, “Optimal dis- criminative feature and dictionary learning for image set classification,” Information Sciences, vol. 547, pp. 498–513, 2021
2021
-
[16]
Linearized kernel dictionary learning with group sparse priors for action recognition,
C. Fan, C. Hu, and B. Liu, “Linearized kernel dictionary learning with group sparse priors for action recognition,” The Visual Computer , vol. 35, no. 12, pp. 1797–1807, 2019
2019
-
[17]
Domain adaption based on source dictionary regularized rkhs subspace learning,
W. Lei, Z. Ma, Y. Lin, and W. Gao, “Domain adaption based on source dictionary regularized rkhs subspace learning,” Pattern Analysis and Applications, pp. 1–20, 2021
2021
-
[18]
A recursive model of residual life prediction for human beings with health infor- mation from activities of daily living and memory,
K. Gao, T. Wang, K. Peng, Z. Wang, Q. He, and R. Peng, “A recursive model of residual life prediction for human beings with health infor- mation from activities of daily living and memory,” Systems Science & Control Engineering, vol. 9, no. 1, pp. 529–541, 2021
2021
-
[19]
Fast kernel sparse representation,
H. Li, Y. Gao, and J. Sun, “Fast kernel sparse representation,” in 2011 International Conference on Digital Image Computing: Techniques and Applications, pp. 72–77, IEEE, 2011
2011
-
[20]
Kernel sparse representation based classification,
J. Yin, Z. Liu, Z. Jin, and W. Yang, “Kernel sparse representation based classification,” Neurocomputing, vol. 77, no. 1, pp. 120–128, 2012
2012
-
[21]
Design of non-linear kernel dictionaries for object recognition,
H. Van Nguyen, V. M. Patel, N. M. Nasrabadi, and R. Chellappa, “Design of non-linear kernel dictionaries for object recognition,” IEEE Transactions on Image Processing, vol. 22, no. 12, pp. 5123–5135, 2013
2013
-
[22]
Kernel sparse representation-based classifier,
L. Zhang, W.-D. Zhou, P.-C. Chang, J. Liu, Z. Yan, T. Wang, and F.-Z. Li, “Kernel sparse representation-based classifier,” IEEE Transactions on Signal Processing, vol. 60, no. 4, pp. 1684–1695, 2011
2011
-
[23]
Visual classification with multitask joint sparse representation,
X.-T. Yuan, X. Liu, and S. Yan, “Visual classification with multitask joint sparse representation,” IEEE Transactions on Image Processing , vol. 21, no. 10, pp. 4349–4360, 2012
2012
-
[24]
Kernel sparse representation for image classification and face recognition,
S. Gao, I. W.-H. Tsang, and L.-T. Chia, “Kernel sparse representation for image classification and face recognition,” in European conference on computer vision, pp. 1–14, Springer, 2010. 29
2010
-
[25]
Sparse coding and dictionary learning for symmetric positive definite matri- ces: A kernel approach,
M. T. Harandi, C. Sanderson, R. Hartley, and B. C. Lovell, “Sparse coding and dictionary learning for symmetric positive definite matri- ces: A kernel approach,” in European Conference on Computer Vision , pp. 216–229, Springer, 2012
2012
-
[26]
Log-Euclidean kernels for sparse representation and dictionary learning,
P. Li, Q. Wang, W. Zuo, and L. Zhang, “Log-Euclidean kernels for sparse representation and dictionary learning,” in Proceedings of the IEEE international conference on computer vision, pp. 1601–1608, 2013
2013
-
[27]
Manifold kernel sparse rep- resentation of symmetric positive-definite matrices and its applications,
Y. Wu, Y. Jia, P. Li, J. Zhang, and J. Yuan, “Manifold kernel sparse rep- resentation of symmetric positive-definite matrices and its applications,” IEEE Transactions on Image Processing, vol. 24, no. 11, pp. 3729–3741, 2015
2015
-
[28]
Multiple kernel sparse representations for supervised and unsupervised learning,
J. J. Thiagarajan, K. N. Ramamurthy, and A. Spanias, “Multiple kernel sparse representations for supervised and unsupervised learning,” IEEE transactions on Image Processing , vol. 23, no. 7, pp. 2905–2915, 2014
2014
-
[29]
Kernel sparse representation for time series classification,
Z. Chen, W. Zuo, Q. Hu, and L. Lin, “Kernel sparse representation for time series classification,” Information Sciences, vol. 292, pp. 15–26, 2015
2015
-
[30]
Sparse kernel dictionary learning,
C. O’Brien and M. D. Plumbley, “Sparse kernel dictionary learning,” in Proceedings of the 11th IMA International Conference on Mathematics in Signal Processing, 2016
2016
-
[31]
Greedy dictionary learning for ker- nel sparse representation based classifier,
V. Abrol, P. Sharma, and A. K. Sao, “Greedy dictionary learning for ker- nel sparse representation based classifier,” Pattern Recognition Letters, vol. 78, pp. 64–69, 2016
2016
-
[32]
Linearized kernel dictionary learning,
A. Golts and M. Elad, “Linearized kernel dictionary learning,” IEEE Journal of Selected Topics in Signal Processing , vol. 10, no. 4, pp. 726– 739, 2016
2016
-
[33]
Online learning for ma- trix factorization and sparse coding.,
J. Mairal, F. Bach, J. Ponce, and G. Sapiro, “Online learning for ma- trix factorization and sparse coding.,” Journal of Machine Learning Re- search, vol. 11, no. 1, 2010
2010
-
[34]
Recursive least squares dictionary learning algorithm,
K. Skretting and K. Engan, “Recursive least squares dictionary learning algorithm,” IEEE Transactions on Signal Processing , vol. 58, no. 4, pp. 2121–2130, 2010
2010
-
[35]
Generalized adap- tive weighted recursive least squares dictionary learning,
Y. Naderahmadian, M. A. Tinati, and S. Beheshti, “Generalized adap- tive weighted recursive least squares dictionary learning,” Signal Pro- cessing, vol. 118, pp. 89–96, 2016. 30
2016
-
[36]
Online dictionary learning on symmetric positive definite manifolds with vision applications,
S. Zhang, S. Kasiviswanathan, P. C. Yuen, and M. Harandi, “Online dictionary learning on symmetric positive definite manifolds with vision applications,” in Twenty-Ninth AAAI Conference on Artificial Intelli- gence, 2015
2015
-
[37]
Online kernel dictionary learning for object recog- nition,
H. Liu and F. Sun, “Online kernel dictionary learning for object recog- nition,” in 2016 IEEE International Conference on Automation Science and Engineering (CASE) , pp. 268–273, IEEE, 2016
2016
-
[38]
Online kernel dictionary learning on a budget,
J. Lee and S.-J. Kim, “Online kernel dictionary learning on a budget,” in 2016 50th Asilomar Conference on Signals, Systems and Computers , pp. 1535–1539, IEEE, 2016
2016
-
[39]
The kernel recursive least-squares algorithm,
Y. Engel, S. Mannor, and R. Meir, “The kernel recursive least-squares algorithm,” IEEE Transactions on Signal Processing , vol. 52, no. 8, pp. 2275–2285, 2004
2004
-
[40]
W. Liu, J. C. Principe, and S. S. Haykin, Kernel adaptive filtering: a comprehensive introduction, vol. 1. Wiley Online Library, 2010
2010
-
[41]
S. S. Haykin, Adaptive Filter Theory , vol. 1. Pearson, fifth ed., 2014
2014
-
[42]
EEG in schizophrenia,
E. Olejarczyk and W. Jernajczyk, “EEG in schizophrenia,” RepOD,
-
[2006]
https://doi.org/10.18150/repod.0107441. 31
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.