Abstract

We consider the question whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit low-rank regularization. We focus on the noiseless matrix sensing scenario over low-rank positive semi-definite (PSD) matrices over the reals, with a sensing mechanism that satisfies restricted isometry properties. Surprisingly, it was recently argued that for recovery of PSD matrices, gradient descent over a squared,\textit {full-rank} factorized space introduces implicit low-rank regularization. Thus, a clever choice of the recovery algorithm avoids the need for explicit low-rank regularization. In this contribution, we prove that in fact, under certain conditions, the PSD constraint by itself is sufficient to lead to a unique low-rank matrix recovery, without explicit or implicit regularization. Therefore, under these conditions, the set of PSD matrices that are consistent with the observed data, is a singleton, regardless of the algorithm used. Our numerical study indicates that this result is general and extends to cases beyond the those covered by the proof.

Date

June 3, 2020

Authors

Kelly Geyer, Anastasios Kyrillidis, Amir Kalev

Conference

International Conference on Artificial Intelligence and Statistics

Pages

930-940

Publisher

PMLR