A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
We consider in this paper the problem of noisy 1-bit matrix completion under a general non-uniform sampling distribution using the max-norm as a convex relaxation for the rank. A max-norm constrained maximum likelihood estimate is introduced and studied. The rate of convergence for the estimate is obtained. Information-theoretical methods are used to establish a minimax lower bound under the general sampling model. The minimax upper and lower bounds together yield the optimal rate of convergence for the Frobenius norm loss. Computational algorithms and numerical performance are also discussed.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Matrix Completion via Max-Norm Constrained Optimization
Matrix completion has been well studied under the uniform sampling model and the trace-norm regularized methods perform well both theoretically and numerically in such a setting. However, the uniform sampling model is un…
Matrix CompletionLow-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 CompletionDeterministic Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs: Exact and Stable Recovery
In this paper we study the matrix completion problem: Suppose $X \in {\mathbb R}^{n_r \times n_c}$ is unknown except for a known upper bound $r$ on its rank. By measuring a small number $m \ll n_r n_c$ of elements of $X$…
Matrix CompletionMisclassification excess risk bounds for 1-bit matrix completion
This study investigates the misclassification excess risk bound in the context of 1-bit matrix completion, a significant problem in machine learning involving the recovery of an unknown matrix from a limited subset of it…
Matrix CompletionNear-optimal sample complexity for convex tensor completion
We analyze low rank tensor completion (TC) using noisy measurements of a subset of the tensor. Assuming a rank-$r$, order-$d$, $N \times N \times \cdots \times N$ tensor where $r=O(1)$, the best sampling complexity that …