More Web Proxy on the site http://driver.im/

Article

Learning low-rank kernel matrices

Authors:

Mátyás Sustik,

Inderjit DhillonAuthors Info & Claims

ICML '06: Proceedings of the 23rd international conference on Machine learning

Pages 505 - 512

https://doi.org/10.1145/1143844.1143908

Published: 25 June 2006 Publication History

Abstract

Kernel learning plays an important role in many machine learning tasks. However, algorithms for learning a kernel matrix often scale poorly, with running times that are cubic in the number of data points. In this paper, we propose efficient algorithms for learning low-rank kernel matrices; our algorithms scale linearly in the number of data points and quadratically in the rank of the kernel. We introduce and employ Bregman matrix divergences for rank-deficient matrices---these divergences are natural for our problem since they preserve the rank as well as positive semi-definiteness of the kernel matrix. Special cases of our framework yield faster algorithms for various existing kernel learning problems. Experimental results demonstrate the effectiveness of our algorithms in learning both low-rank and full-rank kernels.

References

[1]

Bach, F., & Jordan, M. (2005). Predictive low-rank decomposition for kernel methods. Proc. ICML-2005.]]

Digital Library

[2]

Barnes, J., & Hut, P. (1986). A hierarchical O(n log n) force calculation algorithm. Nature, 324, 446--449.]]

[3]

Bregman, L. (1967). The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Mathematics and Mathematical Physics, 7, 200--217.]]

[4]

Censor, Y., & Zenios, S. (1997). Parallel optimization. Oxford University Press.]]

Digital Library

[5]

Demmel, J. D. (1997). Applied numerical linear algebra. Society for Industrial and Applied Mathematics.]]

Digital Library

[6]

Fine, S., & Scheinberg, K. (2001). Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2, 243--264.]]

Digital Library

[7]

Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Johns Hopkins University Press.]]

[8]

Greengard, L., & Rokhlin, V. (1987). A fast algorithm for particle simulations. J. Comput. Phys., 73, 325--348.]]

Digital Library

[9]

Higham, N. (2002). Computing the nearest correlation matrix---a problem from finance. IMA J. Numerical Analysis, 22, 329--343.]]

[10]

Kulis, B., Basu, S., Dhillon, I., & Mooney, R. (2005). Semi-supervised graph clustering: A kernel approach. Proc. ICML-2005.]]

Digital Library

[11]

Kwok, J., & Tsang, I. (2003). Learning with idealized kernels. Proc. ICML-2003.]]

[12]

Lanckriet, G., Cristianini, N., Bartlett, P., Ghaoui, L. E., & Jordan, M. (2004). Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5, 27--72.]]

Digital Library

[13]

Shawe-Taylor, J., & Cristianini, N. (2004). Kernel methods for pattern analysis. Cambridge University Press.]]

[14]

Tsuda, K., Rätsch, G., & Warmuth, M. (2005). Matrix exponentiated gradient updates for online learning and Bregman projection. Journal of Machine Learning Research, 6, 995--1018.]]

Digital Library

[15]

Weinberger, K., Sha, F., & Saul, L. (2004). Learning a kernel matrix for nonlinear dimensionality reduction. Proc. ICML-2004.]]

Digital Library

Cited By

Nielsen F(2024)Fast Proxy Centers for the Jeffreys Centroid: The Jeffreys–Fisher–Rao Center and the Gauss–Bregman Inductive CenterEntropy10.3390/e2612100826:12(1008)Online publication date: 22-Nov-2024
https://doi.org/10.3390/e26121008
Zois ETsourounis DKalivas D(2024)Similarity Distance Learning on SPD Manifold for Writer Independent Offline Signature VerificationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333368119(1342-1356)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3333681
Cho NLee TShin H(2024)Recursive Least Squares with Log-Determinant Divergence Regularisation for Online Inertia Identification2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610389(12578-12584)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610389
Show More Cited By

Index Terms

Learning low-rank kernel matrices

Recommendations

Asymptotic error bounds for kernel-based Nyström low-rank approximation matrices

