24 August 2017 De-biasing low-rank projection for matrix completion
Author Affiliations +
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.
Conference Presentation
© (2017) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Simon Foucart, Simon Foucart, Deanna Needell, Deanna Needell, Yaniv Plan, Yaniv Plan, Mary Wootters, Mary Wootters, "De-biasing low-rank projection for matrix completion", Proc. SPIE 10394, Wavelets and Sparsity XVII, 1039417 (24 August 2017); doi: 10.1117/12.2275004; https://doi.org/10.1117/12.2275004

Back to Top