Speaker: Nihar Shah

Abstract: Noisy matrix non-negative matrix completion involves reconstructing a structured matrix whose entries are partially observed in noise. Standard approaches to this problem are based on assuming that the underlying matrix has a low (non-negative) rank. We first describe how this classical non-negative rank model enforces restrictions that may be quite undesirable in practice. We propose a richer model based on what we term the "permutation-rank" of a matrix, and show how these restrictions can be avoided by using this richer model. Second, we establish the minimax rates of estimation under the new permutation-based model, and prove that surprisingly, the minimax rates are equivalent up to logarithmic factors to those for estimation under the typical low rank model. We also analyze a computationally efficient singular-value-thresholding algorithm, known to be optimal for the low-rank setting, and show that it also simultaneously yields a consistent estimator for the low-permutation rank setting.