×

Approximation of kernel matrices by circulant matrices and its application in kernel selection methods. (English) Zbl 1191.65190

Authors’ abstract: This paper focuses on developing fast numerical algorithms for selection of a kernel optimal for a given training data set. The optimal kernel is obtained by minimizing a cost functional over a prescribed set of kernels. The cost functional is defined in terms of a positive semi-definite matrix determined completely by a given kernel and the given sampled input data. Fast computational algorithms are developed by approximating the positive semi-definite matrix by a related circulant matrix so that the fast Fourier transform can apply to achieve a linear or quasi-linear computational complexity for finding the optimal kernel. We establish convergence of the approximation method. Numerical examples are presented to demonstrate the approximation accuracy and computational efficiency of the proposed methods.

MSC:

65R20 Numerical methods for integral equations
45Q05 Inverse problems for integral equations
46E22 Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces)
68Q32 Computational learning theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Argyriou A, Micchelli C A, Pontil M, Ying Y. A spectral regularization framework for multi-task structure learning. NIPS, 2008, 20: 25–32
[2] Aronszajn N. Theory of reproducing kernels. Trans Amer Math Soc, 1950, 68: 337–404 · Zbl 0037.20701 · doi:10.1090/S0002-9947-1950-0051437-7
[3] Bhatia R. Matrix Analysis. New York: Springer, 1997
[4] Bochner S. Lectures on Fourier Integrals. Princeton: Princeton University Press, 1959 · Zbl 0085.31802
[5] de Boor C. A Practical Guide to Splines. New York: Springer-Verlag, 1978 · Zbl 0406.41003
[6] Bousquet O, Herrmann D J L. On the complexity of learning the kernel matrix. NIPS, 2003, 15: 399–406
[7] Chapelle O, Vapnik V, Bousquet O, Mukherjee S. Choosing multiple parameters for support vector machines. Machine Learning, 2002, 46: 131–159 · Zbl 0998.68101 · doi:10.1023/A:1012450327387
[8] Cormen T H, Leiserson C E, Rivest R L, Stein C. Introduction to Algorithms. Boston: MIT Press, 2001 · Zbl 1047.68161
[9] Cristianini N, Shawe-Taylor J, Elisseeff A, Kandola J. On kernel-target alignment. NIPS, 2002, 14: 367–373
[10] Cucker F, Smale S. On the mathematical foundations of learning. Bull Amer Math Soc, 2002, 39: 1–49 · Zbl 0983.68162 · doi:10.1090/S0273-0979-01-00923-5
[11] Davis P J. Circulant Matrices. New York: John Wiley & Sons Inc, 1979
[12] Demko S, Moss W, Smith P. Decay rates for inverses of band matrices. Math Comput, 1984, 43: 491–499 · Zbl 0568.15003 · doi:10.1090/S0025-5718-1984-0758197-9
[13] Drucker H, Wu D, Vapnik V N. Support vector machines for span categorization. IEEE Trans Neural Networks, 1999, 10: 1048–1054 · doi:10.1109/72.788645
[14] Durrett R. Probability: Theory and Examples. Belmont: Duxbury Press, 1996 · Zbl 1202.60001
[15] Gasquet C, Witomski P. Fourier Analysis and Applications. New York: Springer-Verlag, 1999 · Zbl 0931.94001
[16] Gelfand I, Raikov D, Shilov G. Commutative Normed Rings. Bronx: Chelsea Publishing Company, New York, 1964
[17] Gray R M. Toeplitz and Circulant Matrices: A Review. Boston: Now Publishers Inc, 2006 · Zbl 1115.15021
[18] Grenander U, Szegö G. Toeplitz Forms and Their Applications. Berkeley and Los Angeles: University of Calif Press, 1958 · Zbl 0080.09501
[19] Horn R A, Johnson C R. Matrix Analysis. Cambridge: Cambridge University Press, 1986
[20] Kimeldorf G, Wahba G. Some results on Tchebycheffian spline functions. J Math Anal Appl, 1971, 33: 82–95 · Zbl 0201.39702 · doi:10.1016/0022-247X(71)90184-3
[21] Lanckriet G R G, Cristianini N, Bartlett P, El Ghaoui L, Jordan M I. Learning the kernel matrix with semi-definite programming. J Mach Learn Res, 2004, 5: 27–72 · Zbl 1222.68241
[22] Lin Y, Brown L D. Statistical properties of the method of regularization with periodic Gaussian reproducing kernel. Ann Statis, 2004, 32: 1723–1743 · Zbl 1045.62026 · doi:10.1214/009053604000000454
[23] Micchelli C A, Pontil M. Learning the kernel function via regularization. J Mach Learn Res, 2005, 6: 1099–1125 · Zbl 1222.68265
[24] Micchelli C A, Pontil M. On learning vector-valued functions. Neural Comput, 2005, 17: 177–204 · Zbl 1092.93045 · doi:10.1162/0899766052530802
[25] Müller K -R, Smola A J, Rätsch G, Schölkopf B, Kohlmorgen J, Vapnik V N. Predicting time series with support vector machines. Lecture Notes in Computer Science, 1997, 1327: 999–1004 · doi:10.1007/BFb0020283
[26] Schölkopf B, Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Cambridge: MIT Press, 2004 · Zbl 1072.68541
[27] Serre T, Wolf L, Bileschi S, Riesenhuber M, Poggio T. Robust object recognition with cortex-like mechanisms. IEEE Trans Pattern Analysis and Machine Intelligence, 2007, 29: 411–426 · Zbl 05340761 · doi:10.1109/TPAMI.2007.56
[28] Shawe-Taylor J, Cristianini N. Kernel Methods for Pattern Analysis. Cambridge: Cambridge University Press, 2004 · Zbl 0994.68074
[29] Smola A J, Schölkopf B. On a kernel-based method for pattern recognition, regression, approximation, and operator inversion. Algorithmica, 1998, 22: 211–231 · Zbl 0910.68189 · doi:10.1007/PL00013831
[30] Sung K K, Poggio T. Example-based learning for view-based human face detection. IEEE Trans Pattern Analysis and Machine Intelligence, 1998, 20: 39–51 · Zbl 05110547 · doi:10.1109/34.655648
[31] Vapnik V N. Statistical Learning Theory. New York: Wiley, 1998 · Zbl 0935.62007
[32] Xu Y, Zhang H. Refinable kernels. J Mach Learn Res, 2007, 8: 2083–2120 · Zbl 1222.68337
[33] Xu Y, Zhang H. Refinement of reproducing kernels. J Mach Learn Res, 2009, 10: 137–170 · Zbl 1235.68211
[34] Ying Y, Zhou D X. Learnability of Gaussians with flexible variances. J Mach Learn Res, 2007, 8: 249–276 · Zbl 1222.68339
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.