Many kernel-based learning algorithms have the computational load scaled with the sample size n due to the column size of a full kernel Gram matrix K. This article considers the Nystrom low-rank approximation. It uses a reduced kernel K@^, which is nxm, ...
An Implicit Multishift $QR$-Algorithm for Hermitian Plus Low Rank Matrices

Hermitian plus possibly non-Hermitian low rank matrices can be efficiently reduced into Hessenberg form. The resulting Hessenberg matrix can still be written as the sum of a Hermitian plus low rank matrix. In this paper we develop a new implicit ...
Low-Rank Kernel Learning with Bregman Matrix Divergences

In this paper, we study low-rank matrix nearness problems, with a focus on learning low-rank positive semidefinite (kernel) matrices for machine learning applications. We propose efficient algorithms that scale linearly in the number of data points and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '06: Proceedings of the 23rd international conference on Machine learning

June 2006

1154 pages

ISBN:1595933832

DOI:10.1145/1143844

Program Chairs:
William Cohen,
Andrew Moore

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

ICML '06 Paper Acceptance Rate 140 of 548 submissions, 26%;

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
877
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)9

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nielsen F(2024)Fast Proxy Centers for the Jeffreys Centroid: The Jeffreys–Fisher–Rao Center and the Gauss–Bregman Inductive CenterEntropy10.3390/e2612100826:12(1008)Online publication date: 22-Nov-2024
https://doi.org/10.3390/e26121008
Zois ETsourounis DKalivas D(2024)Similarity Distance Learning on SPD Manifold for Writer Independent Offline Signature VerificationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333368119(1342-1356)Online publication date: 2024
https://doi.org/10.1109/TIFS.2023.3333681
Cho NLee TShin H(2024)Recursive Least Squares with Log-Determinant Divergence Regularisation for Online Inertia Identification2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610389(12578-12584)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610389
Kimura RNakatani TKamo NMarc DAraki SUeda TMakino S(2024)Diffusion Model-Based MIMO Speech Denoising and Dereverberation2024 IEEE International Conference on Acoustics, Speech, and Signal Processing Workshops (ICASSPW)10.1109/ICASSPW62465.2024.10626291(455-459)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSPW62465.2024.10626291
Liu RLiu LHe DZhang WLarsson E(2023)Detecting Abrupt Change in Channel Covariance Matrix for MIMO CommunicationIEEE Transactions on Wireless Communications10.1109/TWC.2023.325642322:11(7834-7847)Online publication date: Nov-2023
https://doi.org/10.1109/TWC.2023.3256423
Chen ZXu TWu XWang RKittler J(2023)Hybrid Riemannian Graph-Embedding Metric Learning for Image Set ClassificationIEEE Transactions on Big Data10.1109/TBDATA.2021.31130849:1(75-92)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TBDATA.2021.3113084
Carè ACarli RLibera ARomeres DPillonetto G(2023)Kernel Methods and Gaussian Processes for System Identification and Control: A Road Map on Regularized Kernel-Based Learning for ControlIEEE Control Systems10.1109/MCS.2023.329162543:5(69-110)Online publication date: Oct-2023
https://doi.org/10.1109/MCS.2023.3291625
Kasa SRajan V(2023)Avoiding inferior clusterings with misspecified Gaussian mixture modelsScientific Reports10.1038/s41598-023-44608-313:1Online publication date: 6-Nov-2023
https://doi.org/10.1038/s41598-023-44608-3
Li JWang NGong SJiang XZhang D(2023)Metric learning and local enhancement based collaborative representation for hyperspectral image classificationMultimedia Tools and Applications10.1007/s11042-023-17198-583:14(42459-42484)Online publication date: 16-Oct-2023
https://doi.org/10.1007/s11042-023-17198-5
Wu HWang WXia ZChen YLiu YChen J(2023)A discriminative multiple-manifold network for image set classificationApplied Intelligence10.1007/s10489-023-04900-153:21(25119-25134)Online publication date: 3-Aug-2023
https://doi.org/10.1007/s10489-023-04900-1
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents