Low Permutation-rank Matrices: Structural Properties and Noisy Completion

Nihar B. Shah, Sivaraman Balakrishnan, Martin J. Wainwright

We consider the problem of noisy matrix completion, in which the goal is to reconstruct a structured matrix whose entries are partially observed in noise. Standard approaches to th…