TY - JOUR AU - Zhao, Hui AU - Han, Jiuqiang AU - Wang, Naiyan AU - Xu, Congfu AU - Zhang, Zhihua PY - 2011/08/04 Y2 - 2024/03/28 TI - A Fast Spectral Relaxation Approach to Matrix Completion via Kronecker Products JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 25 IS - 1 SE - AAAI Technical Track: Machine Learning DO - 10.1609/aaai.v25i1.7913 UR - https://ojs.aaai.org/index.php/AAAI/article/view/7913 SP - 580-585 AB - <p> 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. </p> ER -