A Fast Spectral Relaxation Approach to Matrix Completion via Kronecker Products

Authors

  • Hui Zhao Xi'an Jiaotong University
  • Jiuqiang Han Xi'an Jiaotong University
  • Naiyan Wang Zhejiang University
  • Congfu Xu Zhejiang University
  • Zhihua Zhang Zhejiang University

Abstract

In the existing methods for solving matrix completion, such as singular value thresholding (SVT), soft-impute and fixed point continuation (FPCA) algorithms, it is typically required to repeatedly implement singular value decompositions (SVD) of matrices.When the size of the matrix in question is large, the computational complexity of finding a solution is costly. To reduce this expensive computational complexity, we apply Kronecker products to handle the matrix completion problem. In particular, we propose using Kronecker factorization, which approximates a matrix by the Kronecker product of several matrices of smaller sizes. Weintroduce Kronecker factorization into the soft-impute framework and devise an effective matrix completion algorithm.Especially when the factorized matrices have about the samesizes, the computational complexity of our algorithm is improved substantially.

Downloads

Published

2011-08-04

How to Cite

Zhao, H., Han, J., Wang, N., Xu, C., & Zhang, Z. (2011). A Fast Spectral Relaxation Approach to Matrix Completion via Kronecker Products. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 580-585. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7913

Issue

Section

AAAI Technical Track: Machine Learning