MinimaxRank-1Factorization

We consider the problem of recovering a rank-one matrix from a subset of entries subject to arbitrary perturbations, assuming we have no information about the magnitude of perturbation. We propose a weighted log least square based algorithm whose performance for small disturbances matches exactly the fundamental lower bounds that we derive for this problem, and which are related to the spectral gap of a graph representing the revealed entries. We show that for larger disturbances, potentially exponentially growing errors are unavoidable if no additional information is available. We then propose a second algorithm relying on encoding the matrix factorization in the stationary distribution of a Markov chain and leveraging known lower and upper bounds on the entries, allowing to overcome the exponential error growth. Ours is the first work that achieves minimax bounds on rank-one approximation error with algorithms of near-linear time complexity