Fast Generalized Matrix Regression with Applications in Machine Learning
Fast matrix algorithms have become the fundamental tools of machine learning in big data era. The generalized matrix regression problem is widely used in the matrix approximation such as CUR decomposition, kernel matrix approximation, and stream singular value decomposition (SVD), etc. In this paper, we propose a fast generalized matrix regression algorithm (Fast GMR) which utilizes sketching technique to solve the GMR problem efficiently. Given error parameter $0<\epsilon<1$, the Fast GMR algorithm can achieve a $(1+\epsilon)$ relative error with the sketching sizes being of order $\cO(\epsilon^{-1/2})$ for a large group of GMR problems. We apply the Fast GMR algorithm to the symmetric positive definite matrix approximation and single pass singular value decomposition and they achieve a better performance than conventional algorithms. Our empirical study also validates the effectiveness and efficiency of our proposed algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningregressionSimilar Papers 제목 키워드 기반
Learning of Generalized Low-Rank Models: A Greedy Approach
Learning of low-rank matrices is fundamental to many machine learning applications. A state-of-the-art algorithm is the rank-one matrix pursuit (R1MP). However, it can only be used in matrix completion problems with the …
BIG-bench Machine LearningMatrix CompletionA Novel Approach in Solving Stochastic Generalized Linear Regression via Nonconvex Programming
Generalized linear regressions, such as logistic regressions or Poisson regressions, are long-studied regression analysis approaches, and their applications are widely employed in various classification problems. Our stu…
ClusteringregressionA Singular Woodbury and Pseudo-Determinant Matrix Identities and Application to Gaussian Process Regression
We study a matrix that arises from a singular form of the Woodbury matrix identity. We present generalized inverse and pseudo-determinant identities for this matrix, which have direct applications for Gaussian process re…
regressionMeta-Learning with Generalized Ridge Regression: High-dimensional Asymptotics, Optimality and Hyper-covariance Estimation
Meta-learning involves training models on a variety of training tasks in a way that enables them to generalize well on new, unseen test tasks. In this work, we consider meta-learning within the framework of high-dimensio…
Meta-LearningregressionRiemannian optimizationLearning in High-Dimensional Feature Spaces Using ANOVA-Based Fast Matrix-Vector Multiplication
Kernel matrices are crucial in many learning tasks such as support vector machines or kernel ridge regression. The kernel matrix is typically dense and large-scale. Depending on the dimension of the feature space even th…
regression