Adaptive Multinomial Matrix Completion
The task of estimating a matrix given a sample of observed entries is known as the \emph{matrix completion problem}. Most works on matrix completion have focused on recovering an unknown real-valued low-rank matrix from a random sample of its entries. Here, we investigate the case of highly quantized observations when the measurements can take only a small number of values. These quantized outputs are generated according to a probability distribution parametrized by the unknown matrix of interest. This model corresponds, for example, to ratings in recommender systems or labels in multi-class classification. We consider a general, non-uniform, sampling scheme and give theoretical guarantees on the performance of a constrained, nuclear norm penalized maximum likelihood estimator. One important advantage of this estimator is that it does not require knowledge of the rank or an upper bound on the nuclear norm of the unknown matrix and, thus, it is adaptive. We provide lower bounds showing that our estimator is minimax optimal. An efficient algorithm based on lifted coordinate gradient descent is proposed to compute the estimator. A limited Monte-Carlo experiment, using both simulated and real data is provided to support our claims.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionMulti-class ClassificationRecommendation SystemsSimilar Papers 제목 키워드 기반
Low-rank matrix completion and denoising under Poisson noise
This paper considers the problem of estimating a low-rank matrix from the observation of all or a subset of its entries in the presence of Poisson noise. When we observe all entries, this is a problem of matrix denoising…
DenoisingLow-Rank Matrix CompletionMatrix CompletionSurvey of Matrix Completion Algorithms
Matrix completion problem has been investigated under many different conditions since Netflix announced the Netflix Prize problem. Many research work has been done in the field once it has been discovered that many real …
compressed sensingMatrix CompletionSurveyAdaptive Noisy Matrix Completion
Low-rank matrix completion has been studied extensively under various type of categories. The problem could be categorized as noisy completion or exact completion, also active or passive completion algorithms. In this pa…
Low-Rank Matrix CompletionMatrix CompletionAdaptive Matrix Completion for the Users and the Items in Tail
Recommender systems are widely used to recommend the most appealing items to users. These recommendations can be generated by applying collaborative filtering methods. The low-rank matrix completion method is the state-o…
Collaborative FilteringLow-Rank Matrix CompletionMatrix CompletionRecommendation SystemsBayesian Matrix Completion via Adaptive Relaxed Spectral Regularization
Bayesian matrix completion has been studied based on a low-rank matrix factorization formulation with promising results. However, little work has been done on Bayesian matrix completion based on the more direct spectral …
Bayesian InferenceCollaborative FilteringMatrix Completion