De-biasing low-rank projection for matrix completion Conference Paper uri icon


  • 2017 SPIE. We study matrix completion with non-uniform, deterministic sampling patterns. We introduce a computable parameter, which is a function of the sampling pattern, and show that if this parameter is small, then we may recover missing entries of the matrix, with appropriate weights. We theoretically analyze a simple and well-known recovery method, which simply projects the (zero-padded) subsampled matrix onto the set of low-rank matrices. We show that under non-uniform deterministic sampling, this method yields a biased solution, and we propose an algorithm to de-bias it. Numerical simulations demonstrate that de-biasing significantly improves the estimate. However, when the observations are noisy, the error of this method can be sub-optimal when the sampling is highly non-uniform. To remedy this, we suggest an alternative which is based on projection onto the max-norm ball whose robustness to noise tolerates arbitrarily non-uniform sampling. Finally, we analyze convex optimization in this framework.

name of conference

  • Wavelets and Sparsity XVII

published proceedings


author list (cited authors)

  • Foucart, S., Needell, D., Plan, Y., & Wootters, M.

citation count

  • 7

complete list of authors

  • Foucart, Simon||Needell, Deanna||Plan, Yaniv||Wootters, Mary

editor list (cited editors)

  • Lu, Y. M., Papadakis, M., & Van De Ville, D.

publication date

  • January 2017