Matrix Completion using Kronecker Product Approximation
A matrix completion problem is to recover the missing entries in a partially observed matrix. Most of the existing matrix completion methods assume a low rank structure of the underlying complete matrix. In this paper, we introduce an alternative and more general form of the underlying complete matrix, which assumes a low Kronecker rank instead of a low regular rank, but includes the latter as a special case. The extra flexibility allows for a much more parsimonious representation of the underlying matrix, but also raises the challenge of determining the proper Kronecker product configuration to be used. We find that the configuration can be identified using the mean squared error criterion as well as a modified cross-validation criterion. We establish the consistency of this procedure under suitable conditions on the signal-to-noise ratio. A aggregation procedure is also proposed to deal with special missing patterns and complex underlying structures. Both numerical and empirical studies are carried out to demonstrate the performance of the new method.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringDenoisingMatrix CompletionSimilar Papers 제목 키워드 기반
KoPA: Automated Kronecker Product Approximation
We consider the problem of matrix approximation and denoising induced by the Kronecker product decomposition. Specifically, we propose to approximate a given matrix by the sum of a few Kronecker products of matrices, whi…
DenoisingHybrid Kronecker Product Decomposition and Approximation
Discovering the underlying low dimensional structure of high dimensional data has attracted a significant amount of researches recently and has shown to have a wide range of applications. As an effective dimension reduct…
Dimensionality ReductionA New Perspective on Shampoo's Preconditioner
Shampoo, a second-order optimization algorithm which uses a Kronecker product preconditioner, has recently garnered increasing attention from the machine learning community. The preconditioner used by Shampoo can be view…
Quantum Speedup for Spectral Approximation of Kronecker Products
Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render it an expensive operation, leading to h…
Sketching for Kronecker Product Regression and P-splines
TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subs…
regression